This is an archive of the discontinued LLVM Phabricator instance.

[MemorySSAUpdater] Update Phi operands after trivial Phi elimination
ClosedPublic

Authored by labrinea on Jul 17 2018, 7:08 AM.

Details

Summary

Bug fix for PR37445. The regression test is a reduced version of the original reproducer attached to the bug report. The underlying problem and its fix are similar to PR37808. The bug lies in MemorySSAUpdater::getPreviousDefRecursive(), where PhiOps is computed before the call to tryRemoveTrivialPhi() and it ends up being out of date, pointing to stale data.

Diff Detail

Event Timeline

labrinea created this revision.Jul 17 2018, 7:08 AM

A few remarks:

  • SmallVector<WeakVH, 8> PhiOps fixes the bug on its own (without the rest changes) and I am wondering why..
  • When we mark a block as visited why do we cache it? When the recursion ends we might trivially remove the Phi. In that case the second cache insertion for the same key block should fail, no?
  • Do we ever reach the PHIExistsButNeedsUpdate case? Is it when a Phi existed beforehand, meaning we did not create it? I can't think of another way to reach that state.
  • Interestingly enough the reproducer only made opt crash in bitcode form and not in IR form.

Thanks for this!

Looks like the MSSA that we're starting with here has a redundant Phi to start with (6 = MemoryPhi({_, liveOnEntry}, {_2, 6})), so it's unsurprising that we try to remove it. In general, I'm noticing that MSSA tries really hard to keep this nice minimal Phi form, but it's really easy for a user to inadvertently make a Phi trivially removable with a RAUW or similar. Fixing this is likely nontrivial + out of the scope of this patch, so I'm happy to support this for now. It's just a mildly sad state of affairs. :)

Do we ever reach the PHIExistsButNeedsUpdate case? Is it when a Phi existed beforehand, meaning we did not create it? I can't think of another way to reach that state.

Good point. In general, we'd hit that case if we called getPreviousDefRecursive on a BB with > 1 pred with an existing Phi, but I don't see how that can happen today. The only callers are:

  • getPreviousDef, which, unless it's given a Phi, is guaranteed to not call getPreviousDefRecursive if there's a Phi in the same BB as its argument.
  • getPreviousDefFromEnd, which has an identical guarantee (except it takes a BB instead of a MemoryAccess)

...And we only ever call getPreviousDef with Uses/Defs.

Replacing that code with llvm_unreachable gave 0 errors in a clang bootstrap, so I assume it's dead code. If you'd like to remove it (or replace it with an assertion), please do so in a separate patch.

SmallVector<WeakVH, 8> PhiOps fixes the bug on its own (without the rest changes) and I am wondering why..

Best guess: we end up calling tryRemoveTrivialPhi(nullptr, VectorOfWeakVH), which ends up seeing a vector consisting of {nullptr, liveOnEntry} (nullptr being a special value we use in tryRemoveTrivialPhi, so passing it in as an operand is really sketchy), which then "recurses" on and returns liveOnEntry. liveOnEntry != nullptr, so we don't try to create a phi/etc.

I doubt all of that is right, but ...

When we mark a block as visited why do we cache it? When the recursion ends we might trivially remove the Phi. In that case the second cache insertion for the same key block should fail, no?

Not sure I understand the question. Do you mean "why do we cache the Phi we've just created if we're visiting a block for the second time?" If so, the cache will automatically track the removal if we do ultimately end up removing the phi. If not, we'll fill the Phi in when we wind our stack back to the bit that populates it, so the second cache insertion should be a nop anyway..

Interestingly enough the reproducer only made opt crash in bitcode form and not in IR form.

