Page MenuHomePhabricator

[MemorySSA] Be more conservative when traversing MemoryPhis.
ClosedPublic

Authored by fhahn on Wed, Sep 16, 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.Wed, Sep 16, 11:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Sep 16, 11:00 AM
Herald added a subscriber: Prazek. · View Herald Transcript
fhahn requested review of this revision.Wed, Sep 16, 11:00 AM
fhahn updated this revision to Diff 292338.Wed, Sep 16, 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–1270

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.Wed, Sep 16, 3:03 PM
llvm/include/llvm/Analysis/MemorySSA.h
1262–1270

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.Thu, Sep 17, 7:57 AM

use precise size for translated addr.

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

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.Thu, Sep 17, 12:30 PM
llvm/include/llvm/Analysis/MemorySSA.h
1262–1270

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.Thu, Sep 17, 1:17 PM

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

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

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.Thu, Sep 17, 2:07 PM
This revision is now accepted and ready to land.Thu, Sep 17, 2:07 PM
This revision was landed with ongoing or failed builds.Thu, Sep 17, 2:21 PM
This revision was automatically updated to reflect the committed changes.