This is an archive of the discontinued LLVM Phabricator instance.

[MemCpyOpt] Fix MemorySSA preservation
ClosedPublic

Authored by nikic on Oct 3 2020, 2:32 AM.

Details

Summary

moveUp() moves instructions, so we should move the corresponding memory accesses as well. We should also move the store instruction itself: Even though we'll end up removing it later, this gives us a correct MemoryDef to replace.

Noticed this discrepancy while looking at D26739.

Diff Detail

Event Timeline

nikic created this revision.Oct 3 2020, 2:32 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 3 2020, 2:32 AM
nikic requested review of this revision.Oct 3 2020, 2:32 AM

Thank you for fixing this!

Could you clang-format the patch?

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

Is it possible for the cast here to fail?
P is known to modify the Load location a the callsite. Is it possible this is true for specific cases not modeled as MemoryDefs in MemorySSA (e.g. when using a non-standard aa pipeline, and basicaa is disabled, certain accesses are seen as "can access/modify" but are ignored in the MemorySSA modeling - see MemorySSA.cpp:1766).

nikic updated this revision to Diff 296288.Oct 5 2020, 1:54 PM

Be more conservative when fetching the MemoryDef for P.

nikic added inline comments.Oct 5 2020, 1:57 PM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

I wasn't able to come up with a case that fails based on some quick experiments -- anything I tried would get foiled by the above safety checks without basicaa. However, it doesn't cost us anything to be conservative here, so I changed this to use a dyn_cast_or_null.

nikic updated this revision to Diff 296294.Oct 5 2020, 2:01 PM

Revert previous change.

nikic added inline comments.Oct 5 2020, 2:04 PM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

Actually, thinking about this again, just using dyn_cast_or_null here isn't safe: Just because we can't get the MemoryDef for P does not mean that we don't have to move accesses in MemorySSA, we just no longer know where they need to be moved to. With that in mind, I think it is safer to leave the cast<> and let is assert if it turns out that we can run into this issue after all.

asbirlea added inline comments.Oct 5 2020, 5:57 PM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

Agreed, we'd still need an insertion point.
I think the logic would be something like this:

MemoryAccess *InsertPoint = nullptr;
Instruction *LastToMove = ToLift[ToList.size()-1];
for (auto &Ins : make_range(P->getIterator(), --LastToMove->getIterator())) {
  if (InsertPoint = MSSAU->getMemorySSA()->getMemoryAccess(&Ins))
    break;
}

////// below

// No need to move accesses is InsertPoint == nullptr
if (MSSAU && InsertPoint) {
  if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I))
    MSSAU->moveBefore(MA, InsertPoint);
}
nikic added inline comments.Oct 7 2020, 9:32 AM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

This doesn't look quite right to me either. Imagine we have this kind of sequence:

P
ToLift[1]
MA
ToLift[0] = SI

While there is no memory access between P and ToLift[1], it is still necessary to move the ToLift[0] access above MA.

I think we would have to do something like this to handle it:

MemoryAccess *InsertPoint =
    MSSAU ? MSSAU->getMemorySSA()->getMemoryAccess(P);
// Below
if (MSSAU) {
  if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I)) {
    if (InsertPoint)
      MSSAU->moveBefore(MA, InsertPoint);
    else
      InsertPoint = MA;
  }
}
nikic updated this revision to Diff 296711.Oct 7 2020, 9:35 AM

Handle P not being a MemoryAccess.

asbirlea added inline comments.Oct 7 2020, 3:34 PM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

You're right, there may be accesses that are interleaved with ToLift entries.
But not all entries in ToList can have an access based on the check below (or is that not the case?).
For example:

P
ToLift[1]      -> getMemAccess = nullptr
MA
ToLift[0] = SI  -> needs to be moved before MA, MA needs to be found

In your example, ToLift[0] would be moved before ToLift[1], and that doesn't look right.

A simpler approach may be:

  • get first access before P (if P has an access get the iterator for memory accesses and do a decrement; if it doesn't walk instructions up to LI, which has an access for sure, or pass this info into the method from the call site which does this exact walk).
  • in the loop below do:
assert (MemInsertPoint && "Exists");
if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I))
  MSSAU->moveAfter(MA, MemInsertPoint);
  MemInsertPoint = MA;
}
nikic updated this revision to Diff 297330.Oct 9 2020, 1:41 PM

Next try...

nikic added inline comments.Oct 9 2020, 1:44 PM
llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
554

You're right, my previous code didn't really make sense, as the relevant memory access isn't part of ToLift. I've now updated it according to your suggestion, hopefully correctly. This is pretty ugly, but at least should go away once we determine this based on MemorySSA.

asbirlea accepted this revision.Oct 12 2020, 7:39 AM

LGTM.

This revision is now accepted and ready to land.Oct 12 2020, 7:39 AM
This revision was automatically updated to reflect the committed changes.