[MemorySSA] Add expesive check for validating clobber accesses.

[asbirlea]

Summary

Add validation of clobber accesses as expensive check.

[george.burgess.iv]

Thanks for this!

lib/Analysis/MemorySSA.cpp

456

LLVM_ATTRIBUTE_UNUSED is probably unneeded; we have a member function that calls this regardless of whether NDEBUG/EXPENSIVE_CHECKS are on

463

Is it reasonable to not involve the walker here at all? :)

I ask because, if EXPENSIVE_CHECKS are on, the walker should already be calling checkClobberSanity on everything it hands back. So I think the only coverage we need out of this "we have these accesses that report isOptimized() == true. Let's make sure that the optimization is valid." (which it might have been originally, but then the IR+MemorySSA were changed and now it's not)

1695

This appears unused?

1701

It seems a bit awkward that we're casting this to a MUD, then extracting the instruction, then looking the MUD back up, then casting it to a MUD (in checkClobberSanityInstruction).

Since this is the only user of checkClobberSanityInstruction, would it make sense to manually inline it in this function and simplify a bit?

[asbirlea]

Address comments. Undo const-ifies no longer needed.

[asbirlea]

lib/Analysis/MemorySSA.cpp

1695

I was using this locally in a unittest, but it doesn't make sense to have unittests assert, so removing it.

[asbirlea]

lib/Analysis/MemorySSA.cpp

1705

Nit: keep the const up until upward_defs_begin and const_cast there?
(Worklist can be ConstMemoryAccessPair).
This seemed cleaner, but I'm ok with it either way.

[george.burgess.iv]

LGTM after the requested nit. Thanks again!

lib/Analysis/MemorySSA.cpp

1705

Nit: keep the const up until upward_defs_begin and const_cast there?

Yes, please.

Also please add a FIXME or note that, given infinite free time, we should probably refactor to make upward_defs_iterator respect constness...

It's a slightly larger change, but it pushes this const_cast as close to the point of "here's where this isn't annotated with const but logically is" as we can easily get it, which makes the safety of the const_cast a bit easier to reason about IMO (and keeps the API a bit cleaner).

[asbirlea]

Fix nit.

[asbirlea]

Missed an update.

include/llvm/Analysis/MemorySSA.h

public:
   /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
   /// dominates Use \p B.
   bool dominates(const MemoryAccess *A, const Use &B) const;
 
   /// Verify that MemorySSA is self consistent (IE definitions dominate
   /// all uses, uses appear in the right places).  This is used by unit tests.
   void verifyMemorySSA() const;
 
+  /// Check clobber sanity for an access.
+  void checkClobberSanityAccess(const MemoryAccess *MA) const;
+
   /// Used in various insertion functions to specify whether we are talking
   /// about the beginning or end of a block.
   enum InsertionPlace { Beginning, End };
 
 protected:
   // Used by Memory SSA annotater, dumpers, and wrapper pass
   friend class MemorySSAAnnotatedWriter;
   friend class MemorySSAPrinterLegacyPass;
   friend class MemorySSAUpdater;
 
   void verifyDefUses(Function &F) const;
   void verifyDomination(Function &F) const;
   void verifyOrdering(Function &F) const;
   void verifyDominationNumbers(const Function &F) const;
+  void verifyClobberSanity(const Function &F) const;
 
   // This is used by the use optimizer and updater.
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
     auto It = PerBlockAccesses.find(BB);
     return It == PerBlockAccesses.end() ? nullptr : It->second.get();
   }
 
   // This is used by the use optimizer and updater.

lib/Analysis/MemorySSA.cpp

 /// inbetween `Start` and `ClobberAt` can clobbers `Start`.
 ///
 /// This is meant to be as simple and self-contained as possible. Because it
 /// uses no cache, etc., it can be relatively expensive.
 ///
 /// \param Start     The MemoryAccess that we want to walk from.
 /// \param ClobberAt A clobber for Start.
 /// \param StartLoc  The MemoryLocation for Start.
