This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Use correct memory location for read clobber check
ClosedPublic

Authored by nikic on Dec 18 2020, 12:39 AM.

Details

Summary

MSSA DSE starts at a killing store, finds an earlier store and then checks that the earlier store is not read along any paths (without being killed first). However, it uses the memory location of the killing store for that, not the earlier store that we're attempting to eliminate.

This has a number of problems:

  • Mismatches between what BasicAA considers aliasing and what DSE considers an overwrite (even though both are correct in isolation) can result in miscompiles. This is PR48279, which D92045 tries to fix in a different way. The problem is that we're using a location from a store that is potentially not executed and thus may be UB, in which case analysis results can be arbitrary.
  • Metadata on the killing store may be used to determine aliasing, but there is no guarantee that the metadata is valid, as the specific killing store may not be executed. Using the metadata on the earlier store is valid (it is the store we're removing, so on any execution where its removal may be observed, it must be executed).
  • The location is imprecise. For full overwrites the killing store will always have a location that is larger or equal than the earlier access location, so it's beneficial to use the earlier access location. This is not the case for partial overwrites, in which case either location might be smaller. There is some room for improvement here.

Using the earlier access location means that we can no longer cache which accesses are read for a given killing store, as we may be querying different locations. However, it turns out that simply dropping the cache has no notable impact on compile-time, so that seems fine: https://llvm-compile-time-tracker.com/compare.php?from=3d56644f18eefe30e353e7fae3cb5e5daf0a0ffb&to=9bdb4e5b085bc3d054c30f6256c344a14748a715&stat=instructions

Diff Detail

Event Timeline

nikic created this revision.Dec 18 2020, 12:39 AM
nikic requested review of this revision.Dec 18 2020, 12:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 18 2020, 12:39 AM
fhahn accepted this revision.Dec 18 2020, 5:42 AM

LGTM, thanks!

Using the earlier access location means that we can no longer cache which accesses are read for a given killing store, as we may be querying different locations. However, it turns out that simply dropping the cache has no notable impact on compile-time.

Yes that should be fine. There were some major changes after the caching was added which meant that now the 'check-for-reads' loop is not as critical to compile time as before. The cache mostly helped to explore further before running out of budget. So there are some cases we will miss without caching, but from the stats I collected for this patch, it seems there are only minor negative swings and it is best to get this fix in and then potentially tweak it further.

This revision is now accepted and ready to land.Dec 18 2020, 5:42 AM
fhahn added inline comments.Dec 18 2020, 5:45 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1957

Can this just be MemoryLocation CurrentLoc? We should skip the case when it would be None and it should always be != None before after the loop.

nikic added inline comments.Dec 18 2020, 9:06 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1957

This uses Optional<MemoryLocation> because getLocForWriteEx() returns it that way. Should I copy it into a separate non-Optional variable after the check that it is not None?

fhahn added inline comments.Dec 18 2020, 9:29 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1957

I'd put the result of getLocForWriteEx into a new temprary and move the content to CurrentLoc after the check. Or have something like

if (auto Loc = getLocForWriteEx(....)) {
  CurrentLoc = *Loc;
} else {
  StepAgain = true;
  ....
  continue;
}
nikic updated this revision to Diff 312836.Dec 18 2020, 9:46 AM

Drop Optional<> wrapper.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1957

I liked your second suggestion. Does the new version look fine?

fhahn added inline comments.Dec 18 2020, 10:04 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1957

that looks good, thanks!

This revision was automatically updated to reflect the committed changes.
tambre added a subscriber: tambre.Dec 18 2020, 12:27 PM
tambre added inline comments.
llvm/test/Transforms/DeadStoreElimination/MSSA/out-of-bounds-stores.ll
33

Should the "FIXME." have been removed?