LLVM  15.0.0git
Macros | Functions | Variables
LoopCacheAnalysis.cpp File Reference
#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/ADT/BreadthFirstIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Support/CommandLine.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, const SCEV &ElemSize, ScalarEvolution &SE)
 Compute the trip count for the given loop L or assume a default value if it is not a compile time constant. More...
 

Variables

static 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 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"))
 

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 43 of file LoopCacheAnalysis.cpp.

Function Documentation

◆ computeTripCount()

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

Compute the trip count for the given loop L or assume a default value if it is not a compile time constant.

Return the SCEV expression for the trip count.

Definition at line 109 of file LoopCacheAnalysis.cpp.

References llvm::dbgs(), DefaultTripCount, llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getConstant(), llvm::Loop::getName(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEV::getType(), and LLVM_DEBUG.

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 62 of file LoopCacheAnalysis.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::is_sorted(), L2, and Loops.

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