<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Dec 18, 2016 at 12:38 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@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 class="h5"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Dec 17, 2016 at 8:39 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><div class="gmail_extra"><div class="gmail_quote"><span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div class="m_6727250221666874238m_-2072195203290018287h5"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br></blockquote><div><br></div></div></div><div>LVI is one of those analyses with quadratic runtime, but has a cutoff to its search depth so that it is technically not quadratic. So increased inlining could easily exacerbate it more than non-"quadratic" passes. (increased inlining would also cause a general slowdown too).</div><div><br></div></div></div></div></blockquote><div><br></div></span><div>LVI is only quadratic because of the way we've built it (it's actually worse than quadratic,but let's just normalize to "quadratic").</div><div>Non-lazy versions are not quadratic, and you could likely build an incremental lazy version that is also not quadratic in practice.<br></div><div>At some point, none of this will change unless people hold the line somewhere. Compilers usually get slower 0.1% at a time, not in huge leaps and bounds.</div><div>Without people saying "If we really want to get this case, in a thing not really designed to get that case sanely, we need to stop and think about it", it doesn't get thought about.</div><div><br></div><div>Obviously, you can go too far into that extreme, but i think we are still too far on one side of that one (at least, in most places in LLVM)<br></div></div></div></div>
</blockquote></div><br></div></div></div><div class="gmail_extra">Good point. One thing that struck me when randomly browsing the GCC source code is that GCC seems to use far more sophisticated algorithms (e.g. lots of files with comments at the top citing different papers and things; not that counting citations means that much, but it's a rough proxy for keeping up with the literature). WIth LLVM, it seems like most of the stuff is homegrown or at least not frequently revisited with an eye to using an new algorithm. And once something starts picking up a bunch of special cases and things, it becomes harder and harder to replace with a new better thing, because nobody will want to throw the old thing away until the new thing covers the same set of test cases.</div></div></blockquote><div><br></div><div>This is precisely what happened with GVN, for example (and happens with other things, like InstCombine, like LVI, like BasicAA, ...).   All of these things started by serving a purpose and with some useful design lifetime.  They made sense for those things.  People push them past their useful design lifetime and original purposes, but they don't get redesigned or rethought.  Pretty soon, you have a mess that is very hard to clean up for the reason you stated (in practice, you may have to split analysis or passes, and accept that you can't and shouldn't try to catch absolutely everything in every single pass).</div><div><br></div><div>Thankfully, a number of companies/people in our community can get the time to spend on "technical debt" instead of just improving performance, but it's, IMHO, still overloaded a little too much on the performance at any cost side.</div><div>It happens with all compilers, of course, it's not specific to LLVM.</div><div><br></div><div>As for why GCC tends to use more literature, again IMHO:</div><div>GCC has more areas than LLVM with specific code owners, which has the upside that someone is ostensibly thinking about these things and has some thought where that area should go.   They can provide explicit guidance, at at least make sure something is going in the right direction.   The downside, of course, is that it comes with a bit of bureaucracy (though, IMHO, LLVM has this in practice, it's just hidden more)., and sometimes a little less innovation (again, varies)   It also means people have to not view it as an honorific, and when they move on or change or stop caring or what have you, that the area gets reassigned to someone else.  The other downside is that it often involves saying "no, let's not do that, let's do this instead" a lot, and that makes people feel bad when they know someone else is just trying to achieve a task someone assigned them.</div><div><br></div><div>The only thing any of these approaches change, in the end, is the useful lifetime of the end result.  It doesn't mean you end up with a thing that is perfect, but you may get a thing that works well for 10 years instead of 5.  Whether that is the right tradeoff for what you are doing, also varies wildly (it probably makes no sense to spend 6 months designing a thing that is only meant to last 6 months).</div><div><br></div><div>Also, this isn't, of course, to say that homegrown is necessarily bad.   But doing it well at least requires having read and understood enough theory to understand how to grow your own thing well, or be for a thing small enough it just doesn't matter :)</div><div>Personally, I learned compilers and optimization in an environment surrounded by people who had pretty much done everything we are trying to do before, and so i always learned to go hunting to see what the state of the art was, and the theories behind it, before i tried to roll my own.  That didn't always make the state of the art good, sane, or even implementable, mind you, but it meant it at least got thought about, and often, even when the papers were crazy, they had ideas or approaches you could reuse. <br></div><div><br></div><div>--Dan</div></div></div></div>