[llvm-dev] [RFC] Simple GVN hoist

[Momchil Velikov via llvm-dev]

[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?
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?

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 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.

Any other ideas?

~chill

[1] by no means a guarantee, we're just looking to asses the risks going one or another way