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/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"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-cache-cost"

Functions
static Loop *	getInnerMostLoop (const LoopVectorTy &Loops)
	Retrieve the innermost loop in the given loop nest Loops.
static bool	isOneDimensionalArray (const SCEV &AccessFn, const SCEV &ElemSize, const Loop &L, ScalarEvolution &SE)
static const SCEV *	computeTripCount (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.

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::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(), and Loops.

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

isOneDimensionalArray()

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

static

Definition at line 81 of file LoopCacheAnalysis.cpp.

References assert(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownNegative(), and llvm::ScalarEvolution::isLoopInvariant().

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")) ( "default-trip-count"  , cl::init(100)  , cl::Hidden  , cl::desc("Use this to specify the default trip count of a loop")    )

static

Referenced by llvm::CacheCost::CacheCost(), and computeTripCount().

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