<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Nov 11, 2021 at 9:02 AM Momchil Velikov via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">[back to the mailing list, for more(?) exposure]<br>
<br>
From: Alina Sbirlea <<a href="mailto:asbirlea@google.com" target="_blank">asbirlea@google.com</a>><br>
> I added a note about this in <a href="https://reviews.llvm.org/D110822" rel="noreferrer" target="_blank">https://reviews.llvm.org/D110822</a>.<br>
<br>
> So, stepping back, I'd like to raise the question of how this change is going to be used if implemented.<br>
> In the current default pipeline MemorySSA is not available where GVN is added. This is forcing the<br>
> computation of MemorySSA before GVN.<br>
<br>
> Having MemorySSA computed before GVN may be good in the LTO pipeline (GVN already preserves the<br>
> analysis), as the following passes require it (MemCpyOpt and DSE), but in the function simplification pipeline<br>
> we'd end up with GVN computing, using and preserving two analysis (MemorySSA and MemDepAnalysis) with<br>
> overlapping goals.<br>
<br>
> The status for switching to NewGVN is uncertain at this point, but porting GVN to switch over from<br>
> MemDepAnalysis to MemorySSA may be an option, at least in the interim. This will lift the issue of having two<br>
> analysis and also provide the availability of MemorySSA here.<br>
<br>
> Is this something you'd be interested in exploring?<br>
<br>
It is possible. We (the Arm team working on these things) would like to have a reasonable idea[1] <br>
of a couple of things.<br>
<br>
First, will this get us anywhere? Does anyone can think of any other objections<br>
(provided, of course, the patch is of sufficient quality) against merging this and enabling it by default, including<br>
computing MemorySSA?<br></blockquote><div><br></div><div>From my side the only objection would be if the implementation regressess either compile or run times severely.</div><div><br></div><div>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.</div><div><br></div><div>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. </div><div>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.</div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
AFAIK, GVNHoist was disabled due to some benchmark regressions, unfortunately I wasn't able to find a trace about<br>
this decision, does anyone know anything more about it? Would anyone interested be able to apply<br>
<a href="https://reviews.llvm.org/D111418" rel="noreferrer" target="_blank">https://reviews.llvm.org/D111418</a> (5 patches) and check and see if there are unacceptable regressions,<br>
that we can try to resolve?<br></blockquote><div><br></div><div>Could you run these through the <a href="https://llvm-compile-time-tracker.com/index.php">compiler-tracker</a> as an initial testing stage? (+nikic for support here)</div><div>(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)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Second, what are we getting into, if we decide to migrate GVN.cpp to MemorySSA? Would that be<br>
a couple of weeks or a multi-year project? Has anyone already thought about approaches to doing that? </blockquote><div><br></div><div>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).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
I spent maybe a total of three days looking at GVN/MemorySSA/MemoryDependenceAnalysis<br>
and the transition does not look straightforward or obvious, more like re-implementing (parts of)<br>
MemoryDependenceAnalysis. I mean, it looks doable and not *that* much work, but more likely than not<br>
I'm overlooking something.<br>
<br>
For example, looking at the dependencies of loads (if I'm not mistaken that's the only kind relevant to GVN)<br>
the MemoryDependencyAnalysis would return other loads as "dependencies", depending on aliasing,<br>
and also `alloca`s. This does not have a direct equivalent in MemorySSA. I'm thinking of something along<br>
the lines of: get the clobbering def for a load, get all its uses, from this list, remove uses, post-dominated<br>
by other uses (as long as the post-dominating one is not a MayAlias), and somehow do this<br>
in an efficient manner - that'll hopefully get the same set of dependencies (local or not) as the ones obtained from<br>
the MemoryDependencyAnalysis, continue from there as before.<br></blockquote><div><br></div><div>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.</div><div><br></div><div>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). </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Any other ideas?<br>
<br>
~chill<br>
<br>
[1] by no means a guarantee, we're just looking to asses the risks going one or another way<br></blockquote><div><br></div><div>Understood and it makes sense! Hope I've clarified some of your questions.</div><div><br></div><div>Best,</div><div>Alina</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div>