This is an archive of the discontinued LLVM Phabricator instance.

[MemorySSA] Teach LoopSimplify to preserve MemorySSA.
ClosedPublic

Authored by asbirlea on Apr 17 2019, 10:33 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Apr 17 2019, 10:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 17 2019, 10:33 AM
asbirlea updated this revision to Diff 195820.Apr 18 2019, 3:02 PM

Simplify patch to preserve MemorySSA in the old pass manager only when the pass is already available (remove *require*).
New pass manager does not preserve it.

asbirlea edited the summary of this revision. (Show Details)Apr 18 2019, 3:03 PM
asbirlea edited the summary of this revision. (Show Details)Apr 18 2019, 4:12 PM

Simplify patch to preserve MemorySSA in the old pass manager only when the pass is already available (remove *require*).
New pass manager does not preserve it.

Ugh.

Ok, I want to revisit a suggestion I made previously: maybe let's just not enable MemorySSA by default in the old pass manager? Given that it forces you to add all of this code and complexity, it seems like we should just leave it off-by-default there, and enable it by default in the new pass manager only.

Other than the slight "ew"-ness of that, are there any other problems?

It's not as much the ew-ness that bothers me.
It's that, if MemorySSA is to be preserved and widely used in the loop pass, then this infrastructure change is needed anyway.

The simplifyLoop API is called from a bunch of other *loop* passes. Whenever these are updated, we'll need to teach this API to make the update (the new pass manager will care too)
Following this patch, it will be much easier to just get MemorySSA analysis pass and pass it along to the API that already does the right thing. This same approach saved me a lot of time when I updated the other Utils. If you notice in this patch, the calls to formDedicatedExitBlocks or SplitBlockPredecessors are already doing the right thing.

You're quite right that this is not a requirement to enable MemorySSA in the new pass manager. I am hoping it is not as big of a change to block it, and that it opens up more paths.
If it turns out to be a blocker, I'm happy to split the EnableMSSALoopDependency flag in 2 for the 2 pass managers and flip just one. What do you think?

I don't mean to interrupt the ongoing discussion; just wanted to send a few nits about the MSSA-specific bits. Thanks!