-/// \param MSSA      The MemorySSA isntance that Start and ClobberAt belong to.
+/// \param MSSA      The MemorySSA instance that Start and ClobberAt belong to.
 /// \param Query     The UpwardsMemoryQuery we used for our search.
 /// \param AA        The AliasAnalysis we used for our search.
-static void LLVM_ATTRIBUTE_UNUSED
-checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt,
-                   const MemoryLocation &StartLoc, const MemorySSA &MSSA,
-                   const UpwardsMemoryQuery &Query, AliasAnalysis &AA) {
+static void checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt,
+                               const MemoryLocation &StartLoc,
+                               const MemorySSA &MSSA,
+                               const UpwardsMemoryQuery &Query,
+                               AliasAnalysis &AA) {
   assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
 
   if (MSSA.isLiveOnEntryDef(Start)) {
     assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
            "liveOnEntry must clobber itself");
     return;
   }
 
for (MemoryAccess *MA : def_chain(MAP.first)) {
           }
         }
         break;
       }
 
       // We should never hit liveOnEntry, unless it's the clobber.
       assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
 
+      // If Start is a Def, skip self.
+      if (MA == Start)
+        continue;
+
       if (auto *MD = dyn_cast<MemoryDef>(MA)) {
         (void)MD;
         assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA)
                     .IsClobber &&
                "Found clobber before reaching ClobberAt!");
         continue;
       }
 
       assert(isa<MemoryPhi>(MA));
       Worklist.append(upward_defs_begin({MA, MAP.second}), upward_defs_end());
     }
   }
 
   // If ClobberAt is a MemoryPhi, we can assume something above it acted as a
   // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point.
   assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
          "ClobberAt never acted as a clobber");
 }
 
 namespace {
 
 /// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
 /// in one class.
 class ClobberWalker {
   /// Save a few bytes by using unsigned instead of size_t.
   using ListIndex = unsigned;
 
   /// Represents a span of contiguous MemoryDefs, potentially ending in a
   /// MemoryPhi.
   struct DefPath {
     MemoryLocation Loc;
     // Note that, because we always walk in reverse, Last will always dominate
     // First. Also note that First and Last are inclusive.
     MemoryAccess *First;
     MemoryAccess *Last;

 #endif
 
 void MemorySSA::verifyMemorySSA() const {
   verifyDefUses(F);
   verifyDomination(F);
   verifyOrdering(F);
   verifyDominationNumbers(F);
   Walker->verify(this);
+  verifyClobberSanity(F);
+}
+
+/// Check sanity of the clobbering instruction for access MA.
+void MemorySSA::checkClobberSanityAccess(const MemoryAccess *MA) const {
+  if (const auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
+    if (!MUD->isOptimized())
+      return;
+    auto *I = MUD->getMemoryInst();
+    auto Loc = MemoryLocation::getOrNone(I);
+    if (Loc == None)
+      return;
+    auto *Clobber = MUD->getOptimized();
+    UpwardsMemoryQuery Q(I, MUD);
+    checkClobberSanity(const_cast<MemoryUseOrDef *>(MUD), Clobber, *Loc, *this, Q, *AA);
+  }
+}
+
+void MemorySSA::verifyClobberSanity(const Function &F) const {
+#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
+  for (const BasicBlock &BB : F) {
+    const AccessList *Accesses = getBlockAccesses(&BB);
+    if (!Accesses)
+      continue;
+    for (const MemoryAccess &MA : *Accesses)
+      checkClobberSanityAccess(&MA);
+  }
+#endif
 }
 
 /// Verify that all of the blocks we believe to have valid domination numbers
 /// actually have valid domination numbers.
 void MemorySSA::verifyDominationNumbers(const Function &F) const {
 #ifndef NDEBUG
   if (BlockNumberingValid.empty())
     return;