[llvm-dev] [RFC] Simple GVN hoist

Thu Nov 11 15:49:56 PST 2021

On Thu, Nov 11, 2021 at 9:02 AM Momchil Velikov via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> [back to the mailing list, for more(?) exposure]
>
> From: Alina Sbirlea <asbirlea at google.com>
> > I added a note about this in https://reviews.llvm.org/D110822.
>
> > So, stepping back, I'd like to raise the question of how this change is
> going to be used if implemented.
> > In the current default pipeline MemorySSA is not available where GVN is
> added. This is forcing the
> > computation of MemorySSA before GVN.
>
> > Having MemorySSA computed before GVN may be good in the LTO pipeline
> (GVN already preserves the
> > analysis), as the following passes require it (MemCpyOpt and DSE), but
> in the function simplification pipeline
> > we'd end up with GVN computing, using and preserving two analysis
> (MemorySSA and MemDepAnalysis) with
> > overlapping goals.
>
> > The status for switching to NewGVN is uncertain at this point, but
> porting GVN to switch over from
> > MemDepAnalysis to MemorySSA may be an option, at least in the interim.
> This will lift the issue of having two
> > analysis and also provide the availability of MemorySSA here.
>
> > Is this something you'd be interested in exploring?
>
> It is possible. We (the Arm team working on these things) would like to
> have a reasonable idea[1]
> of a couple of things.
>
> First, will this get us anywhere? Does anyone can think of any other
> objections
> (provided, of course, the patch is of sufficient quality) against merging
> this and enabling it by default, including
> computing MemorySSA?
>

>From my side the only objection would be if the implementation regressess
either compile or run times severely.

My team's focus is on improving the infrastructure in LLVM without
negatively impacting performance. One of the top priorities at the moment
is removing the usages of MemDepAnalysis - GVN is the last of these. I've
been looking into fixing NewGVN in order to get it to a stage of being
viable to replace the current GVN. At this point, there are still
correctness issues to resolve, and even with those addressed it will not
reach parity with GVN due to NewGVN not doing PRE.

Given all this and your involvement in adding GVNHoist to the current GVN,
it seems worth considering whether investment into the current GVN makes
more sense at this time.
It's still possible that NewGVN would give better optimizations and/or
compile times, but if GVN were to only rely on MemorySSA for its decisions,
then we'd be enabling that by default first. Computing MemorySSA will not
be an issue for adding GVN Hoist then, since it would always be available.
Again, my only objection to adding GVN Hoist then is providing a reasonable
balance on what are the gains when adding the new optimization vs the
compile time incurred.

> AFAIK, GVNHoist was disabled due to some benchmark regressions,
> unfortunately I wasn't able to find a trace about
> this decision, does anyone know anything more about it? Would anyone
> interested be able to apply
> https://reviews.llvm.org/D111418 (5 patches) and check and see if there
> are unacceptable regressions,
> that we can try to resolve?
>

Could you run these through the compiler-tracker
<https://llvm-compile-time-tracker.com/index.php> as an initial testing
stage? (+nikic for support here)
(I expect a higher increase in compile time due to computing MSSA that
would be mitigated if GVN is first switched to only use MemorySSA)

Second, what are we getting into, if we decide to migrate GVN.cpp to
> MemorySSA? Would that be
> a couple of weeks or a multi-year project? Has anyone already thought
> about approaches to doing that?

I'd estimate a few months of on and off work (or less than a couple of
months if more dedicated work). The DSE transition was a similar process;
looking at patch history, from the first patch variant to the flag being
flipped there were ~7 months (+fhahn for additional feedback here).

> I spent maybe a total of three days looking at
> GVN/MemorySSA/MemoryDependenceAnalysis
> and the transition does not look straightforward or obvious, more like
> re-implementing (parts of)
> MemoryDependenceAnalysis. I mean, it looks doable and not *that* much
> work, but more likely than not
> I'm overlooking something.
>
> For example, looking at the dependencies of loads (if I'm not mistaken
> that's the only kind relevant to GVN)
> the MemoryDependencyAnalysis would return other loads as "dependencies",
> depending on aliasing,
> and also `alloca`s. This does not have a direct equivalent in MemorySSA.
> I'm thinking of something along
> the lines of: get the clobbering def for a load, get all its uses, from
> this list, remove uses, post-dominated
> by other uses (as long as the post-dominating one is not a MayAlias), and
> somehow do this
> in an efficient manner - that'll hopefully get the same set of
> dependencies (local or not) as the ones obtained from
> the MemoryDependencyAnalysis, continue from there as before.
>

That's the general idea, yes. Similar traversals were added in DSE, and it
may make sense to reuse (potentially factor out) some of those.

I don't think you're overlooking anything. We just didn't focus on this
until now because the general agreement has been we'd move over to NewGVN
instead (vs for DSE there wasn't another pass using MemorySSA and doing the
same kind of transformation).

>
> Any other ideas?
>
> ~chill
>
> [1] by no means a guarantee, we're just looking to asses the risks going
> one or another way
>

Understood and it makes sense! Hope I've clarified some of your questions.

Best,
Alina

_______________________________________________
> 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/20211111/5834bf81/attachment.html>