llvm dev - Mar 2020 - large slowdown in DAGCombiner::MergeConsecutiveStores

Hello all,

We are seeing a large compiler performance regression in moving from LLVM
6.0.1 to 8.0.1. We have a long function (~50000 instructions) that used to
compile in about a minute but now takes at least an hour. All the time is
in MergeConsecutiveStores, I believe due to super-linear behavior in
analyzing very long chains of stores. For example, this change makes the
problem go away:

```
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -16011,6 +16011,9 @@ bool
DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
                        StoreNodes.begin() + NumConsecutiveStores);
       continue;
     }
+    else if (NumConsecutiveStores > 128) {
+      return RV;
+    }
```

Does anybody have any advice on what a good way to fix this would be? Does
it make sense to have some kind of limit on how many stores we try to
merge? (Even if so, I don't know whether the above is the right way to
implement such a limit.)

Thanks in advance for any suggestions.

-Jeff
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200319/5f12abd4/attachment.html>

Hi,
> On Mar 19, 2020, at 20:29, Jeff Bezanson via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hello all,
> 
> We are seeing a large compiler performance regression in moving from LLVM
6.0.1 to 8.0.1. We have a long function (~50000 instructions) that used to
compile in about a minute but now takes at least an hour. All the time is in
MergeConsecutiveStores, I believe due to super-linear behavior in analyzing very
long chains of stores. For example, this change makes the problem go away:
> 
Are you seeing the same performance regression on master? 

Over the last year, at least 2 patches landed to improve compile time in similar
cases: https://reviews.llvm.org/D62633 https://reviews.llvm.org/D65174

Cheers
Florian

Thanks for those references. I tried this with a ~1 week old master and
indeed the situation is much better. It's now about 2x slower than 6.0.1.
The extra time is still in MergeConsecutiveStores. Do you think there's any
scope for further limiting the work done there? The performance is now at
least tolerable though.

Many thanks to everyone who has looked into these issues; this makes a big
difference for some interesting Julia use cases.

-Jeff


On Thu, Mar 19, 2020 at 4:37 PM Florian Hahn <florian_hahn at apple.com>
wrote:
> Hi,
>
> > On Mar 19, 2020, at 20:29, Jeff Bezanson via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Hello all,
> >
> > We are seeing a large compiler performance regression in moving from
> LLVM 6.0.1 to 8.0.1. We have a long function (~50000 instructions) that
> used to compile in about a minute but now takes at least an hour. All the
> time is in MergeConsecutiveStores, I believe due to super-linear behavior
> in analyzing very long chains of stores. For example, this change makes the
> problem go away:
> >
>
> Are you seeing the same performance regression on master?
>
> Over the last year, at least 2 patches landed to improve compile time in
> similar cases: https://reviews.llvm.org/D62633
> https://reviews.llvm.org/D65174
>
> Cheers
> Florian
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200320/295d97da/attachment.html>