Page MenuHomePhabricator

Use MemorySSA in LICM to do sinking and hoisting.
Needs ReviewPublic

Authored by asbirlea on Nov 22 2017, 2:54 PM.

Details

Summary

Step 2 in using MemorySSA in LICM:
Use MemorySSA in LICM to do sinking and hoisting, all under "EnableMSSALoopDependency" flag.
Promotion is disabled.

Enable flag in LICM sink/hoist tests to test correctness of this change. Moved one test which
relied on promotion, in order to test all sinking tests.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Gentle ping!

Note this is still NFC since flag to enable use of MemorySSA remains disabled during this transition.
However I enabled testing to maintain correctness.

sanjoy requested changes to this revision.Dec 14 2017, 11:55 PM

Initial round of comments.

lib/Transforms/Scalar/LICM.cpp
162

Can this be an std::unique_ptr?

And why is it on the class as opposed to being a stack variable in runOnLoop like CurAST?

295

This seems unnecessary.

730–737

Probably better to leave this un-initialized; that way the compiler will warn if we forget to initialize it in one branch. You could also use a ternary here.

798

This can probably be a single llvm::any_of on CurLoop->blocks().

1789

How about call it isVolatileLoadOrLiveOnEntry?

1791

The usual idiom I've seen for this is:

if (!Processed.insert(Acc).second)
  return false;
1792

Should we be returning true in this recursive case? IE if we have a MemoryPhi that has one of its inputs as itself and the other input as live-on-entry then shouldn't that be equivalent to just a live-on-entry?

1798

I'd avoid testing for MemoryDef early -- instead I'd suggest doing this as:

if (auto *Phi = dyn_cast_or_null<MemoryPhi>(Acc)) {
} else if (auto *Def = dyn_cast_or_null<MemoryDef>(Acc)) {
}
1802

How about a range for on Phi->operands()? Or even better -- return llvm::all_of(Phi->operands(), <lambda>);

1809

Is this correct even if defining access for Def is a store in the loop?

1820

LLVM style is avoiding braces for one liners. You could also fold the assignment into the condition, like if (MemoryUseOrDef *AccI = ...)

1824

This can just be if (MemoryUse *MU = dyn_cast_or_null<MemoryUse>(MUD))

1841

s/if/If/

1842

This seems fishy -- if volatile loads do not invalidate pointers then why are they treated as defs by MSSA?

lib/Transforms/Scalar/LoopSink.cpp
301

How about adding /*MemorySSAUpdater=*/nullptr etc. here?

This revision now requires changes to proceed.Dec 14 2017, 11:55 PM
asbirlea updated this revision to Diff 127629.Dec 19 2017, 5:12 PM
asbirlea marked 14 inline comments as done.

Address comments.

lib/Transforms/Scalar/LICM.cpp
1791

Code in question removed.

1792

Right, but code in question removed.

1802

If using Phi->operands() I need to re-add the conversion from Use to MemoryAccess hidden in the macro in getIncomingValue().
New code would be:

return llvm::all_of(Phi->operands(), [MSSA, &Processed](const Use &Arg) {           
      return isVolatileLoadOrLiveOnEntry(
          cast_or_null<MemoryAccess>(Arg.get()), MSSA, Processed);                      
    });

Does this look better than existing?

Scratch that, code in question removed.

1809

Code updated, see comment below.

1842

Well, because they should be treated as defs. Motivation for special casing this was test/Transforms/LICM/volatile-alias.ll.
I updated the code to no longer consider volatile loads acceptable, meaning test in question will fail. And I believe that's the right thing.

sanjoy requested changes to this revision.Dec 20 2017, 4:31 PM

Some of the comments inline may be naive since I'm not very familiar with MemorySSA.

lib/Transforms/Scalar/LICM.cpp
405

Can this be a std::unique_ptr?

422

Should this assert be checking CurAST != nullptr ^ (MSSAUpdater != nullptr && MSSA != nullptr)?

775

Minor nit: I usually prefer leaving variables like Invalidated uninitialized; that way if I forget to assign to it on one branch of the if I'll get a warning and/or an ASan failure.

782

We should probably early exit if !Op->getType()->isPointerTy() (and assert Op->getType()->isPointerTy() in pointerInvalidatedByLoopWithMSSA etc.

790–791

Minor nit: even though unnecessary, I'd prefer using braces here since for readability.

972

I'm not sure that setting the defining access to nullptr here is correct -- if there is some subtle reason why it is, please add a comment.

974

Instead of two dyn_cast_or_nulls how about:

if (NewMemAcc) {
  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc)) {
    ...
  } else {
    auto *MemUse = cast<MemoryUse>(NewMemAcc);
  }
}

?

976

