[llvm-dev] llvm (the middle-end) is getting slower, December edition

[Sean Silva via llvm-dev]

On Sat, Dec 17, 2016 at 8:39 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

>
>>>
>> 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).
>>
>>
> 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").
> Non-lazy versions are not quadratic, and you could likely build an
> incremental lazy version that is also not quadratic in practice.
> 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.
> 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.
>
> 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)
>

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.

-- Sean Silva
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161218/3f93a75e/attachment.html>