[MemorySSA] Add caching results of reaching LiveOnEntry MemoryDef to ClobberWalker

[eastig]

Summary

There is the project VIXL (https://git.linaro.org/arm/vixl.git), AArch32 and AArch64 Runtime Code Generation Library. The library is used by such projects as AOSP and HHVM. The library has C++ sources which trigger quadratic running time in MemorySSA.
For example, the compilation time of https://git.linaro.org/arm/vixl.git/tree/test/aarch32/test-assembler-cond-rd-operand-rn-in-it-block-t32.cc is 5 minutes. G++ 5.4 compiles it in 17 seconds. The file contains a big global array of structs for which an initialiser is generated. The issue was found by Google. At the moment a workaround to turn optimisations off for the sources is used: https://android.googlesource.com/platform/external/vixl/+/master/test/aarch32/test-utils-aarch32.h.

This patch is a prototype of caching some results in ClobberWalker. The idea of caching is based on a pattern I have seen. When there is a walk path leading to a LiveOnEntry MemoryDef its result can be reused as soon as we get on the path again.

The patch reduces the compilation time from 5 minutes to 25 seconds.
Command to reproduce:

clang++ -c -Wall -Werror -fdiagnostics-show-option -Wextra -Wredundant-decls -pedantic -Wwrite-strings -Wunused -DVIXL_INCLUDE_TARGET_A32 -DVIXL_INCLUDE_TARGET_T32 -DVIXL_INCLUDE_TARGET_A64 -O3 -DVIXL_CODE_BUFFER_MMAP -DVIXL_INCLUDE_SIMULATOR_AARCH64 -Wmissing-noreturn  -Wunreachable-code -Wno-long-long -Wno-variadic-macros -Isrc -Itest test/aarch32/test-assembler-cond-rd-operand-rn-in-it-block-t32.cc

Testing results:

1. check-all passed
2. VIXL tests passed
3. Bootstrapped clang
   1. check-all passed
   2. VIXL tests passed

[george.burgess.iv]

Thanks for this!

It's unrelated to the general problem here, but for this repro in particular, it looks pretty simple to reduce compile time to ~2 seconds on clang ToT. Clang needs to emit a dynamic initializer for kTests because neither Condition nor Register are constexpr. If you tag kTests with [[clang::require_constant_initialization]] and address the complaints it has, it looks like just a handful of additions of constexpr will allow clang to elide the dynamic initializer entirely.

Back on topic, since we already keep per-Memory{Use,Def} caches of where things point to, and keeping up with those has been a constant source of bugs, I'm pretty reluctant to have a second cache here to have to reason about.

We originally had a similar cache embedded inside of the clobber walker (https://reviews.llvm.org/D31576). It was removed because it was a net loss (or neutral) in cycles and memory in all of the cases we could find. In general, for caches where you can't trivially figure out the things that point to a cached clobber (as we have here), we're in the unfortunate situation of needing to drop the entire thing on basically every meaningful update of any MemoryAccess, which makes it difficult for them to provide great value in general.

Looking at the repro, it appears that, after optimizations, we end up with a single basic block that consists of over 20,000 (!) lines of IR. Around 19,000 of these are stores. So, it makes sense that our current walker spins a lot for this. :)

When we first landed MemorySSA, there were talks about flagging pathological blocks like that and just refusing to walk/optimize them at all. For the reasons detailed above, I'd strongly prefer we do that over keeping a cache, unless a new cache is a very solid win in general. If you find that idea reasonable, it looks like the MaxCheckLimit flag is only respected in our OptimizeUses walker; I'd be happy to have some logic in our CachingWalker that says "if we walk more than MaxCheckLimit defs in a single block, give up."

What do you think?

lib/Analysis/MemorySSA.cpp

599

If we end up going forward with this, please make caching optional, so that we can have an EXPENSIVE_CHECKS assert to verify that we get the same result with/without our cache (without dropping our cache), as we did before.

[eastig]

Hi George,

Thank you for the comments and advice.

There is a problem with using constexpr. The VIXL library is built with c++98 by default. I'll speak to VIXL developers whether it is still a requirement.

I agree with you any caching is a source of bugs. I prefer using heuristics to adding functionality producing bugs.
I am not sure the current caching prototype is bug-free. I made some assumptions which might not be always true.

As the case is definitely pathological I'd be happy to have some kind of heuristics to filter it out.
I appreciate if someone familiar with the MemorySSA code adds the heuristics. If everyone is busy, I can try to do.

Thanks,
Evgeny

[asbirlea]

FWIW, the cause of the slowdown is the usage of MemorySSA in EarlyCSE.
Here's an alternative solution: D58248.
On my machine compile time goes from ~41s to ~11s (with vixl ToT today).

[eastig]

In D56720#1398464, @asbirlea wrote:

FWIW, the cause of the slowdown is the usage of MemorySSA in EarlyCSE.
Here's an alternative solution: D58248.
On my machine compile time goes from ~41s to ~11s (with vixl ToT today).

Thank you, Alina, for working on this.

lib/Analysis/MemorySSA.cpp

checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt,
   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 {
+class CachingClobberWalker {
   /// 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;
     Optional<ListIndex> Previous;
 
     DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
             Optional<ListIndex> Previous)
         : Loc(Loc), First(First), Last(Last), Previous(Previous) {}
 
     DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
             Optional<ListIndex> Previous)
         : DefPath(Loc, Init, Init, Previous) {}
   };
 