I'd prefer /*RenameUses=*/true.

982

I'm not clear on how this works -- IIUC you're calling into getClobberingMemoryAccess with NewMemUse's DefiningAccess set to nullptr, but:

  • Why don't we have to do this for MemoryDefs?
  • What if MSSA->getWalker() is a DoNothingMemorySSAWalker?
  • There are places where we should be crashing, like: CachingWalker::getClobberingMemoryAccess line 2078 that calls getClobberingMemoryAccess(DefiningAccess, Q) that calls ClobberWalker::findWalker which has if (auto *MU = dyn_cast<MemoryUse>(Start)).
1249–1250

Can this be cast_or_null?

1803

Stray comment?

1806

Minor nit: probably cleaner to use if (MSSA->isLiveOnEntryDef(Source) || !CurLoop->contains(Source->getBlock())) here.

This revision now requires changes to proceed.Dec 20 2017, 4:31 PM
asbirlea updated this revision to Diff 127969.Dec 21 2017, 4:32 PM
asbirlea marked 17 inline comments as done.

Comments.

asbirlea added inline comments.
lib/Transforms/Scalar/LICM.cpp
422

At some point I was testing with both enabled, but considering the added compile time when doing that, yes :).

982

AFAIU:
For Defs the DefiningAccess is properly updated.
For Uses, there is a DefiningAccess set, but that one is not optimized. When adding an access like in this case, calling getClobberingMemoryAccess will optimize it.
If the walker is DoNothingMemorySSAWalker, it won't optimize?

Pulling in george.burgess.iv to clarify, it's possible I'm missing something here.

Only looked at the bit I was mentioned in.

lib/Transforms/Scalar/LICM.cpp
982

IIUC you're calling into getClobberingMemoryAccess with NewMemUse's DefiningAccess set to nullptr

I'm assuming you meant MemUse, in which case insertUse sets up the defining access to something non-null.

It's sort of sketchy that we're trying to eagerly update the defining access using the walker, though. Is there a reason that we can't call MSSA->getWalker()->getClobberingMemoryAccess(MemUse); when we need optimized clobbers? Doing so should be incredibly cheap when the use has already been optimized, and it lets us be lazy about the work we do (if we don't need an accurate clobber for MemUse, we'll just never compute it)

asbirlea marked an inline comment as done.Dec 22 2017, 11:35 AM
asbirlea added a subscriber: dberlin.
asbirlea added inline comments.
lib/Transforms/Scalar/LICM.cpp
982

I'm assuming you meant MemUse, in which case insertUse sets up the defining access to something non-null.

Thanks for clarifying this.

It's sort of sketchy that we're trying to eagerly update the defining access using the walker, though. Is there a reason that we can't call MSSA->getWalker()->getClobberingMemoryAccess(MemUse); when we need optimized clobbers? Doing so should be incredibly cheap when the use has already been optimized, and it lets us be lazy about the work we do (if we don't need an accurate clobber for MemUse, we'll just never compute it)

The reasoning here is that when making code changes such as hoist/sink, I need accesses to be (reasonably) optimized. I'm not necessarily to looking to get full precision here, I'd be perfectly happy with an API to optimize up to the MemorySSA optimize-uses cap.
In LICM.cpp:1652 (and in the future for promotion) I'm relying on getting the defining access, not the walker->clobbering access, allowing for some imprecision in exchange for not paying the lookup time for blocks with large load/store count.
I had come across a case where after a hoist or sink, this approach did not work for a very small testcase without using the walker to get clobbering.
So the choice I made was to use the walker ahead of time to update accesses I insert when cloning, allowing me to use getDefining afterwards.

Hopefully I clarified the intention here :). Do you think there's a better way to address this problem? I'm open to suggestions.

@dberlin

So, this use renaming is expensive, and i'd like to understand the goal (It requires walking all stores and loads in the dominator subtree rooted at your memory access) It's really meant for when you've inserted defs that may alias existing uses.
If your goal is to replace all uses of an old memory access with some new memoryaccess, you want to use the replace API :)

The code here is creating a new memory access to handle cloning an access in all exit blocks, where that access may alias existing uses, so I think using the replace API isn't enough.
Please let me know if there is a way to handle this differently.

Gentle ping.

asbirlea updated this revision to Diff 131215.Jan 24 2018, 3:07 AM

Add a flag for the decision of using getDefining vs Walker->getClobbering, for optimizing pathological cases.

lebedev.ri added inline comments.
test/Transforms/LICM/sinking.ll
363

But there is no sink-promote.ll in this differential?
Is that in some other patch?

asbirlea updated this revision to Diff 131230.Jan 24 2018, 5:08 AM

Added sink-promote.ll. Thanks for catching this!

