Index: include/llvm/Analysis/AliasAnalysis.h
===================================================================
--- include/llvm/Analysis/AliasAnalysis.h
+++ include/llvm/Analysis/AliasAnalysis.h
@@ -303,7 +303,11 @@
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   IsCapturedCacheT IsCapturedCache;
 
-  AAQueryInfo() : AliasCache(), IsCapturedCache() {}
+  using MDNodePair = std::pair<const MDNode *, const MDNode *>;
+  using TBAACacheT = SmallDenseMap<MDNodePair, bool, 8>;
+  TBAACacheT TBAACache;
+
+  AAQueryInfo() : AliasCache(), IsCapturedCache(), TBAACache() {}
 };
 
 class BatchAAResults;
Index: include/llvm/Analysis/TypeBasedAliasAnalysis.h
===================================================================
--- include/llvm/Analysis/TypeBasedAliasAnalysis.h
+++ include/llvm/Analysis/TypeBasedAliasAnalysis.h
@@ -52,7 +52,7 @@
                            AAQueryInfo &AAQI);
 
 private:
-  bool Aliases(const MDNode *A, const MDNode *B) const;
+  bool Aliases(const MDNode *A, const MDNode *B, AAQueryInfo &AAQI);
   bool PathAliases(const MDNode *A, const MDNode *B) const;
 };
 
Index: lib/Analysis/TypeBasedAliasAnalysis.cpp
===================================================================
--- lib/Analysis/TypeBasedAliasAnalysis.cpp
+++ lib/Analysis/TypeBasedAliasAnalysis.cpp
@@ -373,7 +373,7 @@
     return AAResultBase::alias(LocA, LocB, AAQI);
 
   // If accesses may alias, chain to the next AliasAnalysis.
-  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
+  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA, AAQI))
     return AAResultBase::alias(LocA, LocB, AAQI);
 
   // Otherwise return a definitive result.
@@ -429,7 +429,7 @@
 
   if (const MDNode *L = Loc.AATags.TBAA)
     if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
-      if (!Aliases(L, M))
+      if (!Aliases(L, M, AAQI))
         return ModRefInfo::NoModRef;
 
   return AAResultBase::getModRefInfo(Call, Loc, AAQI);
@@ -443,7 +443,7 @@
 
   if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
     if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
-      if (!Aliases(M1, M2))
+      if (!Aliases(M1, M2, AAQI))
         return ModRefInfo::NoModRef;
 
   return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
@@ -470,7 +470,8 @@
 }
 
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
-                            const MDNode **GenericTag = nullptr);
+                            const MDNode **GenericTag = nullptr,
+                            AAQueryInfo *AAQI = nullptr);
 
 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
   const MDNode *GenericTag;
@@ -655,7 +656,10 @@
 /// overlap. If \arg GenericTag is not null, then on return it points to the
 /// most generic access descriptor for the given two.
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
-                            const MDNode **GenericTag) {
+                            const MDNode **GenericTag, AAQueryInfo *AAQI) {
+  if (GenericTag)
+    assert(!AAQI && "Cannot use BatchAA in TBAA when doing updates");
+
   if (A == B) {
     if (GenericTag)
       *GenericTag = A;
@@ -669,6 +673,14 @@
     return true;
   }
 
+  std::pair<AAQueryInfo::TBAACacheT::iterator, bool> Pair;
+  if (AAQI) {
+    AAQueryInfo::MDNodePair MDNodes(A, B);
+    Pair = AAQI->TBAACache.insert(std::make_pair(MDNodes, true));
+    if (!Pair.second)
+      return Pair.first->second;
+  }
+
   // Verify that both input nodes are struct-path aware.  Auto-upgrade should
   // have taken care of this.
   assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
@@ -692,19 +704,26 @@
   if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
                                CommonType, GenericTag, MayAlias) ||
       mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
-                               CommonType, GenericTag, MayAlias))
+                               CommonType, GenericTag, MayAlias)) {
+    if (AAQI)
+      Pair.first->second = MayAlias;
     return MayAlias;
+  }
 
   // Otherwise, we've proved there's no alias.
   if (GenericTag)
     *GenericTag = createAccessTag(CommonType);
+
+  if (AAQI)
+    Pair.first->second = false;
   return false;
 }
 
 /// Aliases - Test whether the access represented by tag A may alias the
 /// access represented by tag B.
-bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
-  return matchAccessTags(A, B);
+bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B,
+                                AAQueryInfo &AAQI) {
+  return matchAccessTags(A, B, nullptr, &AAQI);
 }
 
 AnalysisKey TypeBasedAA::Key;