Page MenuHomePhabricator

[GVN] Preserve MemorySSA if it is available.
ClosedPublic

Authored by fhahn on Aug 25 2020, 5:56 AM.

Details

Summary

Preserve MemorySSA if it is available before running GVN.

DSE with MemorySSA will run closely after GVN. If GVN and 2 other
passes preserve MemorySSA, DSE can re-use MemorySSA used by LICM
when doing LTO.

Diff Detail

Event Timeline

fhahn created this revision.Aug 25 2020, 5:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2020, 5:56 AM
fhahn requested review of this revision.Aug 25 2020, 5:56 AM
fhahn updated this revision to Diff 288079.Aug 26 2020, 12:28 PM

Use createMemoryAccessAfter with the appropriate defining access.

Not exactly the path I had in mind (working on newGVN was), but that's a longer avenue and I'm curious to see the compile-time impact of preserving MSSA :-)

llvm/lib/Transforms/Scalar/GVN.cpp
1346

I don't think this is right. Def can be a MemoryUse and that should not be a defining access.
I *think* it should take
MemoryAccess *Def2=isa<MemoryUse>(Def)? Def->getDefiningAccess():Def;
(with some proper var renaming)

This also shows MSSA should have an assert checking for this internally, I'll have to add that.

Please also add a MSSA verification at the end of the pass

if (MSSA && VerifyMemorySSA)
   MSSA->verifyMemorySSA();
2240

Optional or std::unique_ptr?
Previous cases used unique ptr, with MSSAU.get() passed as argument below.

fhahn updated this revision to Diff 288705.Aug 28 2020, 2:22 PM

Fix MemorySSA update for PRE loads. They are inserted just before the terminator, so we can just use createAccessInBB with BeforeTerminator position and the defining access of the original load.

Not exactly the path I had in mind (working on newGVN was), but that's a longer avenue and I'm curious to see the compile-time impact of preserving MSSA :-)

Ideally NewGVN would be ready, but unfortunately there are still a few bigger issues. I intend to pick this back up after wrapping up a few other things.

Preserving MemorySSA is crucial to stay compile-time competitive with LTO, geomean ReleaseLTO -0.58%, ReleaseLTO (link only) -1.24%

http://llvm-compile-time-tracker.com/compare.php?from=d24856f1e0485c1a619528359e3cfd3dc8d15857&to=062412e79fcfedf2cf004433e42036b0333e3f83&stat=instructions

fhahn added a comment.EditedAug 28 2020, 2:26 PM
This comment has been deleted.
llvm/lib/Transforms/Scalar/GVN.cpp
1346

yes this was not entirely right. I think we can simply use createMemoryAccessInBB, as we insert just before the terminator. LI is always a MemoryUse, so the defining access of the the new load should be just the defining access of the original load.

This seems to work fine with building SPEC2000/SPEC2006/MultiSource with expensive MemSSA verification.

2240

Are you suggesting to use a unique_ptr in runImpl to manage a dynamically allocated updater in runImpl? I am not sure if that would be a big advantage, as constructing the Updater unconditionally on the stack should be quite cheap and we don't have to worry about dynamic allocations.

asbirlea added inline comments.Aug 28 2020, 5:12 PM
llvm/lib/Transforms/Scalar/GVN.cpp
1346

Regarding the comment: "Get the defining access of the original load. The inserted loads are guaranteed to load from the same definition."

I thought about this when adding the comment, and I was going to suggest exactly this. But, thinking further, I don't think setting the defining access as LI's defining access is always correct.
Assume MSSA is further used, then the defining access used here may decide further optimizations. For example, it may say that it's ok to hoist NewLoad above LI, even though LI may be volatile and a MemoryDef in the MSSA representation.

Come to think about it, if LI is volatile, so will NewLoad, so this should check NewLoad's access and use insertDef if that's the case, because accesses further down will need updating then.

