CacheUtility.cpp File Reference

#include "CacheUtility.h"
#include "llvm/IR/PatternMatch.h"
#include "FunctionUtils.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include <utility>

Include dependency graph for CacheUtility.cpp:

Go to the source code of this file.

Classes
struct	NonAffineClosedFormRewriter
	Replace every non-affine recurrence (of degree at most three) inside an expression by its closed form in the canonical induction variable of its loop, treated as an opaque value. More...

Typedefs
using	NoWrapFlagsTy

Functions
llvm::cl::opt< bool >	EfficientBoolCache ("enzyme-smallbool", cl::init(false), cl::Hidden, cl::desc("Place 8 bools together in a single byte"))
	Pack 8 bools together in a single byte.
llvm::cl::opt< bool >	EnzymeZeroCache ("enzyme-zero-cache", cl::init(false), cl::Hidden, cl::desc("Zero initialize the cache"))
llvm::cl::opt< bool >	EnzymePrintPerf ("enzyme-print-perf", cl::init(false), cl::Hidden, cl::desc("Enable Enzyme to print performance info"))
llvm::cl::opt< bool >	EfficientMaxCache ("enzyme-max-cache", cl::init(false), cl::Hidden, cl::desc("Avoid reallocs when possible by potentially overallocating cache"))
llvm::cl::opt< bool >	EnzymeRewriteAccumulators ("enzyme-rewrite-accumulators", cl::init(true), cl::Hidden, cl::desc("Rewrite a loop-carried counter whose step is an inner loop's " "trip count into a closed form of the induction variable"))
std::pair< PHINode *, Instruction * >	InsertNewCanonicalIV (Loop *L, Type *Ty, const llvm::Twine &Name)
std::pair< PHINode *, Instruction * >	FindCanonicalIV (Loop *L, Type *Ty)
static const SCEV *	closedFormOfNegatingRecurrence (PHINode *PN, Loop *L, const SCEV *IterationNumber, ScalarEvolution &SE)
	PN is a header phi of L that is negated on every iteration, x_{i+1} = -x_i, such as the alternating sign of a cofactor expansion.
static const SCEV *	closedFormOfCountedAccumulator (PHINode *PN, Loop *L, const SCEV *IterationNumber, ScalarEvolution &SE)
	PN is a header phi of L that scalar evolution could not classify.
void	RemoveRedundantIVs (Loop *L, PHINode *CanonicalIV, Instruction *Increment, MustExitScalarEvolution &SE, llvm::function_ref< void(Instruction *, Value *)> replacer, llvm::function_ref< void(Instruction *)> eraser)
void	CanonicalizeLatches (const Loop *L, BasicBlock *Header, BasicBlock *Preheader, PHINode *CanonicalIV, MustExitScalarEvolution &SE, CacheUtility &gutils, Instruction *Increment, ArrayRef< BasicBlock * > latches)

Typedef Documentation

NoWrapFlagsTy

using NoWrapFlagsTy

Initial value:

 
    decltype(std::declval<const SCEVAddRecExpr &>().getNoWrapFlags())

Definition at line 253 of file CacheUtility.cpp.

Function Documentation

CanonicalizeLatches()

void CanonicalizeLatches	(	const Loop *	L,
		BasicBlock *	Header,
		BasicBlock *	Preheader,
		PHINode *	CanonicalIV,
		MustExitScalarEvolution &	SE,
		CacheUtility &	gutils,
		Instruction *	Increment,
		ArrayRef< BasicBlock * >	latches )

Definition at line 647 of file CacheUtility.cpp.

References getBranchCondition(), getFirstNonPHI(), and isConditionalBranch().

Referenced by CacheUtility::getContext().

closedFormOfCountedAccumulator()

static const SCEV * closedFormOfCountedAccumulator ( PHINode * PN, Loop * L, const SCEV * IterationNumber, ScalarEvolution & SE )

static

PN is a header phi of L that scalar evolution could not classify.

Recognize an accumulator whose per-iteration step is the trip count of an inner loop, as in

