Index: lib/Analysis/MemorySSA.cpp
===================================================================
--- lib/Analysis/MemorySSA.cpp
+++ lib/Analysis/MemorySSA.cpp
@@ -474,7 +474,7 @@
 
 /// 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;
 
@@ -497,6 +497,81 @@
         : 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;
@@ -521,14 +596,7 @@
     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
@@ -537,17 +605,32 @@
   /// 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)
@@ -685,9 +768,9 @@
     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());
@@ -887,7 +970,7 @@
   }
 
 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
@@ -925,6 +1008,10 @@
   }
 
   void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA); }
+
+  void resetCache() {
+    CachedResults.clear();
+  }
 };
 
 struct RenamePassData {
@@ -948,7 +1035,7 @@
 namespace llvm {
 
 class MemorySSA::ClobberWalkerBase {
-  ClobberWalker Walker;
+  CachingClobberWalker Walker;
   MemorySSA *MSSA;
 
 public:
@@ -965,6 +1052,9 @@
   // 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
@@ -987,6 +1077,7 @@
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
+    Walker->invalidateInfo(MA);
   }
 
   void verify(const MemorySSA *MSSA) override {
@@ -1012,6 +1103,7 @@
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
+    Walker->invalidateInfo(MA);
   }
 
   void verify(const MemorySSA *MSSA) override {