+  /// Result of calling walkToPhiOrClobber.
+  struct UpwardsWalkResult {
+    /// The "Result" of the walk. Either a clobber, the last thing we walked, or
+    /// both. Include alias info when clobber found.
+    MemoryAccess *Result;
+    bool IsKnownClobber;
+    Optional<AliasResult> AR;
+  };
+
+  // Walk paths can share parts leading to the same results.
+  // As soon as we get to the path which has a known result
+  // we can stop and use the result.
+  // We define a walk path part as a pair of MemoryDef and MemoryLocation.
+  // To cache walk results we distinguish walks path by their DefPath.Last
+  // and DefPath.Loc.
+  // When a path part is processed we check which path it has appeared first.
+  // If such a path exists, the result of the path is used.
+  class WalkResultsCache {
+  public:
+    using WalkPathIdTy = const MemoryAccess *;
+
+    WalkResultsCache() = default;
+    WalkResultsCache(const WalkResultsCache &) = delete;
+    WalkResultsCache &operator=(const WalkResultsCache &) = delete;
+
+    void startPath(const DefPath &Desc) {
+      CurrentWalkPathId = Desc.Last;
+      CurrentMemLocId =
+          SeenMemLocations
+              .insert(std::make_pair(Desc.Loc, SeenMemLocations.size()))
+              .first->second;
+    }
+
+    std::pair<WalkPathIdTy, bool> registerMemoryDef(const MemoryDef *MD) {
+      WalkPathPartTy CurrentPathPart{MD, CurrentMemLocId};
+      auto InsertResult = PathsFirstTimeAppeared.insert(
+          std::make_pair(CurrentPathPart, CurrentWalkPathId));
+      return (InsertResult.second)
+                 ? std::make_pair(InsertResult.first->second, false)
+                 : std::make_pair(
+                       InsertResult.first->second,
+                       WalkResults.count(InsertResult.first->second) == 1);
+    }
+
+    UpwardsWalkResult getResult(WalkPathIdTy PathId) {
+      assert(WalkResults.count(PathId) == 1 &&
+             "No result in cache for the provided walk path id.");
+      return WalkResults[PathId];
+    }
+
+    void cacheResultForCurrentPath(const UpwardsWalkResult &Result) {
+      WalkResults.insert(std::make_pair(CurrentWalkPathId, Result));
+    }
+
+    void clear() {
+      SeenMemLocations.clear();
+      PathsFirstTimeAppeared.clear();
+      WalkResults.clear();
+    }
+
+  private:
+    // To save memory we keep a track of memory locations we've seen.
+    using MemLocationIdTy = unsigned;
+    using SeenMemLocationsTy = DenseMap<MemoryLocation, MemLocationIdTy>;
+    using WalkPathPartTy = std::pair<const MemoryDef *, MemLocationIdTy>;
+    using PathsFirstTimeAppearedTy = DenseMap<WalkPathPartTy, WalkPathIdTy>;
+    using WalkResultsTy = DenseMap<WalkPathIdTy, UpwardsWalkResult>;
+
+    MemLocationIdTy CurrentMemLocId;
+    WalkPathIdTy CurrentWalkPathId;
+    SeenMemLocationsTy SeenMemLocations;
+    PathsFirstTimeAppearedTy PathsFirstTimeAppeared;
+    WalkResultsTy WalkResults;
+  };
+
   const MemorySSA &MSSA;
   AliasAnalysis &AA;
   DominatorTree &DT;
   UpwardsMemoryQuery *Query;
 
   // Phi optimization bookkeeping
   SmallVector<DefPath, 32> Paths;
   DenseSet<ConstMemoryAccessPair> VisitedPhis;
 
   /// Find the nearest def or phi that `From` can legally be optimized to.
   const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
     assert(From->getNumOperands() && "Phi with no operands?");
 
     BasicBlock *BB = From->getBlock();
     MemoryAccess *Result = MSSA.getLiveOnEntryDef();
     DomTreeNode *Node = DT.getNode(BB);
     while ((Node = Node->getIDom())) {
       auto *Defs = MSSA.getBlockDefs(Node->getBlock());
       if (Defs)
         return &*Defs->rbegin();
     }
     return Result;
   }
 
-  /// Result of calling walkToPhiOrClobber.
-  struct UpwardsWalkResult {
-    /// The "Result" of the walk. Either a clobber, the last thing we walked, or
-    /// both. Include alias info when clobber found.
-    MemoryAccess *Result;
-    bool IsKnownClobber;
-    Optional<AliasResult> AR;
-  };
+  WalkResultsCache CachedResults;
 
   /// 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 MemoryAccess *SkipStopAt = nullptr) const {
