[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

457

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

464

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)

1696

This appears unused?

1702

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

1696

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

1706

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

1706

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

struct ClobberAlias {
   bool IsClobber;
   Optional<AliasResult> AR;
 };
 
 } // end anonymous namespace
 
 // Return a pair of {IsClobber (bool), AR (AliasResult)}. It relies on AR being
 // ignored if IsClobber = false.
-static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
+static ClobberAlias instructionClobbersQuery(const MemoryDef *MD,
                                              const MemoryLocation &UseLoc,
                                              const Instruction *UseInst,
                                              AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
   ImmutableCallSite UseCS(UseInst);
   Optional<AliasResult> AR;
 

 /// 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,
+static void
+checkClobberSanity(const 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;
   }
 
   bool FoundClobber = false;
-  DenseSet<MemoryAccessPair> VisitedPhis;
-  SmallVector<MemoryAccessPair, 8> Worklist;
+  DenseSet<ConstMemoryAccessPair> VisitedPhis;
+  SmallVector<ConstMemoryAccessPair, 8> Worklist;
   Worklist.emplace_back(Start, StartLoc);
   // Walk all paths from Start to ClobberAt, while looking for clobbers. If one
   // is found, complain.
   while (!Worklist.empty()) {
-    MemoryAccessPair MAP = Worklist.pop_back_val();
+    auto MAP = Worklist.pop_back_val();
     // All we care about is that nothing from Start to ClobberAt clobbers Start.
     // We learn nothing from revisiting nodes.
     if (!VisitedPhis.insert(MAP).second)
       continue;
 
-    for (MemoryAccess *MA : def_chain(MAP.first)) {
+    for (const auto *MA : def_chain(MAP.first)) {
       if (MA == ClobberAt) {
-        if (auto *MD = dyn_cast<MemoryDef>(MA)) {
+        if (const auto *MD = dyn_cast<MemoryDef>(MA)) {
           // instructionClobbersQuery isn't essentially free, so don't use `|=`,
           // since it won't let us short-circuit.
           //
           // Also, note that this can't be hoisted out of the `Worklist` loop,
           // since MD may only act as a clobber for 1 of N MemoryLocations.
           FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MD);
           if (!FoundClobber) {
             ClobberAlias CA =
                 instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
             if (CA.IsClobber) {
               FoundClobber = true;
               // Not used: CA.AR;
             }
           }
         }
         break;
       }
 
       // We should never hit liveOnEntry, unless it's the clobber.
       assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
 
-      if (auto *MD = dyn_cast<MemoryDef>(MA)) {
+      // If Start is a Def, skip self.
+      if (MA == Start)
+        continue;
+
+      if (const 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());
+      Worklist.append(
+          upward_defs_begin({const_cast<MemoryAccess *>(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;