class CacheCost

Declaration

class CacheCost { /* full declaration omitted */ };

Description

\c CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memory references it contains. The 'cache cost' of a loop 'L' in a loop nest 'LN' is computed as the sum of the cache costs of all of its reference groups when the loop is considered to be in the innermost position in the nest. A reference group represents memory references that fall into the same cache line. Each reference group is analysed with respect to the innermost loop in a loop nest. The cost of a reference is defined as follow: - one if it is loop invariant w.r.t the innermost loop, - equal to the loop trip count divided by the cache line times the reference stride if the reference stride is less than the cache line size (CLS), and the coefficient of this loop's index variable used in all other subscripts is zero (e.g. RefCost = TripCount/(CLS/RefStride)) - equal to the innermost loop trip count if the reference stride is greater or equal to the cache line size CLS.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:188

Member Variables

private llvm::LoopVectorTy Loops

Loops in the loop nest associated with this object.

private SmallVector<llvm::CacheCost::LoopTripCountTy, 3> TripCounts

Trip counts for the loops in the loop nest associated with this object.

private SmallVector<llvm::CacheCost::LoopCacheCostTy, 3> LoopCosts

Cache costs for the loops in the loop nest associated with this object.

private Optional<unsigned int> TRT

The max. distance between array elements accessed in a loop so that the elements are classified to have temporal reuse.

private const llvm::LoopInfo& LI

private llvm::ScalarEvolution& SE

private llvm::TargetTransformInfo& TTI

private llvm::AAResults& AA

private llvm::DependenceInfo& DI

public static const llvm::CacheCostTy InvalidCost = -1

Method Overview

• public CacheCost(const llvm::LoopVectorTy & Loops, const llvm::LoopInfo & LI, llvm::ScalarEvolution & SE, llvm::TargetTransformInfo & TTI, llvm::AAResults & AA, llvm::DependenceInfo & DI, Optional<unsigned int> TRT = None)
• private void calculateCacheFootprint()
• private llvm::CacheCostTy computeLoopCacheCost(const llvm::Loop & L, const llvm::ReferenceGroupsTy & RefGroups) const
• private llvm::CacheCostTy computeRefGroupCacheCost(const llvm::ReferenceGroupTy & RG, const llvm::Loop & L) const
• public static std::unique_ptr<CacheCost> getCacheCost(llvm::Loop & Root, llvm::LoopStandardAnalysisResults & AR, llvm::DependenceInfo & DI, Optional<unsigned int> TRT = None)
• public llvm::CacheCostTy getLoopCost(const llvm::Loop & L) const
• public ArrayRef<llvm::CacheCost::LoopCacheCostTy> getLoopCosts() const
• private bool populateReferenceGroups(llvm::ReferenceGroupsTy & RefGroups) const
• private void sortLoopCosts()

Methods

¶CacheCost(const llvm::LoopVectorTy& Loops,
          const llvm::LoopInfo& LI,
          llvm::ScalarEvolution& SE,
          llvm::TargetTransformInfo& TTI,
          llvm::AAResults& AA,
          llvm::DependenceInfo& DI,
          Optional<unsigned int> TRT = None)

Description

Construct a CacheCost object for the loop nest described by \p Loops. The optional parameter \p TRT can be used to specify the max. distance between array elements accessed in a loop so that the elements are classified to have temporal reuse.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:200

Parameters

const llvm::LoopVectorTy& Loops

const llvm::LoopInfo& LI

llvm::ScalarEvolution& SE

llvm::TargetTransformInfo& TTI

llvm::AAResults& AA

llvm::DependenceInfo& DI

Optional<unsigned int> TRT = None

¶void calculateCacheFootprint()

Description

Calculate the cache footprint of each loop in the nest (when it is considered to be in the innermost position).

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:227

¶llvm::CacheCostTy computeLoopCacheCost(
    const llvm::Loop& L,
    const llvm::ReferenceGroupsTy& RefGroups)
    const

Description

Calculate the cost of the given loop \p L assuming it is the innermost loop in nest.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:236

Parameters

const llvm::Loop& L

const llvm::ReferenceGroupsTy& RefGroups

¶llvm::CacheCostTy computeRefGroupCacheCost(
    const llvm::ReferenceGroupTy& RG,
    const llvm::Loop& L) const

Description

Compute the cost of a representative reference in reference group \p RG when the given loop \p L is considered as the innermost loop in the nest. The computed cost is an estimate for the number of cache lines used by the reference group. The representative reference cost is defined as: - equal to one if the reference is loop invariant, or - equal to '(TripCount * stride) / cache_line_size' if (a) loop \p L's induction variable is used only in the reference subscript associated with loop \p L, and (b) the reference stride is less than the cache line size, or - TripCount otherwise

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:249

Parameters

const llvm::ReferenceGroupTy& RG

const llvm::Loop& L

¶static std::unique_ptr<CacheCost> getCacheCost(
    llvm::Loop& Root,
    llvm::LoopStandardAnalysisResults& AR,
    llvm::DependenceInfo& DI,
    Optional<unsigned int> TRT = None)

Description

Create a CacheCost for the loop nest rooted by \p Root. The optional parameter \p TRT can be used to specify the max. distance between array elements accessed in a loop so that the elements are classified to have temporal reuse.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:209

Parameters

llvm::Loop& Root

llvm::LoopStandardAnalysisResults& AR

llvm::DependenceInfo& DI

Optional<unsigned int> TRT = None

¶llvm::CacheCostTy getLoopCost(
    const llvm::Loop& L) const

Description

Return the estimated cost of loop \p L if the given loop is part of the loop nest associated with this object. Return -1 otherwise.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:214

Parameters

const llvm::Loop& L

¶ArrayRef<llvm::CacheCost::LoopCacheCostTy>
getLoopCosts() const

Description

Return the estimated ordered loop costs.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:222

¶bool populateReferenceGroups(
    llvm::ReferenceGroupsTy& RefGroups) const

Description

Partition store/load instructions in the loop nest into reference groups. Two or more memory accesses belong in the same reference group if they share the same cache line.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:232

Parameters

llvm::ReferenceGroupsTy& RefGroups

¶void sortLoopCosts()

Description

Sort the LoopCosts vector by decreasing cache cost.

Declared at: llvm/include/llvm/Analysis/LoopCacheAnalysis.h:253