<div dir="ltr"><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 class=""><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_-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 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 class="gmail_extra"><br></div><div class="gmail_extra">-- Sean Silva  </div></div>