Model cache size and associativity in TargetTransformInfo

[grosser]

Summary

We add the precise cache sizes and associativity for the following Intel
architectures:

• Penry
• Nehalem
• Westmere
• Sandy Bridge
• Ivy Bridge
• Haswell
• Broadwell
• Skylake
• Kabylake

Polly uses since several months a performance model for BLAS computations that
derives optimal cache and register tile sizes from cache and latency
information (based on ideas from "Analytical Modeling Is Enough for High-Performance BLIS", by Tze Meng Low published at TOMS 2016).
While bootstrapping this model, these target values have been kept in Polly.
However, as our implementation is now rather mature, it seems time to teach
LLVM itself about cache sizes.

Interestingly, L1 and L2 cache sizes are pretty constant across
micro-architectures, hence a set of architecture specific default values
seems like a good start. They can be expanded to more target specific values,
in case certain newer architectures require different values. For now a set
of Intel architectures are provided.

Just as a little teaser, for a simple gemm kernel this model allows us to
improve performance from 1.2s to 0.27s. For gemm kernels with less optimal
memory layouts even larger speedups can be reported.

[grosser]

Hi Florian, hi Sebastian, Eli,

I added you in case you also would like to provide feedback.

Best,
Tobias

[gareevroman]

information (based on ideas from "Analytical Models for the BLIS Framework").

Could you add the reference to the paper to the summary?

[gareevroman]

I think throughput and latency of vector fma instructions are pretty constant across micro-architectures too. Can we also add them?

Sorry, probably, it’d require to specify it for each architecture.

[asb]

include/llvm/Analysis/TargetTransformInfo.h

607

It's conceivable that targets might want to differentiate between the I-cache and D-cache. e.g an embedded target may use info on the I-cache to guide custom code layout optimisations.

Is it worth starting with CL_L1D and CL_L2D instead?

include/llvm/Analysis/TargetTransformInfoImpl.h

348

Either the comment or the calculation is incorrect!

lib/Target/X86/X86TargetTransformInfo.cpp

92

Either the comment or the calculation is incorrect!

lib/Target/X86/X86TargetTransformInfo.h

49

Why not implement getCacheAssociativity too?

[grosser]

Incorporate asb's comments.

• Use 'D' postfix to clarify we talk about the data caches
• Fix typo in cache size
• Implement associativity for X86

[grosser]

Hi Alex, hi Roman,

thanks for your feedback. I addressed your comments.

Best,
Tobias

include/llvm/Analysis/TargetTransformInfo.h

607

Very good point. I changed this.

include/llvm/Analysis/TargetTransformInfoImpl.h

348

The calculation was wrong. I fixed this.

lib/Target/X86/X86TargetTransformInfo.cpp

92

The calculation. Fixed.

lib/Target/X86/X86TargetTransformInfo.h

49

Added!

[grosser]

Add a newline between two functions

[fhahn]

include/llvm/Analysis/TargetTransformInfoImpl.h

343

Maybe it would be safer to be conservative and return 0 here, similar to what getCacheLineSize does currently? That allows passes to check if the target provides accurate information ( != 0).

For example, for ARM Cortex cores the level 1 cache size can vary between 0KByte and 64KByte. [1], [2]

Also, we already have getCacheLineSize. Would it make sense to express the cache size in terms of cache lines, (eg X * Cache line size)? That would make it slightly easier to keep them in sync and avoid situations where getCacheSize() is not a multiple of getCacheLineSize()

[1] https://en.wikipedia.org/wiki/Comparison_of_ARMv8-A_cores
[2] https://en.wikipedia.org/wiki/ARM_Cortex-M

[asb]

include/llvm/Analysis/TargetTransformInfoImpl.h

343

I wondered about returning 0 too, but also think we need a new sentinel value. This function should be able to indicate 1) cache is known size X, 2) cache is unknown size, 3) cache is known size 0 (e.g. there is no L2).

[grosser]

Make return values optional to be able to distinguish between unknown cache
size and no cache.

We use Optional in the very same way to indicate clearly that no associativity
has been specified.

[grosser]