lib/Transforms/Scalar/LICM.cpp
982

(To be clear: the addition of the flag resolved my MemorySSA comments. While it's sort of hacky that we need to have it in the first place, the best place to handle "this {block,function} is pathologically big; let's give up instead of taking forever to walk it, and rewalk it, and rewalk it, and ..." is in MSSA, IMO. Until we make MSSA smart enough to actually do that, though, a targeted escape hatch seems like the best way forward to me.)

asbirlea marked 6 inline comments as done.Jan 26 2018, 10:03 AM

Thanks George, marking as Done. Also note that the optimization enables by this flag remains disabled.

Other reviewers: please let me know if there are remaining issues or concerns.
Please note that the use of MemorySSA remains disabled with this patch.

sanjoy added inline comments.Feb 21 2018, 1:11 PM
lib/Transforms/Scalar/LICM.cpp
1

Stray edit?

101

Line too long?

422

Probably better to have two asserts here:

  • assert((MSSAUpdater == nullptr) == (MSSA == nullptr))
  • assert((CurAST != nullptr) ^ (MSSA != nullptr))
980

Note: I did not revisit this bit since it looks like @george.burgess.iv settled it.

1255

I not convinced this is a good idea -- it looks like we're coding to the implementation of getClobberingMemoryAccess here instead of coding to its interface. But if @george.burgess.iv is fine with it, I am too.

1255

It looks like MemorySSA::CachingWalker::getClobberingMemoryAccess has an early exit if OldMemAcc was optimized. Are we okay not updating the defining access in that case?

1795

If MUD is always guaranteed to be a use then this should be cast_or_null. Otherwise please update the comment.

asbirlea updated this revision to Diff 135561.Feb 22 2018, 4:39 PM
asbirlea marked 4 inline comments as done.

Address comments.

asbirlea marked an inline comment as done.Feb 22 2018, 4:39 PM
asbirlea added inline comments.
lib/Transforms/Scalar/LICM.cpp
1255

If it's been optimized, then the defining access should have been updated, and viceversa.
@george.burgess.iv: Could you clarify this please? I don't see resetOptimized being called on any path for the call chain starting with moreToPlace->insertDef, though it would make sense for this to happen. Am I missing something here?

lib/Transforms/Scalar/LICM.cpp
1255

I not convinced this is a good idea -- it looks like we're coding to the implementation of getClobberingMemoryAccess here instead of coding to its interface. But if @george.burgess.iv is fine with it, I am too

In general, I agree, but Walkers are a sticky concept. The model we've sold people is "always call getWalker()->getClobberingMemoryAddress(MA) if you need the optimized access; the walker will handle making repeated calls fast," and we're specifically calling this on MSSA->getWalker().

I'll try to find a way to structure MSSA so that this guarantee is more obvious.

Am I missing something here?

Our theoretical isOptimized bit depends on two things: being flipped by a call to setOptimized, and either our defining access or optimized access having the same ID as it did when setOptimized was called. (...It also depends on stores not appearing out of thin air ;) )

So, when you move a Def, all Uses are implicitly invalided by the replaceAllUsesWith (since their defining access no longer has the same ID as before), and the Def's cached clobber is invalidated when you call setDefiningAccess on it.

Similarly, when you move a Use, we just set its defining access to whatever's closest. So, its cache will be invalidated (or not, if you move it right under its old clobber. But then the optimized use is still correct).

What I'm unsure about is what happens what happens to Defs optimized to a Def when said optimized-to Def is moved. I feel like I asked this during the original reviews for the caching/updater stuff, but I don't remember the answer. I'll do archaeology and get back to you. :)

(If the Def/Def case is uninteresting to this pass, feel free to not block this patch on my search)

lib/Transforms/Scalar/LICM.cpp
1255

OK, so assuming the fixes stick, https://bugs.llvm.org/show_bug.cgi?id=36529 should fix any def/def craziness we may see here.

Moving things around above the defs should also be fine, since if you have a Def A which has an "optimized" clobber B and you add a clobber between them, that sounds like a functional change (or, if nothing can observe that clobber, a waste of CPU time ;) ). Similarly, if B is moved such that a pre-existing clobber should become A's clobber, that sounds like a functional change.

I think this resolves all the questions. Please let me know if not.

Thank you for the fix, George. Yes, I think all issue are addressed now.

asbirlea updated this revision to Diff 147428.May 17 2018, 7:00 PM

Rebase and ping.

asbirlea updated this revision to Diff 166735.Sep 24 2018, 1:08 PM

Rebase patch after resect changes.

Updates:
Change test sink-promote due to PR38989.
Sink is incomplete with MSSA due to recent changes, added TODO and will extend in separate patch.