llvm dev - Sep 2020 - [RFC] Switching to MemorySSA-backed Dead Store Elimination (aka cross-bb DSE)

Hi Florian,

First, thank you for working on this. I'm really glad to see this work so
close to being enabled.

I think the numbers look good for run time, and the benefits of switching
for all configurations are clear.

For compile time, the current regressions are noticeable, but not a deal
breaker in my opinion. I'm very much in favor of switching in all
configurations.

To address some of the concerns, it may make sense to lower the threshold
somewhat to minimize impact at this time (we won't have benefits as large
at the time of the switch). I'm talking about getting the geomean closer to
1% in all configurations if possible.
I believe that the regressions introduced by this flag flip can be undone
by further using MemorySSA in the other passes currently using
MemDepAnalysis, and offsetting the cost of computing MemorySSA in the first
place. The threshold could be raised again to enable more stores eliminated
once the MemCpyOpt+MSSA and NewGVN become the default.

If reducing the thresholds is not possible or removes most of the run time
benefits, I would vote for enabling as is.

Best,
Alina

On Wed, Aug 19, 2020 at 7:37 AM Florian Hahn via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> > On Aug 18, 2020, at 22:14, Florian Hahn via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> >
> >
> >> On Aug 18, 2020, at 16:59, Michael Kruse <llvmdev at
meinersbur.de> wrote:
> >>
> >> Thanks for all the work. The reductions in stores look promising.
Do
> you also have performance numbers how much this improves the execution
> time? Did you observe any regressions where MSSA resulted in fewer removed
> stores?
> >
> > I did not gather numbers for execution time yet, but I’ll try to share
> some tomorrow.
>
>
> Here are some execution time results for ARM64 with -O3 -flto with the
> MemorySSA-DSE compared against the current DSE implementation for CINT2006
> (negative % means reduction in execution time with MemorySSA-DSE). This
> excludes small changes within the noise (<= 0.5%)
>
>
> Exec_time  number of stores removed
>  test-suite...T2006/456.hmmer/456.hmmer.test   -1.6%.     + 70.8%
>  test-suite.../CINT2006/403.gcc/403.gcc.test       -1.4%.     + 35.7%
>  test-suite...0.perlbench/400.perlbench.test         -1.2%.     + 33.2%
>  test-suite...3.xalancbmk/483.xalancbmk.test      -1.0%.     + 3.02%
>  test-suite...T2006/401.bzip2/401.bzip2.test        -0.8%.     + 70.6%
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200819/4ef0ab83/attachment-0001.html>

Hi,

Thanks for all the responses!

My understanding is that there were no objections so far against trading a bit
of additional compile-time for more eliminated stores. Unless there are any new
concerns raised, I’ll continue working on submitting the remaining patches to
keep compile-time in check and flip the switch once they are in.

> On Aug 19, 2020, at 18:46, Alina Sbirlea <alina.sbirlea at gmail.com>
wrote:
> 
> Hi Florian,
> 
> First, thank you for working on this. I'm really glad to see this work
so close to being enabled.
> 
> I think the numbers look good for run time, and the benefits of switching
for all configurations are clear.
> 
> For compile time, the current regressions are noticeable, but not a deal
breaker in my opinion. I'm very much in favor of switching in all
configurations.
> 
> To address some of the concerns, it may make sense to lower the threshold
somewhat to minimize impact at this time (we won't have benefits as large at
the time of the switch). I'm talking about getting the geomean closer to 1%
in all configurations if possible.
> I believe that the regressions introduced by this flag flip can be undone
by further using MemorySSA in the other passes currently using MemDepAnalysis,
and offsetting the cost of computing MemorySSA in the first place. The threshold
could be raised again to enable more stores eliminated once the MemCpyOpt+MSSA
and NewGVN become the default.
> 
> If reducing the thresholds is not possible or removes most of the run time
benefits, I would vote for enabling as is.
I’ve been working on some additional changes to bring compile-time down a bit
further, while keeping the number of eliminated stores at a similar level.
Geomeans:
 -O3                       +0.62%
ReleaseThinLTO   +1.06%, 
ReleaseLTO-g      +0.79% Re
ReleaseThinLTO (link-only)  +0.96%
ReleaseLTO-G  (link only).   +0.80%

http://llvm-compile-time-tracker.com/compare.php?from=e19ef1aab524ef10a2d118adcd9f6fd6ca2d7ca9&to=c6812412983b4ebb20f1e32b83893284c8117e7f&stat=instructions

This also includes changes so DSE can re-use MemorySSA constructed by LICM
earlier during LTO. The limits could certainly be a bit tighter still, but I
hope they might encourage a few additional eyes on DSE + MemorySSA compile-time
wise, which would be great. Also, triggering as often as possible is probably
beneficial in terms of flushing out any remaining issues early.

Cheers,
Florian

Hi Florian,

Following up on D86967, I missed that all the timings were using the legacy
pass manager.
Did you do any testing on the compile and run time impact for the new pass
manager?

Thank you,
Alina


On Tue, Aug 25, 2020 at 12:51 PM Florian Hahn <florian_hahn at apple.com>
wrote:
> Hi,
>
> Thanks for all the responses!
>
> My understanding is that there were no objections so far against trading a
> bit of additional compile-time for more eliminated stores. Unless there are
> any new concerns raised, I’ll continue working on submitting the remaining
> patches to keep compile-time in check and flip the switch once they are in.
>
>
> > On Aug 19, 2020, at 18:46, Alina Sbirlea <alina.sbirlea at
gmail.com>
> wrote:
> >
> > Hi Florian,
> >
> > First, thank you for working on this. I'm really glad to see this
work
> so close to being enabled.
> >
> > I think the numbers look good for run time, and the benefits of
> switching for all configurations are clear.
> >
> > For compile time, the current regressions are noticeable, but not a
deal
> breaker in my opinion. I'm very much in favor of switching in all
> configurations.
> >
> > To address some of the concerns, it may make sense to lower the
> threshold somewhat to minimize impact at this time (we won't have
benefits
> as large at the time of the switch). I'm talking about getting the
geomean
> closer to 1% in all configurations if possible.
> > I believe that the regressions introduced by this flag flip can be
> undone by further using MemorySSA in the other passes currently using
> MemDepAnalysis, and offsetting the cost of computing MemorySSA in the first
> place. The threshold could be raised again to enable more stores eliminated
> once the MemCpyOpt+MSSA and NewGVN become the default.
> >
> > If reducing the thresholds is not possible or removes most of the run
> time benefits, I would vote for enabling as is.
>
> I’ve been working on some additional changes to bring compile-time down a
> bit further, while keeping the number of eliminated stores at a similar
> level. Geomeans:
>  -O3                       +0.62%
> ReleaseThinLTO   +1.06%,
> ReleaseLTO-g      +0.79% Re
> ReleaseThinLTO (link-only)  +0.96%
> ReleaseLTO-G  (link only).   +0.80%
>
>
>
http://llvm-compile-time-tracker.com/compare.php?from=e19ef1aab524ef10a2d118adcd9f6fd6ca2d7ca9&to=c6812412983b4ebb20f1e32b83893284c8117e7f&stat=instructions
>
> This also includes changes so DSE can re-use MemorySSA constructed by LICM
> earlier during LTO. The limits could certainly be a bit tighter still, but
> I hope they might encourage a few additional eyes on DSE + MemorySSA
> compile-time wise, which would be great. Also, triggering as often as
> possible is probably beneficial in terms of flushing out any remaining
> issues early.
>
> Cheers,
> Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200901/5d5cd53c/attachment.html>