lib/Transforms/Utils/Local.cpp
1903 ↗(On Diff #195837)

Would it be better to iterate over the block's MemoryAccess list instead of the entire BB? I'd be happy to have a new removeBlock method or similar in MSSAU to do this.

1908 ↗(On Diff #195837)

Do we also want to clean up any Phis that this trivializes (...assuming that's possible), or is the intent for that to be cleaned up later?

It's not as much the ew-ness that bothers me.
It's that, if MemorySSA is to be preserved and widely used in the loop pass, then this infrastructure change is needed anyway.

The simplifyLoop API is called from a bunch of other *loop* passes. Whenever these are updated, we'll need to teach this API to make the update (the new pass manager will care too)
Following this patch, it will be much easier to just get MemorySSA analysis pass and pass it along to the API that already does the right thing. This same approach saved me a lot of time when I updated the other Utils. If you notice in this patch, the calls to formDedicatedExitBlocks or SplitBlockPredecessors are already doing the right thing.

You're quite right that this is not a requirement to enable MemorySSA in the new pass manager. I am hoping it is not as big of a change to block it, and that it opens up more paths.
If it turns out to be a blocker, I'm happy to split the EnableMSSALoopDependency flag in 2 for the 2 pass managers and flip just one. What do you think?

I see, the fact that this is mostly about getting the utility code to preserve makes lots of sense.

Minor comment below, will look in a bit more detail soon.

include/llvm/Transforms/Utils/LoopSimplify.h
60 ↗(On Diff #195837)

Comment needs updating.

asbirlea updated this revision to Diff 197487.Apr 30 2019, 5:09 PM
asbirlea marked 3 inline comments as done.

Address comments.
Moved some updates to MSSAU methods.
Added MSSA updates missed in the previous iteration.

MSSA bits LGTM modulo a few nits. Feel free to commit when Chandler is happy.

Thanks again!

lib/Analysis/MemorySSAUpdater.cpp
1258 ↗(On Diff #197487)

nit: Would it work just as well to take an ArrayRef<WeakVH> here and drop Start/Stop params? (That way, we can also simplify the loop to a for over UpdatedPHIs)

If not, please make UpdatedPhis a const&

1262 ↗(On Diff #197487)

Please clang-format

1290 ↗(On Diff #197487)

nit: s/auto */(const )?BasicBlock */ for consistency with elsewhere, please

asbirlea updated this revision to Diff 197676.May 1 2019, 5:14 PM
asbirlea marked 3 inline comments as done.

Address comments.

lib/Analysis/MemorySSAUpdater.cpp
1258 ↗(On Diff #197487)

Yes, it would work for this patch. I added the range to reuse it in insertDef, where the start and stop are different, but I didn't include that change here since it's not related.
Please let me know if you prefer to have the Start/Stop removed here and re-added in the follow up patch that cleans the other use cases.

lib/Analysis/MemorySSAUpdater.cpp
1258 ↗(On Diff #197487)

I was hoping more that the ArrayRef would make it so we don't need Start/End to begin with. Slicing/dicing those is trivial, and makes it more obvious what you're doing at the callsite IMO.

I don't feel super strongly either way, though; feel free to do Start/Stop if you think that it's cleaner.

asbirlea updated this revision to Diff 197882.May 2 2019, 3:40 PM
asbirlea marked 3 inline comments as done.

Rebase on top of cleanup patch.

lib/Analysis/MemorySSAUpdater.cpp
1258 ↗(On Diff #197487)

Done in separate cleanup patch. Thanks for the suggestion!

I'm trusting George w/ the MemorySSAUpdater review.

Everything else looks good except for some commented out code I've marked.

lib/Transforms/Utils/LoopSimplify.cpp
838–842 ↗(On Diff #197882)

?

867 ↗(On Diff #197882)

?

asbirlea updated this revision to Diff 198368.May 6 2019, 4:23 PM
asbirlea marked 2 inline comments as done.

Delete left-over comments.

(To be explicit, this LGTM, just letting George mark it as accepted when he's happy too.)

george.burgess.iv accepted this revision.May 6 2019, 4:54 PM

just letting George mark it as accepted when he's happy too

This CL sparks joy, so LGTM. :)

Thanks again!

This revision is now accepted and ready to land.May 6 2019, 4:54 PM

Thank you both for the review!

This revision was automatically updated to reflect the committed changes.

Hi,

With this patch the following starts hitting an assertion:

opt -S -o - memssa.ll -memoryssa -loop-simplify -early-cse-memssa

I get

opt: ../lib/Analysis/MemorySSA.cpp:2019: void llvm::MemorySSA::verifyDefUses(llvm::Function &) const: Assertion `find(predecessors(&B), Phi->getIncomingBlock(I)) != pred_end(&B) && "Incoming phi block not a block predecessor"' failed.

with memssa.ll being

target triple = "x86_64-unknown-linux-gnu"

define void @loop_imm_reg_plus2() {
  br i1 undef, label %bb5, label %bb3

bb5:                                              ; preds = %bb5, %0
  store i16 undef, i16* undef
  br i1 undef, label %bb5, label %bb3

bb3:                                              ; preds = %bb5, %0
  ret void
}

When the assertion fails we have:

(gdb) call F.dump()

define void @loop_imm_reg_plus2() {
  br i1 undef, label %bb5.preheader, label %bb3

bb5.preheader:                                    ; preds = %0
  br label %bb5

bb5:                                              ; preds = %bb5.preheader, %bb5
  store i16 undef, i16* undef
  br i1 false, label %bb5, label %bb3.loopexit

bb3.loopexit:                                     ; preds = %bb5
  br label %bb3

bb3:                                              ; preds = %bb3.loopexit, %0
  ret void
}

(gdb) call B.getName()
$11 = "bb5"
(gdb) call Phi->dump()
2 = MemoryPhi({%0,liveOnEntry},{bb5,1})