Page MenuHomePhabricator

[MemorySSA] Make insertDef insert corresponding phi nodes.
ClosedPublic

Authored by asbirlea on Feb 25 2019, 4:24 PM.

Details

Summary

The original assumption for the insertDef method was that it would not
materialize Defs out of no-where, hence it will not insert phis needed
after inserting a Def.

However, when cloning an instruction (use case used in LICM), we do
materialize Defs "out of no-where". If the block receiving a Def has at
least one other Def, then no processing is needed. If the block just
received its first Def, we must check where Phi placement is needed.
The only new usage of insertDef is in LICM, hence the trigger for the bug.

But the original goal of the method also fails to apply for the move()
method. If we move a Def from the entry point of a diamond to either the
left or right blocks, then the merge block must add a phi.
While this usecase does not currently occur, or may be viewed as an
incorrect transformation, MSSA must behave corectly given the scenario.

Resolves PR40749 and PR40754.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Feb 25 2019, 4:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 25 2019, 4:24 PM
asbirlea updated this revision to Diff 188281.Feb 25 2019, 5:33 PM

Nit: add missed CHECK in test.

Thanks for this!

lib/Analysis/MemorySSAUpdater.cpp
274 ↗(On Diff #188272)

It's unclear to me why this is necessary. We keep an OptimizedID in MemoryDefs to catch these kinds of movements and transparently invalidate the cached optimized Access in those cases. Does that not work here?

(It also seems sort of unrelated to this patch, unless I'm missing something?)

301 ↗(On Diff #188272)

nit: I think there's a general preference for preincrement when the difference doesn't matter.

319 ↗(On Diff #188272)

This was pretty tricky for me to reason about. If you're 100% certain that all of this is correct, feel free to leave this as is. Otherwise, can we please shuffle these new InsertedPhis into an intermediate SmallVector<AssertingVH<MemoryPhi>, N>? The idea would be to keep them there, loop over the new SmallVector, and transfer them into InsertedPhis after the for (auto *Pred : predecessors) loop below.

Sharing my work anyway:

getPreviousDefFromEnd is interesting here, since it'll *also* do Phi insertion/population/trivial removal.

I think we should be fine on the population bit: it only ever calls getPreviousDefFromEnd, so existing Phis should never be stomped by it.

Similarly, insertion should be OK, since it only inserts a Phi when we reach a cycle, and the set of Phis should be relatively complete with the ones we've just added.

Trivial removal is a bit more tricky. You can totally make it recurse on a trivial Phi we've just created. The fun bit is that it only recurses on the *Users* of the value we're replacing a Phi with. So the question is whether we can end up in a world with a partially-formed Phi (e.g. we add one pred of IDFPhi, so IDFPhi is now a User, and thus a candidate for trivial deletion). I don't *think* that should be a problem, since we should have a complete and minimal (modulo the Phis we're in the process of inserting) set of Phis at this point. Since getPreviousDefRecursive guarantees minimality in most cases(*), I don't see how we can be handed a trivial Phi to put in the Incoming list for this.

(*) - The other cases result from irreducible control flow. That's technically nonminimal, but AFAICT it's a nonminimal form that we won't trivially eliminate later on, so...

322 ↗(On Diff #188272)

nit: Would it make sense to hoist this out of one (or both?) loops? Seems like sharing work between getPreviousDefFromEnd invocations is harmless.

341 ↗(On Diff #188272)

Why are we looping over all of the InsertedPhis? Shouldn't this just be the subset of them that we added as a part of the IDF stuff above? (Any Phis we add as a part of getPreviousDef should already be minimal, AIUI)

342 ↗(On Diff #188272)

nit: should this be cast_or_null? WeakVH doesn't track across RAUWs IIRC

Please also bring this into the if (...)

test/Analysis/MemorySSA/pr40749.ll
1 ↗(On Diff #188272)

; REQUIRES: asserts?

asbirlea updated this revision to Diff 188452.Feb 26 2019, 1:35 PM

Address comments.

asbirlea marked 6 inline comments as done.Feb 26 2019, 1:48 PM
asbirlea added inline comments.
lib/Analysis/MemorySSAUpdater.cpp
274 ↗(On Diff #188272)

IIUC, if we have a def, let's call it DefLower, that is optimized to DefBefore replaced here, then DefLower maintains a field: operator 1, pointing to the optimized access), making it a user of DefBefore. If we replace that user with MD, we're optimized DefLower to MD, which may not be correct. Calling resetOptimized will also remove the optimized user. This relates to D56467.

Yes, it's unrelated to this patch, I noticed it when making the changes below and added the change. I can split it up if you prefer it.

319 ↗(On Diff #188272)

I *think* I followed the guidelines you outlined. All newly inserted phis are kept separate while calling the recursive getPreviousDef, and removing non-minimal phis is only done of these new phis.
Please let me know if I missed anything.

george.burgess.iv marked an inline comment as done.Feb 26 2019, 2:58 PM
george.burgess.iv added inline comments.
lib/Analysis/MemorySSAUpdater.cpp
274 ↗(On Diff #188272)

If we replace that user with MD, we're optimized DefLower to MD, which may not be correct

You're totally correct. isOptimized() isn't just bit, though: it should be verifying that getOptimized()->getID() == SomeCachedIDInTheMemoryDef. In this case, that test won't pass, so the MemoryDef in question should be considered unoptimized.

Calling resetOptimized will also remove the optimized user. This relates to D56467.

Looking at D56467 again, that sounds like broken verification code more than anything. We lazily invalidate caches for Uses (e.g. a Use's DefiningAccess); I don't see why we should treat Defs any differently. Sorry for not catching that earlier.

If we wanna land this change now and fix the verification later, I'm OK with that. But for all intents and purposes, Uses that originate from MemoryDefs' OptimizedAccesses shouldn't be treated as Uses unless the MemoryDef still reports itself to be optimized.

...If we find ourselves iterating over the Users of MemoryDefs often, it may be worth making an iterator that skips invalidated Users. IDK whether that's a common use-case (pun intended) or not, though.

I can split it up if you prefer it.

It's small enough that I'm OK with bundling it. I was just making sure it wasn't related in a way that I was missing

319 ↗(On Diff #188272)

Yup :)

285 ↗(On Diff #188452)

Please sink NewInsertedPhis into the if (Iter == IterEnd) { block (removing the trivial Phis later on in this function may invalidate them; I haven't reasoned about whether or not this'll actually happen, but I can't see why we'd care about the guarantee that that doesn't happen, so ...)

344 ↗(On Diff #188452)

Please grab the value for IdxE before the FixupList.empty() loop above; that can add Phis, and it shouldn't be profitable to try to remove them (or if it is, it'd be nice to have an explicit example of where that can happen...)

asbirlea updated this revision to Diff 188582.Feb 27 2019, 11:03 AM
asbirlea marked 9 inline comments as done.

Address comments.

lib/Analysis/MemorySSAUpdater.cpp
274 ↗(On Diff #188272)

You're right that replacing the Def should make the user unoptimized due to the different IDs. Removing the change, and I'll see if I can find the test that failed the verification in the previous patch. Arbitrary insertions may trigger a verification failure from here as well.

322 ↗(On Diff #188272)

Yes...but I'd rather not do it here. The current code seems convoluted enough that I'd do any refactoring change separate.

285 ↗(On Diff #188452)

You're right, I meant to clear it after adding to InsertedPhis, but sinking to reduce its scope is better!

Thanks again!

This revision is now accepted and ready to land.Feb 27 2019, 12:09 PM
This revision was automatically updated to reflect the committed changes.