This is an archive of the discontinued LLVM Phabricator instance.

[MemCpyOpt] Preserve MemorySSA.
ClosedPublic

Authored by fhahn on Aug 26 2020, 12:23 PM.

Details

Summary

This patch updates MemCpyOpt to preserve MemorySSA. It uses the
MemoryDef at the insertion point of the builder and inserts the new def
after that def.

In some cases, we just modify a memory instruction. In that case, get
the defining access, then remove the memory access and add a new one.
If the defining access is in a different block, insert a new def at the
beginning of the current block, otherwise after the defining access.

Diff Detail

Event Timeline

fhahn created this revision.Aug 26 2020, 12:23 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 26 2020, 12:23 PM
fhahn requested review of this revision.Aug 26 2020, 12:23 PM
fhahn updated this revision to Diff 288764.Aug 29 2020, 1:05 AM

Fix some bugs in the updating, add test cases.

There is one case where we turn a memmove into a memcpy, which currently is a no-op. We should probably remove the access and re-add it, but I am not sure how to best ensure we re-add the access at the correct position.

I was working on having MemCpyOpt preserve and use MSSA, in order to replace the use of MemDepAnalysis entirely. But I'm happy with having MSSA preserved first :-).

Some quick comments below.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
421

assert (LastDef && "Must exist.");

431

Remove braces.

llvm/test/Transforms/MemCpyOpt/perserve-memssa.ll
1

Typo in file name, rename file to preserve-memssa.

3

;REQUIRES: asserts

fhahn updated this revision to Diff 289394.Sep 2 2020, 4:38 AM

I was working on having MemCpyOpt preserve and use MSSA, in order to replace the use of MemDepAnalysis entirely. But I'm happy with having MSSA preserved first :-).

I agree that MemCpyOpt is another good candidate the use MSSA and I think it should be possible to share some of the analysis/approach from DSE + MemorySSA to also remove the BB only limitation.

But preserving it is a relatively small step compared to that so we can take the initial step with DSE + MemorySSA :)

Some quick comments below.

Thanks, should be addressed!

fhahn marked 4 inline comments as done.Sep 2 2020, 4:39 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
421

Done, added an assert for both LastAcc and LastDef.

fhahn updated this revision to Diff 289549.Sep 2 2020, 12:59 PM
fhahn marked an inline comment as done.

Add MemorySSAAnalysis to preserved also for NPM.

A small note to test with EXPENSIVE_CHECKS as well, as there's extra verification there.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
323

I'm not sure I fully understand how these two work.
LastDef is the last definition, last access, or the defining access for the new MemoryAccess created below. It should be always updated in the loop. Should it also be updated when BI is not a store or memset but the access is a MemoryDef?
LastAcc is the insertion point (perhaps rename this one?)

The insertion point for the memset in the BB, seems to be where BI left off, so then LastAcc is either the same as LastDef or one before, so it should be updated more often than just for non-store and non-memset?

If my understanding is incomplete, could you please explain?

Unrelated, below, in Ranges, the StartInst is also added and I think that's a store. So LastAcc could be initialized to MSSAU->getMemorySSA()->getMemoryAccess(StartInstI); outside the loop?

1095

Can you add a comment explaining this?
The new memset is inserted after the memcpy, but it is known that its defining access is the memset about to be removed which immediately precedes the memcpy.

fhahn updated this revision to Diff 289744.Sep 3 2020, 9:14 AM

Add additional comments as suggested, thanks!

fhahn updated this revision to Diff 289747.Sep 3 2020, 9:30 AM

Further simplify LastMemDef, MemInsertPoint management.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
323

I'm not sure I fully understand how these two work.
LastDef is the last definition, last access, or the defining access for the new MemoryAccess created below. It should be always updated in the loop. Should it also be updated when BI is not a store or memset but the access is a MemoryDef?
LastAcc is the insertion point (perhaps rename this one?)

I renamed LastAcc to MemInsertPoint.

The insertion point for the memset in the BB, seems to be where BI left off, so then LastAcc is either the same as LastDef or one before, so it should be updated more often than just for non-store and non-memset?

Yes, MemInsertPoint (LastAcc) should be updated on each iteration. I updated the code. I also added comments explaining in more detail what both variables track. MemInsertPoint is either LastMemDef or the last memory user of before the insertion point for the new memsets.

Unrelated, below, in Ranges, the StartInst is also added and I think that's a store. So LastAcc could be initialized to MSSAU->getMemorySSA()->getMemoryAccess(StartInstI); outside the loop?

Yes I think it could be initialized with StartInstI, but it is set in each loop iteration now and should be much clearer, so I don't think it is necessary to additionally initialize it outside the loop

asbirlea accepted this revision.Sep 3 2020, 3:51 PM

Diff looks good to me.
Same comment as before about testing with EXPENSIVE_CHECKS to catch potential missed updates.
Thank you for working on this!

This revision is now accepted and ready to land.Sep 3 2020, 3:51 PM
This revision was landed with ongoing or failed builds.Sep 4 2020, 1:06 AM
This revision was automatically updated to reflect the committed changes.