[AliasAnalysis] Cache the results of TBAA.

nadavrot · nadavrot · commit a07da67d6f84 · 2015-11-23T22:20:37.000-08:00
Add a cache for calls to typesMayAlias. We never invalidate this cache
because type aliasing relations never change.

The hit rate of this cache is really high.
diff --git a/include/swift/SILAnalysis/AliasAnalysis.h b/include/swift/SILAnalysis/AliasAnalysis.h
@@ -59,6 +59,15 @@ class AliasAnalysis : public SILAnalysis {
   SILModule *Mod;
   SideEffectAnalysis *SEA;
 
+  using TBAACacheKey = std::pair<SILType, SILType>;
+
+  /// A cache for the computation of TBAA. True means that the types may
+  /// alias. False means that the types must not alias.
+  ///
+  /// We don't need to invalidate this cache because type aliasing relations
+  /// never change.
+  llvm::DenseMap<TBAACacheKey, bool> TypesMayAliasCache;
+
   using MemoryBehavior = SILInstruction::MemoryBehavior;
 
   AliasResult aliasAddressProjection(SILValue V1, SILValue V2,
@@ -68,6 +77,10 @@ class AliasAnalysis : public SILAnalysis {
   AliasResult aliasInner(SILValue V1, SILValue V2,
                          SILType TBAAType1 = SILType(),
                          SILType TBAAType2 = SILType());  
+
+  /// Returns True if memory of type \p T1 and \p T2 may alias.
+  bool typesMayAlias(SILType T1, SILType T2);
+
 public:
   AliasAnalysis(SILModule *M) :
     SILAnalysis(AnalysisKind::Alias), Mod(M), SEA(nullptr) {}
diff --git a/lib/SILAnalysis/AliasAnalysis.cpp b/lib/SILAnalysis/AliasAnalysis.cpp
@@ -585,16 +585,21 @@ static bool typedAccessTBAAMayAlias(SILType LTy, SILType RTy, SILModule &Mod) {
   return true;
 }
 
-static bool typesMayAlias(SILType T1, SILType T2, SILType TBAA1Ty,
-                          SILType TBAA2Ty, SILModule &Mod) {
-  // Perform type access based TBAA if we have TBAA info.
-  if (TBAA1Ty && TBAA2Ty)
-    return typedAccessTBAAMayAlias(TBAA1Ty, TBAA2Ty, Mod);
+bool AliasAnalysis::typesMayAlias(SILType T1, SILType T2) {
+  // Both types need to be valid.
+  if (!T2 || !T1)
+    return true;
 
-  // Otherwise perform class based TBAA on the passed in refs.
-  //
-  // FIXME: Implement class based TBAA.
-  return true;
+  // Check if we've already computed the TBAA relation.
+  auto Key = std::make_pair(T1, T2);
+  auto Res = TypesMayAliasCache.find(Key);
+  if (Res != TypesMayAliasCache.end()) {
+    return Res->second;
+  }
+
+  bool MA = typedAccessTBAAMayAlias(T1, T2, *Mod);
+  TypesMayAliasCache[Key] = MA;
+  return MA;
 }
 
 //===----------------------------------------------------------------------===//
@@ -629,7 +634,7 @@ AliasResult AliasAnalysis::aliasInner(SILValue V1, SILValue V2,
 
   // Pass in both the TBAA types so we can perform typed access TBAA and the
   // actual types of V1, V2 so we can perform class based TBAA.
-  if (!typesMayAlias(V1.getType(), V2.getType(), TBAAType1, TBAAType2, *Mod))
+  if (!typesMayAlias(TBAAType1, TBAAType2))
     return AliasResult::NoAlias;
 
 #ifndef NDEBUG
