Performance regression in AA

[dotdash]

Bugzilla Link	26564
Version	3.8
OS	Linux
CC	@chandlerc,@gburgessiv,@zmodem,@hfinkel

Extended Description

Since upgrading to a more recent LLVM version for the Rust compiler, there has been a large increase in compile time spent in LLVM optimizations. The corresponding Rust bug report can be found here: rust-lang/rust#31435

At least part of that seems to come from the new AA handling, which exhibits O(n^2) behavior in some cases with n being the number of active AA passes.

This originates from using the AAResultProxy in the AAResultBase class. For example, calling AAResults::getModRefBehavior(CallSite) will iterate over all registered AA results which all may eventually call into AAResultBase::getModRefBehavior(CallSite) which calls AAResultProxy::getModRefBehavior(Function*) which will then iterate over all registered passes again.

[chandlerc]

It would be useful to understand how this manifests as a significant problem. While it is technically quadratic, there is a fixed (and at least usually very small) upper bound. It would be interesting to know what pattern caused this to be a significant performance regression.

[chandlerc]

Looking at this more, it's a pretty terrible pattern we ended up with in AA. I've made an attempt to fix it in http://reviews.llvm.org/D17329 -- it would be really useful to know if that patch addresses the problem you're hitting as there doesn't seem to be a standalone reproducer here.

Also, Hans, this may be worth pulling into 3.8 if possible.

[zmodem]

Also, Hans, this may be worth pulling into 3.8 if possible.

I'm not a big fan of taking big changes this late. I had hoped to tag rc3 by end of day, which could potentially be the final release candidate.

A patch like this I'd like to see bake in tree for at least a day before merging. On the other hand it seems like a bad regression, so maybe it's worth waiting for. I'll follow the review.

[dotdash]

Nice! I've applied the patch from D17329 along with r260183 and r260836 (to ease conflict resolution) to Rust's LLVM fork, which is currently the 3.8 release branch at r260704 plus some minor patches.

That reduces the time spent in the module passes by about 10% for the testcase given in the Rust bugreport. That's not quite back to the old level of time spent there, but I'm not sure whether the remaining 10% can be attributed to this bug. I'll try to spend some time looking at profiles to see whether I can find more details.

[chandlerc]

It would be incredibly useful to attach some bitcode to this bug and suggest an 'opt ...' commandline to run over that bitcode that would reproduce the slowdown you're seeing.

[dotdash]

The one I used for the AA slowdown is 17MB (6MB bzipped), another one that shows a slowdown that seems to come from a different source is 1.7MB (582K bzipped). Are those ok as an attachment or should I try to find something smaller?

[chandlerc]

Nah, those should be fine. The bigger the better in some senses (easier to profile). If you can't attach it, toss it on github somewhere?

[dotdash]

I've pushed the files to https://github.com/dotdash/llvm-testcase

I've just used opt -O2 -o /dev/null to observe the slowdown.

The syntax.0.no-opt.bc file exhibits both, the AA slowdown as well as something else, the core.0.no-opt.bc file also takes longer with the new LLVM version, but I don't know why, yet. Looks like computeKnownBits takes a bit more time, but not enough to account for it all.

For syntax.0.no-opt.bc I get:
release_37 r247539: ~50s
release_38 r259207: ~64s
release_38 r259207 + backport: ~56s

For core.0.no-opt.bc I get:
release_37 r247539: ~2.2s
release_38 r259207: ~2.7s
release_38 r259207 + backport: ~2.7sIf I can provide

[chandlerc]

The patch to remove quadratic behavior is in r262490, but still looking at other slowdown causes.