[MemorySSA] Extend the clobber walker with the option to skip the starting access.

[asbirlea]

Summary

The option enables loop transformations to hoist accesses that do not
have clobbers in the loop. If the clobber queries skips the starting
access, the result may be outside the loop instead of the header Phi.

Adding the walker that uses this option in a separate patch.

[george.burgess.iv]

Thanks for this! I like it when patches are small and split up like this one :)

I'd rather not check in dynamically dead code, though. Can we please hold off on committing this until the patch that makes this un-dead is approved and such?

lib/Analysis/MemorySSA.cpp

625

Is it sensible to have SkipSelfAccess with Query->OriginalAccess == null?

628

Can we move this assert where we plan to set Query->SkipSelfAccess to true?

That way, it'll fire 100% of the time if there's a bug, rather than only if we reach this piece of code

(I realize that'll be in the follow-up patch. Still. :) )

646–650

Please add a short comment explaining why this if exists, since I feel like I'm likely to forget the trickiness we're doing here, and it would help any future readers of the code.

[asbirlea]

Address comments.

[asbirlea]

Ack, will hold off on checking this in until the follow-up use (walker) is finalized.

lib/Analysis/MemorySSA.cpp

625

AFAICT Query->OriginalAccess is never null, so no, not currently. Removing check.

628

Ack, noted to include in follow-up patch.

[asbirlea]

Update setting of where to stop in getBlockingAccess:

• dropping the check for block since we may no longer be in the starting block after adding a paused path.
• adding a second StopAt access in walkToPhiOrClobber, only set when skipping self and for the same location.
• keeping paused path when the original StopAt is found.

[george.burgess.iv]

LGTM; thanks again.

When we have code in a transformation that uses this new walker, please include a test specifically for the SkipStopWhere case that your most recent patchset fixes.

[asbirlea]

Thank you for the review!

Yes, I already have a testcase to include in the patch using the new walker.

lib/Analysis/MemorySSA.cpp

struct UpwardsMemoryQuery {
   // The pointer location we started the query with. This will be empty if
   // IsCall is true.
   MemoryLocation StartingLoc;
   // This is the instruction we were querying about.
   const Instruction *Inst = nullptr;
   // The MemoryAccess we actually got called with, used to test local domination
   const MemoryAccess *OriginalAccess = nullptr;
   Optional<AliasResult> AR = MayAlias;
+  bool SkipSelfAccess = false;
 
   UpwardsMemoryQuery() = default;
 
   UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
   }
class ClobberWalker {
   };
 
   /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
   /// This will update Desc.Last as it walks. It will (optionally) also stop at
   /// StopAt.
   ///
   /// This does not test for whether StopAt is a clobber
   UpwardsWalkResult
-  walkToPhiOrClobber(DefPath &Desc,
-                     const MemoryAccess *StopAt = nullptr) const {
+  walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
+                     const MemoryAccess *SkipStopAt = nullptr) const {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
 
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
-      if (Current == StopAt)
+      if (Current == StopAt || Current == SkipStopAt)
         return {Current, false, MayAlias};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
         if (MSSA.isLiveOnEntryDef(MD))
           return {MD, true, MustAlias};
         ClobberAlias CA =
             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
         if (CA.IsClobber)
while (!PausedSearches.empty()) {
       //     without needing cache entries for {C, MemLoc}, then chances are
       //     that those cache entries would end up ultimately unused.
       //   - We still cache things for A, so C only needs to walk up a bit.
       // If this behavior becomes problematic, we can fix without a ton of extra
       // work.
       if (!VisitedPhis.insert({Node.Last, Node.Loc}).second)
         continue;
 
-      UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere);
+      const MemoryAccess *SkipStopWhere = nullptr;
+      if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
+        assert(isa<MemoryDef>(Query->OriginalAccess));
+        SkipStopWhere = Query->OriginalAccess;
+      }
+
+      UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere,
+                                                 /*SkipStopAt=*/SkipStopWhere);
       if (Res.IsKnownClobber) {
-        assert(Res.Result != StopWhere);
+        assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
         // If this wasn't a cache hit, we hit a clobber when walking. That's a
         // failure.
         TerminatedPath Term{Res.Result, PathIndex};
         if (!MSSA.dominates(Res.Result, StopWhere))
           return Term;
 
         // Otherwise, it's a valid thing to potentially optimize to.
         Terminated.push_back(Term);
         continue;
       }
 
-      if (Res.Result == StopWhere) {
+      if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
         // We've hit our target. Save this path off for if we want to continue
-        // walking.
+        // walking. If we are in the mode of skipping the OriginalAccess, and
+        // we've reached back to the OriginalAccess, do not save path, we've
+        // just looped back to self.
+        if (Res.Result == StopWhere)
           NewPaused.push_back(PathIndex);
         continue;
       }
 
       assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber");
       addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex);
     }
 
     return None;