In D37051#849798, @gareevroman wrote:

I think throughput and latency of vector fma instructions are pretty constant across micro-architectures too. Can we also add them?

Sorry, probably, it’d require to specify it for each architecture.

We could do this. Some of the backend experts might be able to help you how to do this best. I think we should do this in a separate patch. Care to propose one?

include/llvm/Analysis/TargetTransformInfoImpl.h

343

I changed this to llvm::Optional.

[grosser]

Thanks for the useful comments. I now use optional. I am not convinced regarding the cache size in multiples of cache lines. This seems to always require conversions in case we want the actual size in bytes. At least for us, this is the more common value, I believe.

What do other's think. Size in bytes or in cache lines? In the end it's the same information. (We could also add size in bytes for now and add an assert that checks that the returned result (if any) is always a multiple of the cache line size. If somebody needs this information in cache lines, we can always add a helper method.

[asb]

Size in bytes makes most sense to me. The first thing any caller is going to do is convert away from cache lines to bytes or kilobytes anyway.

[fhahn]

In D37051#850696, @asb wrote:

Size in bytes makes most sense to me. The first thing any caller is going to do is convert away from cache lines to bytes or kilobytes anyway.

Agreed, Returning the number of cache lines as result of getCacheSize wouldn't be a good idea.

I meant using the cache line size in X86TTIImpl::getCacheSize. This was just a minor potential nit, I think either way is fine.

[asb]

In D37051#850795, @fhahn wrote:

Agreed, Returning the number of cache lines as result of getCacheSize wouldn't be a good idea.

I meant using the cache line size in X86TTIImpl::getCacheSize. This was just a minor potential nit, I think either way is fine.

Ah, sorry for the misunderstanding. I suspect that the cost of potential confusion outweighs the potential benefit of mistakenly setting a cache size that isn't a multiple of the cache line size, but as you say it's a minor thing and either way would work.

[grosser]

OK. Let me know when this is worth an official LGTM.

[asb]

include/llvm/Analysis/TargetTransformInfoImpl.h

348

Shouldn't this have something like:

`
default:
  llvm_unreachable("Unknown TargetTransformInfo::CacheLevel")

[gareevroman]

In D37051#850439, @grosser wrote:

In D37051#849798, @gareevroman wrote:

I think throughput and latency of vector fma instructions are pretty constant across micro-architectures too. Can we also add them?

Sorry, probably, it’d require to specify it for each architecture.

We could do this. Some of the backend experts might be able to help you how to do this best. I think we should do this in a separate patch. Care to propose one?

Yes, I will propose it. Sometimes it can be difficult to find this information, since it's not always publicly available.

[grosser]

Use C++ class enum

Add llvm_unreachables

[grosser]

Addressed Alex comments.

include/llvm/Analysis/TargetTransformInfoImpl.h

348

The switch above is fully covered, but I can add this as a form of defensive programming. Thinking about this, it might also be useful to used typed enums for the cache level. I will update the patch accordingly.

[fhahn]

include/llvm/Analysis/TargetTransformInfoImpl.h

348

I think using an enum class would be enough. AFAIK, compilers are pretty good at warning about missing cases in switch statements over enum classes. I think there is no need for default, as the compiler would catch missing patterns.

[grosser]

include/llvm/Analysis/TargetTransformInfoImpl.h

348

Right. Especially clang got very good at this and I think gcc also supports this meanwhile.

I did not add a default case on purpose, as this would prevent compiler warnings about uncovered cases. I added a unreachable _after_ the swich, just do document this code is never reached. Most compilers, likely will know this already, but older compilers might warn if they cannot prove the return is unreachable. We help them out here as well.

[fhahn]

LGTM, just a minor nit about the C-style fallthrough comment

include/llvm/Analysis/TargetTransformInfoImpl.h

358

Are you using the C-style comment to tell GCC that this fallthrough case is intentional? LLVM_FALLTHROUGH provides a slightly more portable and direct way of doing that I think

lib/Target/X86/X86TargetTransformInfo.cpp

112

Same as above

[grosser]

Use LLVM_FALLTHROUGH

[grosser]

@fhahn, I just addressed your comments.

@asb, I think this is now ready. Could you have a final look?

[asb]

Looks good to me.

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// \p AllowPromotionWithoutCommonHeader Set true if promoting \p I is
   /// profitable without finding other extensions fed by the same input.
   bool shouldConsiderAddressTypePromotion(
       const Instruction &I, bool &AllowPromotionWithoutCommonHeader) const;
 
   /// \return The size of a cache line in bytes.
   unsigned getCacheLineSize() const;
 
+  /// The possible cache levels
+  enum CacheLevel {
+    CL_L1,   // The L1 cache
+    CL_L2,   // The L2 cache
+
+    // We currently do not model L3 caches, as their sizes differ widely between
+    // microarchitectures. Also, we currently do not have a use for L3 cache
+    // size modeling yet.
+  };
+
+  /// \return The size of the cache level in bytes.
+  unsigned getCacheSize(CacheLevel Level) const;
+
+  /// \return The associativity of the cache level.
+  unsigned getCacheAssociativity(CacheLevel Level) const;
+
   /// \return How much before a load we should place the prefetch instruction.
   /// This is currently measured in number of instructions.
   unsigned getPrefetchDistance() const;
 
   /// \return Some HW prefetchers can handle accesses up to a certain constant
   /// stride.  This is the minimum stride in bytes where it makes sense to start
   /// adding SW prefetches.  The default is 1, i.e. prefetch with any stride.
   unsigned getMinPrefetchStride() const;
public:
   virtual int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                             Type *Ty) = 0;
   virtual unsigned getNumberOfRegisters(bool Vector) = 0;
   virtual unsigned getRegisterBitWidth(bool Vector) const = 0;
   virtual unsigned getMinVectorRegisterBitWidth() = 0;
   virtual bool shouldConsiderAddressTypePromotion(
       const Instruction &I, bool &AllowPromotionWithoutCommonHeader) = 0;
   virtual unsigned getCacheLineSize() = 0;
+  virtual unsigned getCacheSize(CacheLevel Level) = 0;
+  virtual unsigned getCacheAssociativity(CacheLevel Level) = 0;
   virtual unsigned getPrefetchDistance() = 0;
   virtual unsigned getMinPrefetchStride() = 0;
   virtual unsigned getMaxPrefetchIterationsAhead() = 0;
   virtual unsigned getMaxInterleaveFactor(unsigned VF) = 0;
   virtual unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
public:
   bool shouldConsiderAddressTypePromotion(
       const Instruction &I, bool &AllowPromotionWithoutCommonHeader) override {
     return Impl.shouldConsiderAddressTypePromotion(
         I, AllowPromotionWithoutCommonHeader);
   }
   unsigned getCacheLineSize() override {
     return Impl.getCacheLineSize();
   }
+  unsigned getCacheSize(CacheLevel Level) override {
+    return Impl.getCacheSize(Level);
+  }
+  unsigned getCacheAssociativity(CacheLevel Level) override {
+    return Impl.getCacheAssociativity(Level);
+  }
   unsigned getPrefetchDistance() override { return Impl.getPrefetchDistance(); }
   unsigned getMinPrefetchStride() override {
     return Impl.getMinPrefetchStride();
   }
   unsigned getMaxPrefetchIterationsAhead() override {
     return Impl.getMaxPrefetchIterationsAhead();
   }
   unsigned getMaxInterleaveFactor(unsigned VF) override {

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   shouldConsiderAddressTypePromotion(const Instruction &I,
                                      bool &AllowPromotionWithoutCommonHeader) {
     AllowPromotionWithoutCommonHeader = false;
     return false;
   }
 
   unsigned getCacheLineSize() { return 0; }
 
+  unsigned getCacheSize(TargetTransformInfo::CacheLevel Level) {
+    switch (Level) {
+    case TargetTransformInfo::CL_L1:
+      return 32 * 1024;  //  32 KByte
+    case TargetTransformInfo::CL_L2:
+      return 256 * 1024; // 128 KByte
+    }
+  }
+
+  unsigned getCacheAssociativity(TargetTransformInfo::CacheLevel Level) {
+    return 8;
+  }
+
   unsigned getPrefetchDistance() { return 0; }
 
   unsigned getMinPrefetchStride() { return 1; }
 
   unsigned getMaxPrefetchIterationsAhead() { return UINT_MAX; }
 
   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 
   unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty,
                                   TTI::OperandValueKind Opd1Info,
                                   TTI::OperandValueKind Opd2Info,

lib/Analysis/TargetTransformInfo.cpp

bool TargetTransformInfo::shouldConsiderAddressTypePromotion(
   return TTIImpl->shouldConsiderAddressTypePromotion(
       I, AllowPromotionWithoutCommonHeader);
 }
 
 unsigned TargetTransformInfo::getCacheLineSize() const {
   return TTIImpl->getCacheLineSize();
 }
 
+unsigned TargetTransformInfo::getCacheSize(CacheLevel Level) const {
+  return TTIImpl->getCacheSize(Level);
+}
+
+unsigned TargetTransformInfo::getCacheAssociativity(CacheLevel Level) const {
+  return TTIImpl->getCacheAssociativity(Level);
+}
+
 unsigned TargetTransformInfo::getPrefetchDistance() const {
   return TTIImpl->getPrefetchDistance();
 }
 
 unsigned TargetTransformInfo::getMinPrefetchStride() const {
   return TTIImpl->getMinPrefetchStride();
 }
 

lib/Target/X86/X86TargetTransformInfo.h

explicit X86TTIImpl(const X86TargetMachine *TM, const Function &F)
       : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
         TLI(ST->getTargetLowering()) {}
 
   /// \name Scalar TTI Implementations
   /// @{
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
 
   /// @}
+  unsigned getCacheSize(TargetTransformInfo::CacheLevel Level) const;
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector) const;
   unsigned getLoadStoreVecRegBitWidth(unsigned AS) const;
   unsigned getMaxInterleaveFactor(unsigned VF);

lib/Target/X86/X86TargetTransformInfo.cpp

 X86TTIImpl::getPopcntSupport(unsigned TyWidth) {
   assert(isPowerOf2_32(TyWidth) && "Ty width must be power of 2");
   // TODO: Currently the __builtin_popcount() implementation using SSE3
   //   instructions is inefficient. Once the problem is fixed, we should
   //   call ST->hasSSE3() instead of ST->hasPOPCNT().
   return ST->hasPOPCNT() ? TTI::PSK_FastHardware : TTI::PSK_Software;
 }
 
+unsigned X86TTIImpl::getCacheSize(TargetTransformInfo::CacheLevel Level) const {
+  switch (Level) {
+  case TargetTransformInfo::CL_L1:
+    //   - Penry
+    //   - Nehalem
+    //   - Westmere
+    //   - Sandy Bridge
+    //   - Ivy Bridge
+    //   - Haswell
+    //   - Broadwell
+    //   - Skylake
+    //   - Kabylake
+    return 32 * 1024;  //  32 KByte
+  case TargetTransformInfo::CL_L2:
+    //   - Penry
+    //   - Nehalem
+    //   - Westmere
+    //   - Sandy Bridge
+    //   - Ivy Bridge
+    //   - Haswell
+    //   - Broadwell
+    //   - Skylake
+    //   - Kabylake
+    return 256 * 1024; // 128 KByte
+  }
+}
+
 unsigned X86TTIImpl::getNumberOfRegisters(bool Vector) {
   if (Vector && !ST->hasSSE1())
     return 0;
 
   if (ST->is64Bit()) {
     if (Vector && ST->hasAVX512())
       return 32;
     return 16;
   }
   return 8;
 }
 
 unsigned X86TTIImpl::getRegisterBitWidth(bool Vector) const {
   if (Vector) {
     if (ST->hasAVX512())
       return 512;
     if (ST->hasAVX())
       return 256;
     if (ST->hasSSE1())
       return 128;
     return 0;
   }
 
   if (ST->is64Bit())
     return 64;