If LI is always removed (NewLoad is a replacement), and it's always a use, then it's correct to use LI's defining access. But I don't understand GVN's innards enough at this point to make this assessment.

2240

Sure, that works.

2300

Remove braces.

llvm/test/Transforms/GVN/preserve-memoryssa.ll
4

; REQUIRES: asserts

fhahn updated this revision to Diff 288950.Aug 31 2020, 8:12 AM

Also handle the case that LI could be a MemoryDef.

fhahn marked 2 inline comments as done.Aug 31 2020, 8:17 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/GVN.cpp
1346

Come to think about it, if LI is volatile, so will NewLoad, so this should check NewLoad's access and use insertDef if that's the case, because accesses further down will need updating then.

Oh right, I did not consider that LI could actually be a MemoryDef itself (e.g. volatile load)! I adjusted the code, to use the MemoryAcc for LI directly if it is a def and the defining access otherwise. I also updated the code to use insertDef, if the new access is actually a MemoryDef. I don't think GVN currently does load PRE for volatile loads, but it is probably better to handle all possible cases here. I updated the comment as well.

If LI is always removed (NewLoad is a replacement), and it's always a use, then it's correct to use LI's defining access. But I don't understand GVN's innards enough at this point to make this assessment.

I am not sure myself if it is removed in all cases, but it is probably better to be conservative. If the load gets removed, the memory access gets also removed and the the updating mechanism should take care of that.

fhahn updated this revision to Diff 288951.Aug 31 2020, 8:20 AM

Handle case when the new load is a memorydef.

fhahn updated this revision to Diff 289561.Sep 2 2020, 1:58 PM

Add MemorySSA to preserved set for NPM too.

asbirlea accepted this revision.Sep 2 2020, 6:55 PM

Changes look good.
Please also test with EXPENSIVE_CHECKS. The additional MSSA verifications there can unearth missed changes.

This revision is now accepted and ready to land.Sep 2 2020, 6:55 PM
fhahn added a comment.Sep 3 2020, 4:27 AM

Changes look good.
Please also test with EXPENSIVE_CHECKS. The additional MSSA verifications there can unearth missed changes.

Thanks, I did a bootstrap build of LLVM with expensive MemorySSA verification and the test-suite with the set of patches to preserve MemSSA. The tests here and D86651 are from problems surfaced through that testing :)

This revision was landed with ongoing or failed builds.Sep 3 2020, 4:29 AM
This revision was automatically updated to reflect the committed changes.
uabelho added a subscriber: uabelho.Sep 4 2020, 3:44 AM

Hi!

The following crashes for me with this patch
opt -memoryssa -gvn -early-cse-memssa -S -o - foo.ll

with foo.ll being just

define void @f() {
entry:
  unreachable
}

I get

opt: ../lib/IR/LegacyPassManager.cpp:657: void llvm::PMTopLevelManager::setLastUser(ArrayRef<llvm::Pass *>, llvm::Pass *): Assertion `AnalysisPass && "Expected analysis pass to exist."' failed.
fhahn added a comment.Sep 4 2020, 5:02 AM

Hi!

The following crashes for me with this patch
opt -memoryssa -gvn -early-cse-memssa -S -o - foo.ll

with foo.ll being just

define void @f() {
entry:
  unreachable
}

I get

opt: ../lib/IR/LegacyPassManager.cpp:657: void llvm::PMTopLevelManager::setLastUser(ArrayRef<llvm::Pass *>, llvm::Pass *): Assertion `AnalysisPass && "Expected analysis pass to exist."' failed.

Thanks for the report. Looks like there is a problem with MemorySSAWrapperPass depending on AAResultsWrapperPass, which is not explicitly preserved by GVN. The problem can be solved by explicitly requiring AAResultsWrapperPass in EarlyCSE or by preserved AAResultsWrapper pass in GVN. I put up a patch for review/discussion for the best place to fix: D87137