This is an archive of the discontinued LLVM Phabricator instance.

[MemorySSA] Be more conservative when traversing MemoryPhis.
ClosedPublic

Authored by fhahn on Sep 16 2020, 11:00 AM.

Details

Summary

I think we need to be even more conservative when traversing memory
phis, to make sure we catch any loop carried dependences.

This approach updates fillInCurrentPair to use unknown sizes for
locations when we walk over a phi, unless the location is guaranteed to
be loop-invariant for any possible loop. Using an unknown size for
locations should ensure we catch all memory accesses to locations after
the given memory location, which includes loop-carried dependences.

Diff Detail

Event Timeline

fhahn created this revision.Sep 16 2020, 11:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 16 2020, 11:00 AM
Herald added a subscriber: Prazek. · View Herald Transcript
fhahn requested review of this revision.Sep 16 2020, 11:00 AM
fhahn updated this revision to Diff 292338.Sep 16 2020, 2:14 PM

Add accidentially dropped include of User.h

I'm in favor of being conservative here and checking for only constant indexes on the geps.

llvm/include/llvm/Analysis/MemorySSA.h
1262

I'm not clear that the size should be always unknown after phi translation with different ptr, but feel free to correct me.
Here's my suggestion.

if (Translator.getAddr() != Location.Ptr) {
  CurrentPair.second = CurrentPair.second.getWithNewPtr(Translator.getAddr());
  if (PerformedPhiTranslation)
            *PerformedPhiTranslation = true;
} else {
  CurrentPair.second = Location.getWithNewSize(LocationSize::unknown());
}
fhahn added inline comments.Sep 16 2020, 3:03 PM
llvm/include/llvm/Analysis/MemorySSA.h
1262

Hm, I think if we translate to a different address, we still should set to an unknown size, as the translated address could itself be loop dependent and reference multiple actual locations.

But if we translate to an invariant address, it should probably be safe to use the precise address?

The invariance criteria in the patch is just a few things that matter in practice and are easy to check, but I am sure there is potential for detecting more cases there, after we established a safe baseline

fhahn updated this revision to Diff 292507.Sep 17 2020, 7:57 AM

use precise size for translated addr.

fhahn added inline comments.Sep 17 2020, 8:02 AM
llvm/include/llvm/Analysis/MemorySSA.h
1262

I tried to come up with a test case where things go wrong when we use the precise location after successfully translating the address, but failed to do so.

I adjusted the code to keep the precise location when PHI translation succeeded. I am still not entirely sure if this is completely safe, but with DSE & MemorySSA there is now a client that will most likely surface a test case, if things go wrong.

Please let me know which approach you prefer, I am fine with either.

asbirlea added inline comments.Sep 17 2020, 12:30 PM
llvm/include/llvm/Analysis/MemorySSA.h
1262

My inclination here after further review of the code is to not set the size to unknown for all cases, but it's possible it's necessary.
I'd use the same loop invariant condition on the new address.

if (Translator.getAddr() != Location.Ptr) {
  CurrentPair.second = CurrentPair.second.getWithNewPtr(Translator.getAddr());

  if (Translator.getAddr() && 
      !IsGuaranteedLoopInvariant(const_cast<Value *>(Translator.getAddr()))
          CurrentPair.second = CurrentPair.second.getWithNewSize(LocationSize::unknown());

  if (PerformedPhiTranslation)
          *PerformedPhiTranslation = true;
}

(Move Translator.getAddr() to a local variable)

Also, use CurrentPair.second = CurrentPair.second.get..., not CurrentPair.second = Location.get so if the size was reset in the above condition checking loop invariance, that info is kept.

I *think* this is conservatively correct. What do you think?

fhahn updated this revision to Diff 292602.Sep 17 2020, 1:17 PM

Apply suggested change, set size to unknown if result of phi translation is not invariant.

fhahn added inline comments.Sep 17 2020, 1:18 PM
llvm/include/llvm/Analysis/MemorySSA.h
1262

I *think* this is conservatively correct. What do you think?

Thanks, I applied the suggestion. This should be conservatively correct. Once this goes in I plan on enabling DSE + MemorySSA again and see if/what the remaining failures are.

asbirlea accepted this revision.Sep 17 2020, 2:07 PM
This revision is now accepted and ready to land.Sep 17 2020, 2:07 PM
This revision was landed with ongoing or failed builds.Sep 17 2020, 2:21 PM
This revision was automatically updated to reflect the committed changes.
nikic added a subscriber: nikic.Nov 14 2020, 9:39 AM
nikic added inline comments.
llvm/include/llvm/Analysis/MemorySSA.h
1251

As the comment correctly states, an unknown size guarantees that locations after the pointer are considered as clobbers. However, locations before it are not. Could there still be an issue for decrementing pointer loops here?

fhahn added inline comments.Nov 15 2020, 10:04 AM
llvm/include/llvm/Analysis/MemorySSA.h
1251

It appears that currently things work out fine with decrementing pointers because of how BasicAA deals with negative offsets. And there are also a few checks that bail out if either size is unknown. I am not familiar enough with the walking code/the basicAA logic for those cases to judge if we just get lucky. In any case, I put up 7fa8b629208c which adds the decrement version of the test added here. Without the patch, it has the same issue as the increment version.

nikic added inline comments.Nov 15 2020, 11:48 AM
llvm/include/llvm/Analysis/MemorySSA.h
1251

Thanks for adding the test case! I believe that we are indeed getting lucky right now, in that BasicAA is currently slightly over-conservative when it comes to negative offsets, and it is thus hard to reproduce any issues. When I apply D91482 over the new test, it produces an incorrect liveOnEntry use. Assuming my understanding of LocationSize::unknown() is correct, that's an issue with this MemorySSA code rather than the patch.