Add a cache for DL.getTypeAllocSize() to BasicAA.

[jlebar]

Summary

getTypeAllocSize is surprisingly expensive. In my (private, sorry)
testcase, we spend 400ms in getTypeAllocSize out of a total of 3s in
BasicAA. After this change, this goes to 0, and I see no measurable
overhead from the hashtable lookup. Therefore this is a >1.1x speedup
to BasicAA, in my test.

[jlebar]

Use structured binding for iterator.

[nikic]

Compile-time on CTMark: http://llvm-compile-time-tracker.com/compare.php?from=71e52a125cb5f532192c40cf13692c18ede18cb4&to=14ba5930d47843050c2618b70c6cf6fc7d0fc66f&stat=instructions So not a great deal of impact end-to-end.

getTypeAllocSize() is indeed fairly expensive due to the ABI alignment calculation. I think a cache could generally make sense, though I wonder why it is BasicAA specific, and not part of DataLayout itself?

I would also be interested in whether the GEPs in your case are mostly constant offset GEPs. It's on my roadmap to canonicalize those to i8 GEPs, which would allow us to save on a lot of redundant offset calculation in both BasicAA and other places.

[jlebar]

I think a cache could generally make sense, though I wonder why it is BasicAA specific, and not part of DataLayout itself?

I was hesitant to add a cache on DataLayout because

• it's of unbounded size and lifetime (though I guess every Type that's created also permanently adds some memory usage in the LLVM context, so maybe this isn't an issue?). Whereas in here the lifetime is bounded by the lifetime of the BasicAAResult.
• in DataLayout, it's hard to justify why we cache getTypeAllocSize but not any of the other properties.
• this is clearly a win in BasicAA (in my benchmark) but like, who knows how people use DataLayout, maybe it's not a win for all ways one could use it.

That said I don't feel strongly! WDYT?

I would also be interested in whether the GEPs in your case are mostly constant offset GEPs. It's on my roadmap to canonicalize those to i8 GEPs, which would allow us to save on a lot of redundant offset calculation in both BasicAA and other places.

In my case I don't think they are. This is an XLA benchmark, so we tend to have 4D pointers where one or a few offsets are variable. Though I agree that canonicalization would help if they were all constant.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
   ///      alias(%p, %addr1) -> MayAlias !
   ///   store %l, ...
   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
 
   /// Tracks instructions visited by pointsToConstantMemory.
   SmallPtrSet<const Value *, 16> Visited;
 
-  static DecomposedGEP
-  DecomposeGEPExpression(const Value *V, const DataLayout &DL,
+  // Cache around DL.getTypeAllocSize(), which is surprisingly expensive.
+  DenseMap<const Type *, TypeSize> TypeAllocSizeCache;
+
+  // Returns DL.getTypeAllocSize() and inserts it into the cache if it's not
+  // present.
+  TypeSize GetTypeAllocSize(Type *Ty);
+
+  DecomposedGEP DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                        AssumptionCache *AC, DominatorTree *DT);
 
   /// A Heuristic for aliasGEP that searches for a constant offset
   /// between the variables.
   ///
   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
   /// will therefore conservatively refuse to decompose these expressions.
   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if

llvm/lib/Analysis/BasicAliasAnalysis.cpp

for (size_t i = 0; i < VarIndices.size(); i++) {
       if (i != 0)
         OS << ", ";
       VarIndices[i].print(OS);
     }
     OS << "])";
   }
 };
 
+TypeSize BasicAAResult::GetTypeAllocSize(Type *Ty) {
+  auto [it, inserted] = TypeAllocSizeCache.insert({Ty, TypeSize::Fixed(0)});
+  if (inserted) {
+    it->second = DL.getTypeAllocSize(Ty);
+  }
+  return it->second;
+}
 
 /// If V is a symbolic pointer expression, decompose it into a base pointer
 /// with a constant offset and a number of scaled symbolic offsets.
 ///
 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
 /// specified amount, but which may have other unrepresented high bits. As
 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
 BasicAAResult::DecomposedGEP
 BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                       AssumptionCache *AC, DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
   SearchTimes++;
   const Instruction *CxtI = dyn_cast<Instruction>(V);
 
   unsigned MaxIndexSize = DL.getMaxIndexSizeInBits();
   DecomposedGEP Decomposed;
   Decomposed.Offset = APInt(MaxIndexSize, 0);
+
   do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (!Op) {
       // The only non-operator case we can handle are GlobalAliases.
       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
         if (!GA->isInterposable()) {
           V = GA->getAliasee();
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero())
           continue;
 
         // Don't attempt to analyze GEPs if the scalable index is not zero.
-        TypeSize AllocTypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
+        TypeSize AllocTypeSize = GetTypeAllocSize(GTI.getIndexedType());
         if (AllocTypeSize.isScalable()) {
           Decomposed.Base = V;
           return Decomposed;
         }
 
         Decomposed.Offset += AllocTypeSize.getFixedSize() *
                              CIdx->getValue().sextOrTrunc(MaxIndexSize);
         continue;
       }
 
-      TypeSize AllocTypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
+      TypeSize AllocTypeSize = GetTypeAllocSize(GTI.getIndexedType());
       if (AllocTypeSize.isScalable()) {
         Decomposed.Base = V;
         return Decomposed;
       }
 
       GepHasConstantOffset = false;
 
       // If the integer type is smaller than the index size, it is implicitly