Translate a SCEV to an isl::pw_aff and the domain on which it is invalid. More...

#include <SCEVAffinator.h>

Inheritance diagram for polly::SCEVAffinator:

Public Member Functions
	SCEVAffinator (Scop *S, llvm::LoopInfo &LI)

PWACtx	getPwAff (const llvm::SCEV E, llvm::BasicBlock BB=nullptr, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
	Translate a SCEV to an isl::pw_aff.

void	takeNonNegativeAssumption (PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
	Take the assumption that `PWAC` is non-negative.

void	interpretAsUnsigned (PWACtx &PWAC, unsigned Width)
	Interpret the PWA in `PWAC` as an unsigned value.

bool	hasNSWAddRecForLoop (llvm::Loop *L) const
	Check an <nsw> AddRec for the loop `L` is cached.

llvm::LoopInfo *	getLI () const
	Return the LoopInfo used by thi object.

Private Types
using	CacheKey = std::pair< const llvm::SCEV , llvm::BasicBlock >
	Key to identify cached expressions.

Private Member Functions
llvm::Loop *	getScope ()
	Return the loop for the current block if any.

PWACtx	getPWACtxFromPWA (isl::pw_aff PWA)
	Return a PWACtx for `PWA` that is always valid.

isl::pw_aff	addModuloSemantic (isl::pw_aff PWA, llvm::Type *ExprType) const
	Compute the non-wrapping version of `PWA` for type `ExprType`.

PWACtx	checkForWrapping (const llvm::SCEV *Expr, PWACtx PWAC) const
	If `Expr` might cause an integer wrap record an assumption.

bool	computeModuloForExpr (const llvm::SCEV *Expr)
	Whether to track the value of this expression precisely, rather than assuming it won't wrap.

PWACtx	visit (const llvm::SCEV *E)

PWACtx	visitConstant (const llvm::SCEVConstant *E)

PWACtx	visitVScale (const llvm::SCEVVScale *E)

PWACtx	visitPtrToIntExpr (const llvm::SCEVPtrToIntExpr *E)

PWACtx	visitTruncateExpr (const llvm::SCEVTruncateExpr *E)

PWACtx	visitZeroExtendExpr (const llvm::SCEVZeroExtendExpr *E)

PWACtx	visitSignExtendExpr (const llvm::SCEVSignExtendExpr *E)

PWACtx	visitAddExpr (const llvm::SCEVAddExpr *E)

PWACtx	visitMulExpr (const llvm::SCEVMulExpr *E)

PWACtx	visitUDivExpr (const llvm::SCEVUDivExpr *E)

PWACtx	visitAddRecExpr (const llvm::SCEVAddRecExpr *E)

PWACtx	visitSMaxExpr (const llvm::SCEVSMaxExpr *E)

PWACtx	visitSMinExpr (const llvm::SCEVSMinExpr *E)

PWACtx	visitUMaxExpr (const llvm::SCEVUMaxExpr *E)

PWACtx	visitUMinExpr (const llvm::SCEVUMinExpr *E)

PWACtx	visitSequentialUMinExpr (const llvm::SCEVSequentialUMinExpr *E)

PWACtx	visitUnknown (const llvm::SCEVUnknown *E)

PWACtx	visitSDivInstruction (llvm::Instruction *SDiv)

PWACtx	visitSRemInstruction (llvm::Instruction *SRem)

PWACtx	complexityBailout ()

Private Attributes
llvm::DenseMap< CacheKey, PWACtx >	CachedExpressions
	Map to remembered cached expressions.

Scop *	S

isl::ctx	Ctx

unsigned	NumIterators

llvm::ScalarEvolution &	SE

llvm::LoopInfo &	LI

llvm::BasicBlock *	BB

RecordedAssumptionsTy *	RecordedAssumptions = nullptr

const llvm::DataLayout &	TD
	Target data for element size computing.

Friends
struct	llvm::SCEVVisitor< SCEVAffinator, PWACtx >

Detailed Description

Translate a SCEV to an isl::pw_aff and the domain on which it is invalid.

Definition at line 30 of file SCEVAffinator.h.

Member Typedef Documentation

◆ CacheKey

using polly::SCEVAffinator::CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>

private

Key to identify cached expressions.

Definition at line 58 of file SCEVAffinator.h.

Constructor & Destructor Documentation

◆ SCEVAffinator()

SCEVAffinator::SCEVAffinator	(	Scop *	S,
		llvm::LoopInfo &	LI
	)

Definition at line 84 of file SCEVAffinator.cpp.

Member Function Documentation

◆ addModuloSemantic()

isl::pw_aff SCEVAffinator::addModuloSemantic	(	isl::pw_aff	PWA,
		llvm::Type *	ExprType
	)		const

private

Compute the non-wrapping version of PWA for type ExprType.

Parameters

PWA	The piece-wise affine function that might wrap.
Type	The type of the SCEV that was translated to `PWA`.

Returns: The expr PWA modulo the size constraints of ExprType.

Definition at line 160 of file SCEVAffinator.cpp.

References isl::pw_aff::add(), Ctx, Domain, isl::pw_aff::domain(), getWidthExpValOnDomain(), isl::val::int_from_ui(), isl::manage(), isl::multi_pw_aff::sub(), and TD.

Referenced by checkForWrapping(), and visit().

◆ checkForWrapping()

PWACtx SCEVAffinator::checkForWrapping	(	const llvm::SCEV *	Expr,
		PWACtx	PWAC
	)		const

private

If Expr might cause an integer wrap record an assumption.

Parameters

Expr	The SCEV expression that might wrap.
PWAC	The isl representation of `Expr` with the invalid domain.

Returns: The isl representation PWAC with a possibly adjusted domain.

Definition at line 132 of file SCEVAffinator.cpp.

References addModuloSemantic(), polly::AS_RESTRICTION, BB, isl::set::coalesce(), getNoWrapFlags(), IgnoreIntegerWrapping(), isl::set::is_empty(), isl::set::params(), polly::recordAssumption(), RecordedAssumptions, isl::set::unite(), and polly::WRAPPING.

Referenced by visit().

◆ complexityBailout()

PWACtx SCEVAffinator::complexityBailout ( )

private

Definition at line 575 of file SCEVAffinator.cpp.

References BB, polly::COMPLEXITY, SE, and visit().

Referenced by visitAddExpr(), visitMulExpr(), visitSMaxExpr(), and visitSMinExpr().

◆ computeModuloForExpr()

bool SCEVAffinator::computeModuloForExpr ( const llvm::SCEV * Expr )

private

Whether to track the value of this expression precisely, rather than assuming it won't wrap.

Definition at line 188 of file SCEVAffinator.cpp.

References MaxSmallBitWidth, and TD.

Referenced by visit(), visitTruncateExpr(), and visitZeroExtendExpr().

◆ getLI()

llvm::LoopInfo * polly::SCEVAffinator::getLI ( ) const

inline

Return the LoopInfo used by thi object.

Definition at line 54 of file SCEVAffinator.h.

References LI.

Referenced by polly::Scop::getLI().

◆ getPWACtxFromPWA()

PWACtx SCEVAffinator::getPWACtxFromPWA ( isl::pw_aff PWA )

private

Return a PWACtx for PWA that is always valid.

Definition at line 113 of file SCEVAffinator.cpp.

References Ctx, isl::set::empty(), and NumIterators.

Referenced by visit(), visitConstant(), and visitUnknown().

◆ getPwAff()

PWACtx SCEVAffinator::getPwAff	(	const llvm::SCEV *	E,
		llvm::BasicBlock *	BB = `nullptr`,
		RecordedAssumptionsTy *	RecordedAssumptions = `nullptr`
	)

Translate a SCEV to an isl::pw_aff.

Parameters

E	he expression that is translated.
BB	The block in which `E` is executed.

Returns: The isl representation of the SCEV E in Domain.

Definition at line 117 of file SCEVAffinator.cpp.

References BB, isl_set_free(), isl_set_n_dim(), NumIterators, RecordedAssumptions, and visit().

Referenced by polly::Scop::getPwAff().

◆ getScope()

Loop * SCEVAffinator::getScope ( )

private

Return the loop for the current block if any.

Definition at line 88 of file SCEVAffinator.cpp.

References BB, and LI.

Referenced by visit(), visitSDivInstruction(), visitSRemInstruction(), and visitUnknown().

◆ hasNSWAddRecForLoop()

bool SCEVAffinator::hasNSWAddRecForLoop ( llvm::Loop * L ) const

Check an <nsw> AddRec for the loop L is cached.

Definition at line 174 of file SCEVAffinator.cpp.

References CachedExpressions.

Referenced by polly::Scop::hasNSWAddRecForLoop().

◆ interpretAsUnsigned()

void SCEVAffinator::interpretAsUnsigned	(	PWACtx &	PWAC,
		unsigned	Width
	)

Interpret the PWA in PWAC as an unsigned value.

Definition at line 90 of file SCEVAffinator.cpp.

References getWidthExpValOnDomain(), isl_pw_aff_add(), isl_pw_aff_intersect_domain(), isl_pw_aff_nonneg_set(), isl_pw_aff_union_add(), isl_set_complement(), isl_set_copy(), and isl::manage().

Referenced by visitZeroExtendExpr().

◆ takeNonNegativeAssumption()

void SCEVAffinator::takeNonNegativeAssumption	(	PWACtx &	PWAC,
		RecordedAssumptionsTy *	RecordedAssumptions = `nullptr`
	)

Take the assumption that PWAC is non-negative.

Definition at line 99 of file SCEVAffinator.cpp.

References polly::AS_RESTRICTION, BB, isl_pw_aff_neg(), isl_pw_aff_pos_set(), isl_set_copy(), isl_set_params(), isl_set_union(), isl::manage(), polly::recordAssumption(), RecordedAssumptions, and polly::UNSIGNED.

Referenced by polly::Scop::getPwAff(), visitUDivExpr(), and visitZeroExtendExpr().

◆ visit()

PWACtx SCEVAffinator::visit ( const llvm::SCEV * E )

private

Definition at line 197 of file SCEVAffinator.cpp.

References addModuloSemantic(), BB, CachedExpressions, checkForWrapping(), combine(), computeModuloForExpr(), Ctx, Domain, polly::extractConstantFactor(), isl::ctx::get(), polly::getParamsInAffineExpr(), getPWACtxFromPWA(), getScope(), isl_aff_add_coefficient_si(), isl_aff_zero_on_domain(), isl_dim_param, isl_local_space_from_space(), isl_pw_aff_alloc(), isl_pw_aff_mul(), isl_set_universe(), isl_space_copy(), isl_space_set_alloc(), isl_space_set_dim_id(), isl::manage(), NumIterators, SE, and visitConstant().

Referenced by complexityBailout(), getPwAff(), visitAddExpr(), visitAddRecExpr(), visitMulExpr(), visitPtrToIntExpr(), visitSDivInstruction(), visitSignExtendExpr(), visitSMaxExpr(), visitSMinExpr(), visitSRemInstruction(), visitTruncateExpr(), visitUDivExpr(), visitUnknown(), and visitZeroExtendExpr().

◆ visitAddExpr()

PWACtx SCEVAffinator::visitAddExpr ( const llvm::SCEVAddExpr * E )

private

Definition at line 378 of file SCEVAffinator.cpp.

References combine(), complexityBailout(), isl_pw_aff_add(), isTooComplex(), and visit().

◆ visitAddRecExpr()

PWACtx SCEVAffinator::visitAddRecExpr ( const llvm::SCEVAddRecExpr * E )

private

Definition at line 402 of file SCEVAffinator.cpp.

References assert, combine(), Ctx, isl::ctx::get(), isl_aff_set_coefficient_si(), isl_aff_zero_on_domain(), isl_dim_in, isl_local_space_from_space(), isl_pw_aff_add(), isl_pw_aff_from_aff(), isl_space_set_alloc(), isl::manage(), NumIterators, SE, and visit().

◆ visitConstant()

PWACtx SCEVAffinator::visitConstant ( const llvm::SCEVConstant * E )

private

Definition at line 248 of file SCEVAffinator.cpp.

References Ctx, isl::ctx::get(), getPWACtxFromPWA(), isl_aff_val_on_domain(), isl_local_space_from_space(), isl_pw_aff_from_aff(), isl_space_set_alloc(), polly::isl_valFromAPInt(), isl::manage(), NumIterators, and polly::Value.

Referenced by visit().

◆ visitMulExpr()

PWACtx SCEVAffinator::visitMulExpr ( const llvm::SCEVMulExpr * E )

private

Definition at line 390 of file SCEVAffinator.cpp.

References combine(), complexityBailout(), isl_pw_aff_mul(), isTooComplex(), and visit().

◆ visitPtrToIntExpr()

PWACtx SCEVAffinator::visitPtrToIntExpr ( const llvm::SCEVPtrToIntExpr * E )

private

Definition at line 274 of file SCEVAffinator.cpp.

References visit().

◆ visitSDivInstruction()

PWACtx SCEVAffinator::visitSDivInstruction ( llvm::Instruction * SDiv )

private

Definition at line 516 of file SCEVAffinator.cpp.

References assert, combine(), getScope(), isl_pw_aff_tdiv_q(), SE, and visit().

Referenced by visitUnknown().

◆ visitSequentialUMinExpr()

PWACtx SCEVAffinator::visitSequentialUMinExpr ( const llvm::SCEVSequentialUMinExpr * E )

private

Definition at line 474 of file SCEVAffinator.cpp.

◆ visitSignExtendExpr()

PWACtx SCEVAffinator::visitSignExtendExpr ( const llvm::SCEVSignExtendExpr * E )

private

Definition at line 373 of file SCEVAffinator.cpp.

References visit().

◆ visitSMaxExpr()

PWACtx SCEVAffinator::visitSMaxExpr ( const llvm::SCEVSMaxExpr * E )

private

Definition at line 441 of file SCEVAffinator.cpp.

References combine(), complexityBailout(), isl_pw_aff_max(), isTooComplex(), and visit().

◆ visitSMinExpr()

PWACtx SCEVAffinator::visitSMinExpr ( const llvm::SCEVSMinExpr * E )

private

Definition at line 453 of file SCEVAffinator.cpp.

References combine(), complexityBailout(), isl_pw_aff_min(), isTooComplex(), and visit().

◆ visitSRemInstruction()

PWACtx SCEVAffinator::visitSRemInstruction ( llvm::Instruction * SRem )

private

Definition at line 533 of file SCEVAffinator.cpp.

References assert, combine(), getScope(), isl_pw_aff_tdiv_r(), SE, and visit().

Referenced by visitUnknown().

◆ visitTruncateExpr()

PWACtx SCEVAffinator::visitTruncateExpr ( const llvm::SCEVTruncateExpr * E )

private

Definition at line 278 of file SCEVAffinator.cpp.

References polly::AS_RESTRICTION, assert, BB, computeModuloForExpr(), getWidthExpValOnDomain(), isl_dim_set, isl_pw_aff_copy(), isl_pw_aff_ge_set(), isl_pw_aff_lt_set(), isl_pw_aff_neg(), isl_set_dim(), isl_set_params(), isl_set_union(), isl::manage(), isl::manage_copy(), polly::recordAssumption(), RecordedAssumptions, TD, polly::UNSIGNED, and visit().

◆ visitUDivExpr()

PWACtx SCEVAffinator::visitUDivExpr ( const llvm::SCEVUDivExpr * E )

private

Definition at line 478 of file SCEVAffinator.cpp.

References assert, combine(), getWidthExpValOnDomain(), isl_pw_aff_div(), isl::manage(), RecordedAssumptions, SE, takeNonNegativeAssumption(), TD, and visit().

◆ visitUMaxExpr()

PWACtx SCEVAffinator::visitUMaxExpr ( const llvm::SCEVUMaxExpr * E )

private

Definition at line 465 of file SCEVAffinator.cpp.

◆ visitUMinExpr()

PWACtx SCEVAffinator::visitUMinExpr ( const llvm::SCEVUMinExpr * E )

private

Definition at line 469 of file SCEVAffinator.cpp.

◆ visitUnknown()

PWACtx SCEVAffinator::visitUnknown ( const llvm::SCEVUnknown * E )

private

Definition at line 550 of file SCEVAffinator.cpp.

References Ctx, getPWACtxFromPWA(), getScope(), NumIterators, SE, visit(), visitSDivInstruction(), and visitSRemInstruction().

◆ visitVScale()

PWACtx SCEVAffinator::visitVScale ( const llvm::SCEVVScale * E )

private

Definition at line 270 of file SCEVAffinator.cpp.

◆ visitZeroExtendExpr()

PWACtx SCEVAffinator::visitZeroExtendExpr ( const llvm::SCEVZeroExtendExpr * E )

private

Definition at line 313 of file SCEVAffinator.cpp.

References computeModuloForExpr(), interpretAsUnsigned(), RecordedAssumptions, takeNonNegativeAssumption(), TD, and visit().

Friends And Related Function Documentation

◆ llvm::SCEVVisitor< SCEVAffinator, PWACtx >

friend struct llvm::SCEVVisitor< SCEVAffinator, PWACtx >

friend

Definition at line 119 of file SCEVAffinator.h.

Member Data Documentation

◆ BB

llvm::BasicBlock* polly::SCEVAffinator::BB

private

Definition at line 68 of file SCEVAffinator.h.

Referenced by checkForWrapping(), complexityBailout(), getPwAff(), getScope(), takeNonNegativeAssumption(), visit(), and visitTruncateExpr().

◆ CachedExpressions

llvm::DenseMap<CacheKey, PWACtx> polly::SCEVAffinator::CachedExpressions

private

Map to remembered cached expressions.

Definition at line 61 of file SCEVAffinator.h.

Referenced by hasNSWAddRecForLoop(), and visit().

◆ Ctx

isl::ctx polly::SCEVAffinator::Ctx

private

Definition at line 64 of file SCEVAffinator.h.

Referenced by addModuloSemantic(), getPWACtxFromPWA(), visit(), visitAddRecExpr(), visitConstant(), and visitUnknown().

◆ LI

llvm::LoopInfo& polly::SCEVAffinator::LI

private

Definition at line 67 of file SCEVAffinator.h.

Referenced by getLI(), and getScope().

◆ NumIterators

unsigned polly::SCEVAffinator::NumIterators

private

Definition at line 65 of file SCEVAffinator.h.

Referenced by getPWACtxFromPWA(), getPwAff(), visit(), visitAddRecExpr(), visitConstant(), and visitUnknown().

◆ RecordedAssumptions

RecordedAssumptionsTy* polly::SCEVAffinator::RecordedAssumptions = nullptr

private

Definition at line 69 of file SCEVAffinator.h.

Referenced by checkForWrapping(), getPwAff(), takeNonNegativeAssumption(), visitTruncateExpr(), visitUDivExpr(), and visitZeroExtendExpr().

◆ S

Scop* polly::SCEVAffinator::S

private

Definition at line 63 of file SCEVAffinator.h.

◆ SE

llvm::ScalarEvolution& polly::SCEVAffinator::SE

private

Definition at line 66 of file SCEVAffinator.h.

Referenced by complexityBailout(), visit(), visitAddRecExpr(), visitSDivInstruction(), visitSRemInstruction(), visitUDivExpr(), and visitUnknown().

◆ TD

const llvm::DataLayout& polly::SCEVAffinator::TD

private

Target data for element size computing.

Definition at line 72 of file SCEVAffinator.h.

Referenced by addModuloSemantic(), computeModuloForExpr(), visitTruncateExpr(), visitUDivExpr(), and visitZeroExtendExpr().

The documentation for this class was generated from the following files:

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ CacheKey

Constructor & Destructor Documentation

◆ SCEVAffinator()

Member Function Documentation

◆ addModuloSemantic()

◆ checkForWrapping()

◆ complexityBailout()

◆ computeModuloForExpr()

◆ getLI()

◆ getPWACtxFromPWA()

◆ getPwAff()

◆ getScope()

◆ hasNSWAddRecForLoop()

◆ interpretAsUnsigned()

◆ takeNonNegativeAssumption()

◆ visit()

◆ visitAddExpr()

◆ visitAddRecExpr()

◆ visitConstant()

◆ visitMulExpr()

◆ visitPtrToIntExpr()

◆ visitSDivInstruction()

◆ visitSequentialUMinExpr()

◆ visitSignExtendExpr()

◆ visitSMaxExpr()

◆ visitSMinExpr()

◆ visitSRemInstruction()

◆ visitTruncateExpr()

◆ visitUDivExpr()

◆ visitUMaxExpr()

◆ visitUMinExpr()

◆ visitUnknown()

◆ visitVScale()

◆ visitZeroExtendExpr()

Friends And Related Function Documentation

◆ llvm::SCEVVisitor< SCEVAffinator, PWACtx >

Member Data Documentation

◆ BB

◆ CachedExpressions

◆ Ctx

◆ LI

◆ NumIterators

◆ RecordedAssumptions

◆ S

◆ SE

◆ TD