<div dir="ltr"><div>...and adding $0.02 to the "IR outline + inline + MIR outline" idea, my gut feeling (yes, only a "feeling" -- and one coming from my gut, not head!) is that inlining correcting wrong IR outlining decisions with MIR outlining correcting wrong inlining decisions is absolutely unrealistic and a heuristics nightmare at best.<br><br></div><div>Inliner's heuristics are already complex enough and not 100% bulletproof; if we add IR outliner heuristics to the mix -- and then just a little bit of MIR outliner heuristics (which are more precise but, as demonstrated above, not 100% precise as well) on top... you can imagine.<br></div><div><br></div><div>Yours,<br>Andrey<br><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 1, 2017 at 10:07 AM, Andrey Bokhanko <span dir="ltr"><<a href="mailto:andreybokhanko@gmail.com" target="_blank">andreybokhanko@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>All,<br><br>+1 to what Mehdi said.<br><br></div><div>It's a fair concern to question whatever we need yet another Outlining pass. I believe this concern has been cleared by River -- both with theoretical arguments and practical data (benchmark numbers).<br><br></div><div>Jessica's pipeline proposal is completely orthogonal. It's not fair to request River to implement / fit into what she suggested. Sure, it's a valid topic to discuss -- but yet completely orthogonal one. If anything, accepting River's implementation would enable us to do experiments / developments like pipeline changes of this ilk!<br></div><div><br></div>Yours,<br></div>Andrey<br>===<br></div>Compiler Architect<br></div>NXP<br><br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 1, 2017 at 7:38 AM, Mehdi AMINI 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>2017-07-28 21:58 GMT-07:00 Chris Bieneman via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">Apologies for delayed joining of this discussion, but I had a few notes from this thread that I really wanted to chime in about.</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">River,</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">I don't mean to put you on the spot, but I do want to start on a semantic issue. In several places in the thread you used the words "we" and "our" to imply that you're not alone in writing this (which is totally fine), but your initial thread presented this as entirely your own work. So, when you said things like "we feel there's an advantage to being at the IR level", can you please clarify who is "we"?</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">Given that there are a number of disagreements and opinions floating around I think it benefits us all to speak clearly about who is taking what stances.</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">One particular disagreement that I think very much needs to be revisited in this thread was Jessica's proposal of a pipeline of:</div>
<ol>
<li style="margin:0px;line-height:normal;color:rgb(69,69,69)">IR outline</li>
<li style="margin:0px;line-height:normal;color:rgb(69,69,69)">Inline</li>
<li style="margin:0px;line-height:normal;color:rgb(69,69,69)">MIR outline</li></ol><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">In your response to that proposal you dismissed it out of hand with "feelings" but not data. Given that the proposal came from Jessica (a community member with significant relevant experience in outlining), and it was also recognized as interesting by Eric Christopher (a long-time member of the community with wide reaching expertise), I think dismissing it may have been a little premature.</div></div></blockquote><div><br></div></span><div>It isn't clear to me how much the *exact* pipeline and ordering of passes is relevant to consider if "having an outliner at the IR level" is a good idea.</div><span><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">I also want to visit a few procedural notes.</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">Mehdi commented on the thread that it wouldn't be fair to ask for a comparative study because the MIR outliner didn't have one. While I don't think anyone is asking for a comparative study, I want to point out that I think it is completely fair. </div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">If a new contributor approached the community with a new SROA pass and wanted to land it in-tree it would be appropriate to ask for a comparative analysis against the existing pass. How is this different? </div></div></blockquote><div><br></div></span><div>It seems quite different to me because there is no outliner at the IR level and so they don't provide the same functionality. The "Why at the IR level" section of the original email combined with the performance numbers seems largely enough to me to explain why it isn't redundant to the Machine-level outliner.<br></div><div>I'd consider this work for inclusion upstream purely on its technical merit at this point.</div><div>Discussing inclusion as part of any of the default pipeline is a different story.</div><div><br></div><div>Similarly last year, the IR-level PGO was also implemented even though we already had a PGO implementation, because 1) it provided a generic solutions for other frontend (just like here it could be said that it provides a generic solution for targets) and 2) it supported cases that FE-PGO didn't (especially around better counter-context using pre-inlining and such).</div><span><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">Adding a new IR outliner is a different situation from when the MIR one was added. When the MIR outliner was introduced there was no in-tree analog. </div></div></blockquote><div><br></div></span><div>We still usually discuss design extensively. Skipping the IR-level option didn't seem obvious to me, to say the least. And it wasn't really much discussed/considered extensively upstream.</div><div>If the idea is that implementing a concept at the machine level may preclude a future implementation at the IR level, it means we should be *a lot* more picky before accepting such contribution. </div><div>In this case, if I had anticipated any push-back on an IR-level implementation only based on the fact that we have now a Machine-level one, I'd likely have pushed back on the machine-level one.</div><span><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">When someone comes to the community with something that has no existing in-tree analog it isn't fair to necessarily ask them to implement it multiple different ways to prove their solution is the best. </div></div></blockquote><div><br></div></span><div>It may or may not be fair, but there is a tradeoff in how much effort we would require them to convince the community that this is *the* right way to go, depending on what it implies for future approaches.</div><span class="m_5561022771880780HOEnZb"><font color="#888888"><div><br></div><div>-- <br></div><div>Mehdi</div></font></span><div><div class="m_5561022771880780h5"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">However, as a community, we do still exercise the right to reject contributions we disagree with, and we frequently request changes to the implementation (as is shown every time someone tries to add SPIR-V support).</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)"><div style="margin:0px;line-height:normal">In the LLVM community we have a long history of approaching large contributions (especially ones from new contributors) with scrutiny and discussion. It would be a disservice to the project to forget that.</div></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69);min-height:14px">River, as a last note. I see that you've started uploading patches to Phabricator, and I know you're relatively new to the community. When uploading patches it helps to include appropriate reviewers so that the right people see the patches as they come in. To that end can you please include Jessica as a reviewer? Given her relevant domain experience I think her feedback on the patches will be very valuable.</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)"><br></div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">Thank you,</div><div style="margin:0px;line-height:normal;color:rgb(69,69,69)">-Chris</div><div><div class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707h5"><div style="margin:0px;line-height:normal;font-family:'Helvetica Neue';color:rgb(69,69,69)"><br></div><div><blockquote type="cite"><div>On Jul 26, 2017, at 1:52 PM, River Riddle via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396Apple-interchange-newline"><div><div dir="ltr" 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">Hey Sanjoy,<div> </div><div class="gmail_extra"><div class="gmail_quote">On Wed, Jul 26, 2017 at 1:41 PM, Sanjoy Das via llvm-dev<span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396Apple-converted-space"> </span><span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.<wbr>org</a>></span><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396Apple-converted-space"> </span>wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi,<br><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396gmail-"><br>On Wed, Jul 26, 2017 at 12:54 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>> wrote:<br>> The way I interpret Quentin's statement is something like:<br>><br>> - Inlining turns an interprocedural problem into an intraprocedural problem<br>> - Outlining turns an intraprocedural problem into an interprocedural problem<br>><br>> Insofar as our intraprocedural analyses and transformations are strictly<br>> more powerful than interprocedural, then there is a precise sense in which<br>> inlining exposes optimization opportunities while outlining does not.<br><br></span>While I think our intra-proc optimizations are *generally* more<br>powerful, I don't think they are *always* more powerful. For<br>instance, LICM (today) won't hoist full regions but it can hoist<br>single function calls. If we can extract out a region into a<br>readnone+nounwind function call then LICM will hoist it to the<br>preheader if the safety checks pass.<br><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396gmail-"><br>> Actually, for his internship last summer River wrote a profile-guided<br>> outliner / partial inliner (it didn't try to do deduplication; so it was<br>> more like PartialInliner.cpp). IIRC he found that LLVM's interprocedural<br>> analyses were so bad that there were pretty adverse effects from many of the<br>> outlining decisions. E.g. if you outline from the left side of a diamond,<br>> that side basically becomes a black box to most LLVM analyses and forces<br>> downstream dataflow meet points to give an overly conservative result, even<br>> though our standard intraprocedural analyses would have happily dug through<br>> the left side of the diamond if the code had not been outlined.<br>><br>> Also, River's patch (the one in this thread) does parameterized outlining.<br>> For example, two sequences containing stores can be outlined even if the<br>> corresponding stores have different pointers. The pointer to be loaded from<br>> is passed as a parameter to the outlined function. In that sense, the<br>> outlined function's behavior becomes a conservative approximation of both<br>> which in principle loses precision.<br><br></span>Can we outline only once we've already done all of these optimizations<br>that outlining would block?<br></blockquote><div> </div><div> The outliner is able to run at any point in the interprocedural pipeline. There are currently two locations: Early outlining(pre inliner) and late outlining(practically the last pass to run). It is configured to run either Early+Late, or just Late. </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396gmail-"><br>> I like your EarlyCSE example and it is interesting that combined with<br>> functionattrs it can make a "cheap" pass get a transformation that an<br>> "expensive" pass would otherwise be needed. Are there any cases where we<br>> only have the "cheap" pass and thus the outlining would be essential for our<br>> optimization pipeline to get the optimization right?<br>><br>> The case that comes to mind for me is cases where we have some cutoff of<br>> search depth. Reducing a sequence to a single call (+ functionattr<br>> inference) can essentially summarize the sequence and effectively increase<br>> search depth, which might give more results. That seems like a bit of a weak<br>> example though.<br><br></span>I don't know if River's patch outlines entire control flow regions at<br>a time, but if it does then we could use cheap basic block scanning<br>analyses for things that would normally require CFG-level analysis.<br></blockquote><div><br></div><div> The current patch currently just supports outlining from within a single block. Although, I had a working prototype for Region based outlining, I kept it from this patch for simplicity. So its entirely possible to add that kind of functionality because I've already tried.</div><div>Thanks,</div><div> River Riddle</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><br>-- Sanjoy<br><div class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396gmail-HOEnZb"><div class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396gmail-h5"><br>><br>> -- Sean Silva<br>><br>> On Wed, Jul 26, 2017 at 12:07 PM, Sanjoy Das via llvm-dev<br>> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>>><br>>> Hi,<br>>><br>>> On Wed, Jul 26, 2017 at 10:10 AM, Quentin Colombet via llvm-dev<br>>> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>>> > No, I mean in terms of enabling other optimizations in the pipeline like<br>>> > vectorizer. Outliner does not expose any of that.<br>>><br>>> I have not made a lot of effort to understand the full discussion here (so<br>>> what<br>>> I say below may be off-base), but I think there are some cases where<br>>> outlining<br>>> (especially working with function-attrs) can make optimization easier.<br>>><br>>> It can help transforms that duplicate code (like loop unrolling and<br>>> inlining) be<br>>> more profitable -- I'm thinking of cases where unrolling/inlining would<br>>> have to<br>>> duplicate a lot of code, but after outlining would require duplicating<br>>> only a<br>>> few call instructions.<br>>><br>>><br>>> It can help EarlyCSE do things that require GVN today:<br>>><br>>> void foo() {<br>>> ... complex computation that computes func()<br>>> ... complex computation that computes func()<br>>> }<br>>><br>>> outlining=><br>>><br>>> int func() { ... }<br>>><br>>> void foo() {<br>>> int x = func();<br>>> int y = func();<br>>> }<br>>><br>>> functionattrs=><br>>><br>>> int func() readonly { ... }<br>>><br>>> void foo(int a, int b) {<br>>> int x = func();<br>>> int y = func();<br>>> }<br>>><br>>> earlycse=><br>>><br>>> int func(int t) readnone { ... }<br>>><br>>> void foo(int a, int b) {<br>>> int x = func(a);<br>>> int y = x;<br>>> }<br>>><br>>> GVN will catch this, but EarlyCSE is (at least supposed to be!) cheaper.<br>>><br>>><br>>> Once we have an analysis that can prove that certain functions can't trap,<br>>> outlining can allow LICM etc. to speculate entire outlined regions out of<br>>> loops.<br>>><br>>><br>>> Generally, I think outlining exposes information that certain regions of<br>>> the<br>>> program are doing identical things. We should expect to get some mileage<br>>> out of<br>>> this information.<br>>><br>>> -- Sanjoy<br>>> ______________________________<wbr>_________________<br>>> LLVM Developers mailing list<br>>><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>>><span class="m_5561022771880780m_-3618795496910343616gmail-m_1730094247147270707m_4656533488542751396Apple-converted-space"> </span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-b<wbr>in/mailman/listinfo/llvm-dev</a><br>><br>><br>______________________________<wbr>_________________<br>LLVM Developers mailing list<br><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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></div></div></blockquote></div><br></div></div><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;float:none;display:inline">______________________________<wbr>_________________</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"><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;float:none;display:inline">LLVM Developers mailing list</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"><a href="mailto:llvm-dev@lists.llvm.org" 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" target="_blank">llvm-dev@lists.llvm.org</a><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"><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" 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" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a></div></blockquote></div><br></div></div></div><br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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></div></div><br></div></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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></blockquote></div><br></div>