Does the original test-case crash reliably as IR for you? If so, please use that instead. (Phab won't let me download the attached bitcode, but with asan, I see use-after-free crashes 100% of the time in the original repro).

lib/Analysis/MemorySSAUpdater.cpp
68

Should this be a TrackingVH<MemoryAccess> instead? That way, we don't need the "Phi ops may be out of date" loop below.

90

cast_or_null, please. We know this'll be a MemoryAccess if it's non-null.

Does the original test-case crash reliably as IR for you? If so, please use that instead. (Phab won't let me download the attached bitcode, but with asan, I see use-after-free crashes 100% of the time in the original repro).

It does, but using opt -S -O3 ./tc_memphi_gvnhoist.ll -enable-gvn-hoist. Using bugpoint on that command you get the bitcode I uploaded.

Not sure I understand the question. Do you mean "why do we cache the Phi we've just created if we're visiting a block for the second time?" If so, the cache will automatically track the removal if we do ultimately end up removing the phi. If not, we'll fill the Phi in when we wind our stack back to the bit that populates it, so the second cache insertion should be a nop anyway..

Imagine we call getPreviousDefRecursive on a BB with > 1 pred. Assume there's no Phi yet. We mark the BB as visited and start collecting PhiOps with recursive calls via getPreviousDefFromEnd. By the time we reach BB again we create an empty Phi and cache it for the first time (line 62). As all the PhiOps are collected we call tryRemoveTrivialPhi which might have replaced the Phi with another MemoryAccess. Then we try to cache that MemoryAccess with the same BB key (line 110), which should return false.

Should this be a TrackingVH<MemoryAccess> instead? That way, we don't need the "Phi ops may be out of date" loop below.

Works, but still it's not clear to me why. What happens if the PhiOp is a deleted Phi itself? Do we still keep the instance of the dead Phi even though MSSA has deleted the corresponding MemoryAccess? How would this work without the updating loop?

If the bitcode is crashing but the textual IR isn't, you're probably getting bitten by use-list ordering. You can use the preserve-ll-uselistorder option for "opt" to preserve it in IR.

If the bitcode is crashing but the textual IR isn't, you're probably getting bitten by use-list ordering. You can use the preserve-ll-uselistorder option for "opt" to preserve it in IR.

Yeap, that worked.

Waiting for @george.burgess.iv's comments on the following to proceed accordingly.

Not sure I understand the question. Do you mean "why do we cache the Phi we've just created if we're visiting a block for the second time?" If so, the cache will automatically track the removal if we do ultimately end up removing the phi. If not, we'll fill the Phi in when we wind our stack back to the bit that populates it, so the second cache insertion should be a nop anyway..

Imagine we call getPreviousDefRecursive on a BB with > 1 pred. Assume there's no Phi yet. We mark the BB as visited and start collecting PhiOps with recursive calls via getPreviousDefFromEnd. By the time we reach BB again we create an empty Phi and cache it for the first time (line 62). As all the PhiOps are collected we call tryRemoveTrivialPhi which might have replaced the Phi with another MemoryAccess. Then we try to cache that MemoryAccess with the same BB key (line 110), which should return false.

Should this be a TrackingVH<MemoryAccess> instead? That way, we don't need the "Phi ops may be out of date" loop below.

Works, but still it's not clear to me why. What happens if the PhiOp is a deleted Phi itself? Do we still keep the instance of the dead Phi even though MSSA has deleted the corresponding MemoryAccess? How would this work without the updating loop?

As all the PhiOps are collected we call tryRemoveTrivialPhi which might have replaced the Phi with another MemoryAccess. Then we try to cache that MemoryAccess with the same BB key (line 110), which should return false

Thanks for the clarification. I don't think that can happen, since the only way we can remove a Phi is if we call tryRemoveTrivialPhi directly on it (which doesn't happen), or if we recursively call it on said Phi. We only recurse to Users of arbitrary MemoryAccesses, and the blank Phis we create are Users of nothing until we fill their operands in.

If you'd like, you're welcome to add something like assert(Inserted || CachedPreviousDef[BB] == Result); to be sure of this, but like said, I don't see how it can happen.

Works, but still it's not clear to me why. What happens if the PhiOp is a deleted Phi itself?

MSSA Phi deletion requires replacing all Uses (...in the LLVM sense of Use, not MemoryUse) of the to-be-deleted Phi with another MemoryAccess prior to us actually deleteing the Phi. As a part of this replacement, the TrackingVHes will all automatically get pointed at this new MemoryAccess.

labrinea updated this revision to Diff 156466.Jul 20 2018, 3:59 AM

Changes to prior revision.

  • Removed the update loop for PhiOps and used TrackingVH<MemoryAccess> instead.
  • Replaced the Bitcode reproducer with IR using -preserve-ll-uselistorder.

LGTM after one nit is addressed. Thanks again!

lib/Analysis/MemorySSAUpdater.cpp
90

Phi should always be non-null now

This revision is now accepted and ready to land.Jul 20 2018, 2:05 PM
This revision was automatically updated to reflect the committed changes.