[MemorySSA] Fix bug in CachingMemorySSAWalker::getClobberingMemoryAccess.

[gberry]

Summary

For the Instruction version of
CachingMemorySSAWalker::getClobberingMemoryAccess, when checking the
cache for previously computed values, the key used was I's MemoryAccess,
instead of its defining access. If a previous call to the
non-instruction version of getClobberingMemoryAccess has been called, it
will have added I's MemoryAccess itself as the cached result (in the
case it is a MemoryDef).

For example, for the following code:

1 = MemoryDef(liveOnEntry)
store %a

before this change (assuming the calls to getClobberingMemoryAccess are
made in order):

MSSA.getClobberingMemoryAccess(MSSA.getMemoryAccess(I), IMemLoc)
  -> 1 = MemoryDef(liveOnEntry)
MSSA.getClobberingMemoryAccess(I)
  -> 1 = MemoryDef(liveOnEntry)

after this change, the second call correctly returns 'liveOnEntry':

MSSA.getClobberingMemoryAccess(MSSA.getMemoryAccess(I), IMemLoc)
  -> 1 = MemoryDef(liveOnEntry)
MSSA.getClobberingMemoryAccess(I)
  -> liveOnEntry

[gberry]

I didn't include a test case because I'm not sure of a good way to test this. Any ideas would be welcome.

[george.burgess.iv]

FWIW, the only way I know of to test this would be to make a unittest.

---

What happens if we have a chain like:

%1 = alloca i8
; 1 = MemoryDef(liveOnEntry)
store i8 0, i8* %1
; 2 = MemoryDef(1)
store i8 1, i8* %1
; 3 = MemoryDef(2)
store i8 2, i8* %1

And query from top to bottom using getClobberingMemoryAccess(const Instruction *)? I *believe* that our behavior will be:

• First store: Get MD#1's clobber, liveOnEntry, return it without caching anything.
• Second store: Get MD#2's clobber, MD#1, find nothing in cache, determine the clobber is MD#1, cache {MD#2, %1} -> MD#1.
• Third store: Get MD#3's clobber, MD#2, find {MD#2, %1} -> MD#1 in cache, return MD#1.

...Which isn't correct.

That said, I'm not so sure that having two functions that can cache different results for (what ultimately are) the same queries is a great idea. As a quick fix, maybe just not caching the final result for getClobberingMemoryAccess(MA*, MemLoc&) would work? (We'd have to make sure the Walker's caching loop doesn't try to cache this for us as well, if we decide to do this.)

[george.burgess.iv]

...And it looks like this behavior already exists in the walker anyway (because we consult the cache first). Yay.

I'll take a shot at fixing it, and add tests for cases like this.

[• dberlin]

So will you do a superset or should we approve this patch.

In retrospect, we should have added caching later with more full unit
tests, given how complex it ends up

[george.burgess.iv]

So will you do a superset or should we approve this patch.

I planned to just fix the walker, but that ended up being a fix for two different-but-related bugs that seemingly also fixes this problem for free, so superset I guess. Sorry for hijacking this, @gberry; it wasn't my intention to do so. :/ (And thanks for bringing this issue up! :) )

I plan to have the fix upstreamed by noon-ish PST tomorrow.

The bugs ended up being:

• Cache[Foo] gives us the clobber of Foo. So, if DefiningAccess is the clobber for Q.OriginalAccess, and we start walking with DefiningAccess, we look for Cache[DefiningAccess] before checking if DefiningAccess is a clobber.
• We would (sometimes in the DFS, sometimes in the getClobbering... methods) at times cache a MemoryAccess as a clobber for itself. Sometimes this is fine (e.g. Phis we can't optimize), but for Defs, it isn't.

In retrospect, we should have added caching later with more full unit tests, given how complex it ends up

Agreed. Also, when I was adding the tests, I probably should have added more variety in the tests, as well. Just focusing on MemoryUse optimization turned out to cover way less than I thought it would.

[gberry]

@george.burgess.iv No problem. Thanks for fixing my fix.

lib/Transforms/Utils/MemorySSA.cpp

CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
   auto *StartingAccess = cast<MemoryUseOrDef>(MSSA->getMemoryAccess(I));
 
   // We can't sanely do anything with a FenceInst, they conservatively
   // clobber all memory, and have no locations to get pointers from to
   // try to disambiguate
   if (isa<FenceInst>(I))
     return StartingAccess;
 
+  // Start with the thing we already think clobbers this location
+  MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
+
+  // At this point, DefiningAccess may be the live on entry def.
+  // If it is, we will not get a better result.
+  if (MSSA->isLiveOnEntryDef(DefiningAccess))
+    return DefiningAccess;
+
   UpwardsMemoryQuery Q;
   Q.OriginalAccess = StartingAccess;
   Q.IsCall = bool(ImmutableCallSite(I));
   if (!Q.IsCall)
     Q.StartingLoc = MemoryLocation::get(I);
   Q.Inst = I;
   Q.DL = &Q.Inst->getModule()->getDataLayout();
-  if (auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc))
+  if (auto CacheResult = doCacheLookup(DefiningAccess, Q, Q.StartingLoc))
     return CacheResult;
 
-  // Start with the thing we already think clobbers this location
-  MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
-
-  // At this point, DefiningAccess may be the live on entry def.
-  // If it is, we will not get a better result.
-  if (MSSA->isLiveOnEntryDef(DefiningAccess))
-    return DefiningAccess;
-
   MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
   doCacheInsert(Q.OriginalAccess, Result, Q, Q.StartingLoc);
   // TODO: When this implementation is more mature, we may want to figure out
   // what this additional caching buys us. It's most likely A Good Thing.
   if (Q.IsCall)
     for (const MemoryAccess *MA : Q.VisitedCalls)
       doCacheInsert(MA, Result, Q, Q.StartingLoc);