LLVM  10.0.0svn
Macros | Functions | Variables
LoopCacheAnalysis.cpp File Reference

This file defines the implementation for the loop cache analysis. More...

#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/ADT/BreadthFirstIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
Include dependency graph for LoopCacheAnalysis.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-cache-cost"
 

Functions

static LoopgetInnerMostLoop (const LoopVectorTy &Loops)
 Retrieve the innermost loop in the given loop nest Loops. More...
 
static bool isOneDimensionalArray (const SCEV &AccessFn, const SCEV &ElemSize, const Loop &L, ScalarEvolution &SE)
 
static const SCEVcomputeTripCount (const Loop &L, ScalarEvolution &SE)
 Compute the trip count for the given loop L. More...
 

Variables

static cl::opt< unsignedDefaultTripCount ("default-trip-count", cl::init(100), cl::Hidden, cl::desc("Use this to specify the default trip count of a loop"))
 
static cl::opt< unsignedTemporalReuseThreshold ("temporal-reuse-threshold", cl::init(2), cl::Hidden, cl::desc("Use this to specify the max. distance between array elements " "accessed in a loop so that the elements are classified to have " "temporal reuse"))
 

Detailed Description

This file defines the implementation for the loop cache analysis.

The implementation is largely based on the following paper:

  Compiler Optimizations for Improving Data Locality
  By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng
  http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf

The general approach taken to estimate the number of cache lines used by the memory references in an inner loop is:

  1. Partition memory references that exhibit temporal or spacial reuse into reference groups.
  2. For each loop L in the a loop nest LN: a. Compute the cost of the reference group b. Compute the loop cost by summing up the reference groups costs

Definition in file LoopCacheAnalysis.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-cache-cost"

Definition at line 36 of file LoopCacheAnalysis.cpp.

Function Documentation

◆ computeTripCount()

static const SCEV* computeTripCount ( const Loop L,
ScalarEvolution SE 
)
static

Compute the trip count for the given loop L.

Return the SCEV expression for the trip count or nullptr if it cannot be computed.

Definition at line 97 of file LoopCacheAnalysis.cpp.

References llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getOne(), and llvm::SCEV::getType().

Referenced by llvm::IndexedReference::computeRefCost().

◆ getInnerMostLoop()

static Loop* getInnerMostLoop ( const LoopVectorTy Loops)
static

Retrieve the innermost loop in the given loop nest Loops.

It returns a nullptr if any loops in the loop vector supplied has more than one sibling. The loop vector is expected to contain loops collected in breadth-first order.

Definition at line 55 of file LoopCacheAnalysis.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), and llvm::SmallVectorBase::size().

Referenced by llvm::CacheCost::getCacheCost().

◆ isOneDimensionalArray()

static bool isOneDimensionalArray ( const SCEV AccessFn,
const SCEV ElemSize,
const Loop L,
ScalarEvolution SE 
)
static

Variable Documentation

◆ DefaultTripCount

cl::opt<unsigned> DefaultTripCount("default-trip-count", cl::init(100), cl::Hidden, cl::desc("Use this to specify the default trip count of a loop"))
static

◆ TemporalReuseThreshold

cl::opt<unsigned> TemporalReuseThreshold("temporal-reuse-threshold", cl::init(2), cl::Hidden, cl::desc("Use this to specify the max. distance between array elements " "accessed in a loop so that the elements are classified to have " "temporal reuse"))
static