int idx = 0; for (i = 0; i < d; i++) for (j = i + 1; j < d; j++) ... l[idx++] ...

After loop rotation the latch value of idx reaches PN through a phi that merges "inner loop skipped" with the inner loop's exit value, which SCEV does not see through, so PN stays an unknown and would be cached once per iteration in the reverse pass. Derive the step from that exit value, check that a skipped inner loop contributes exactly zero, and return PN as a closed form in the iteration number (a polynomial, quadratic here), or nullptr when the shape does not match or the proofs fail.

Definition at line 307 of file CacheUtility.cpp.

References EnzymeRewriteAccumulators(), evaluateAtIterationWithoutExt(), getBranchCondition(), isConditionalBranch(), and X().

Referenced by RemoveRedundantIVs().

closedFormOfNegatingRecurrence()

static const SCEV * closedFormOfNegatingRecurrence ( PHINode * PN, Loop * L, const SCEV * IterationNumber, ScalarEvolution & SE )

static

PN is a header phi of L that is negated on every iteration, x_{i+1} = -x_i, such as the alternating sign of a cofactor expansion.

Scalar evolution cannot express this recurrence, so without a closed form the reverse pass caches its value once per iteration. At iteration I it is x_0 when I is even and -x_0 when I is odd, i.e. x_0 * (1 - 2 * (I mod 2)), with the parity formed as I - 2 * (I / 2) (truncating I keeps its parity).

Definition at line 262 of file CacheUtility.cpp.

References EnzymeRewriteAccumulators().

Referenced by RemoveRedundantIVs().

EfficientBoolCache()

llvm::cl::opt< bool > EfficientBoolCache	(	"enzyme-smallbool"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Place 8 bools together in a single byte")	)

Pack 8 bools together in a single byte.

EfficientMaxCache()

llvm::cl::opt< bool > EfficientMaxCache	(	"enzyme-max-cache"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Avoid reallocs when possible by potentially overallocating cache")	)

Referenced by CacheUtility::getContext().

EnzymePrintPerf()

llvm::cl::opt< bool > EnzymePrintPerf	(	"enzyme-print-perf"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Enable Enzyme to print performance info")	)

EnzymeRewriteAccumulators()

llvm::cl::opt< bool > EnzymeRewriteAccumulators	(	"enzyme-rewrite-accumulators"	,
		cl::init(true)	,
		cl::Hidden	,
		cl::desc("Rewrite a loop-carried counter whose step is an inner loop's " "trip count into a closed form of the induction variable")	)

Referenced by closedFormOfCountedAccumulator(), closedFormOfNegatingRecurrence(), and RemoveRedundantIVs().

EnzymeZeroCache()

llvm::cl::opt< bool > EnzymeZeroCache	(	"enzyme-zero-cache"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Zero initialize the cache")	)

FindCanonicalIV()

std::pair< PHINode *, Instruction * > FindCanonicalIV	(	Loop *	L,
		Type *	Ty )

Definition at line 160 of file CacheUtility.cpp.

References getFirstNonPHIOrDbg(), and moveBeforeInst().

Referenced by CacheUtility::getContext().

InsertNewCanonicalIV()

std::pair< PHINode *, Instruction * > InsertNewCanonicalIV	(	Loop *	L,
		Type *	Ty,
		const llvm::Twine &	Name )

Definition at line 132 of file CacheUtility.cpp.

References getFirstNonPHIOrDbg().

Referenced by CanonicalizeLoops().

RemoveRedundantIVs()

void RemoveRedundantIVs	(	Loop *	L,
		PHINode *	CanonicalIV,
		Instruction *	Increment,
		MustExitScalarEvolution &	SE,
		llvm::function_ref< void(Instruction *, Value *)>	replacer,
		llvm::function_ref< void(Instruction *)>	eraser )

Definition at line 526 of file CacheUtility.cpp.

References closedFormOfCountedAccumulator(), closedFormOfNegatingRecurrence(), EnzymeRewriteAccumulators(), and getFirstNonPHI().

Referenced by CanonicalizeLoops().