+                     const MemoryAccess *SkipStopAt = nullptr) {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
 
+    CachedResults.startPath(Desc);
+
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
       if (Current == StopAt || Current == SkipStopAt)
         return {Current, false, MayAlias};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
-        if (MSSA.isLiveOnEntryDef(MD))
-          return {MD, true, MustAlias};
+        bool HasResult;
+        WalkResultsCache::WalkPathIdTy PathId;
+        std::tie(PathId, HasResult) = CachedResults.registerMemoryDef(MD);
+        if (HasResult) {
+          UpwardsWalkResult Result{CachedResults.getResult(PathId)};
+          Desc.Last = Result.Result;
+          CachedResults.cacheResultForCurrentPath(Result);
+          return Result;
+        }
+
+        if (MSSA.isLiveOnEntryDef(MD)) {
+          UpwardsWalkResult Result{MD, true, MustAlias};
+          CachedResults.cacheResultForCurrentPath(Result);
+          return Result;
+        }
         ClobberAlias CA =
             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
         if (CA.IsClobber)
           return {MD, true, CA.AR};
       }
     }
 
     assert(isa<MemoryPhi>(Desc.Last) &&
class CachingClobberWalker {
 
   private:
     T &curNode() const { return W->Paths[*N]; }
 
     Walker *W = nullptr;
     Optional<ListIndex> N = None;
   };
 
-  using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
+  using def_path_iterator = generic_def_path_iterator<DefPath, CachingClobberWalker>;
   using const_def_path_iterator =
-      generic_def_path_iterator<const DefPath, const ClobberWalker>;
+      generic_def_path_iterator<const DefPath, const CachingClobberWalker>;
 
   iterator_range<def_path_iterator> def_path(ListIndex From) {
     return make_range(def_path_iterator(this, From), def_path_iterator());
   }
 
   iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const {
     return make_range(const_def_path_iterator(this, From),
                       const_def_path_iterator());
class CachingClobberWalker {
   }
 
   void resetPhiOptznState() {
     Paths.clear();
     VisitedPhis.clear();
   }
 
 public:
-  ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT)
+  CachingClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT)
       : MSSA(MSSA), AA(AA), DT(DT) {}
 
   /// Finds the nearest clobber for the given query, optimizing phis if
   /// possible.
   MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) {
     Query = &Q;
 
     MemoryAccess *Current = Start;

 #ifdef EXPENSIVE_CHECKS
     if (!Q.SkipSelfAccess)
       checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 #endif
     return Result;
   }
 
   void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA); }
+
+  void resetCache() {
+    CachedResults.clear();
+  }
 };
 
 struct RenamePassData {
   DomTreeNode *DTN;
   DomTreeNode::const_iterator ChildIt;
   MemoryAccess *IncomingVal;
 
   RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
                  MemoryAccess *M)
       : DTN(D), ChildIt(It), IncomingVal(M) {}
 
   void swap(RenamePassData &RHS) {
     std::swap(DTN, RHS.DTN);
     std::swap(ChildIt, RHS.ChildIt);
     std::swap(IncomingVal, RHS.IncomingVal);
   }
 };
 
 } // end anonymous namespace
 
 namespace llvm {
 
 class MemorySSA::ClobberWalkerBase {
-  ClobberWalker Walker;
+  CachingClobberWalker Walker;
   MemorySSA *MSSA;
 
 public:
   ClobberWalkerBase(MemorySSA *M, AliasAnalysis *A, DominatorTree *D)
       : Walker(*M, *A, *D), MSSA(M) {}
 
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
                                               const MemoryLocation &);
   // Second argument (bool), defines whether the clobber search should skip the
   // original queried access. If true, there will be a follow-up query searching
   // for a clobber access past "self". Note that the Optimized access is not
   // updated if a new clobber is found by this SkipSelf search. If this
   // additional query becomes heavily used we may decide to cache the result.
   // Walker instantiations will decide how to set the SkipSelf bool.
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, bool);
   void verify(const MemorySSA *MSSA) { Walker.verify(MSSA); }
+  void invalidateInfo(MemoryAccess *) {
+    Walker.resetCache();
+  }
 };
 
 /// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
 /// longer does caching on its own, but the name has been retained for the
 /// moment.
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
   ClobberWalkerBase *Walker;
 
 public:
   CachingWalker(MemorySSA *M, ClobberWalkerBase *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~CachingWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override;
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
+    Walker->invalidateInfo(MA);
   }
 
   void verify(const MemorySSA *MSSA) override {
     MemorySSAWalker::verify(MSSA);
     Walker->verify(MSSA);
   }
 };
 
public:
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override;
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
+    Walker->invalidateInfo(MA);
   }
 
   void verify(const MemorySSA *MSSA) override {
     MemorySSAWalker::verify(MSSA);
     Walker->verify(MSSA);
   }
 };