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, bool IsInsideDomain=true)
	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 the 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	visitPtrToAddrExpr (const llvm::SCEVPtrToAddrExpr *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
bool	IsInsideDomain = true
	Whether the evaluation takes place only when `BB's` domain has already been checked.
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 67 of file SCEVAffinator.h.

Constructor & Destructor Documentation

◆ SCEVAffinator()

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

Definition at line 84 of file SCEVAffinator.cpp.

References Ctx, LI, S, SE, and TD.

Referenced by llvm::SCEVVisitor< SCEVAffinator, PWACtx >.

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 162 of file SCEVAffinator.cpp.

References isl::checked::pw_aff::add(), Ctx, Domain, isl::checked::pw_aff::domain(), getWidthExpValOnDomain(), isl::val::int_from_ui(), isl::checked::manage(), isl::checked::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 134 of file SCEVAffinator.cpp.

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

Referenced by visit().

◆ complexityBailout()

PWACtx SCEVAffinator::complexityBailout ( )

private

Definition at line 581 of file SCEVAffinator.cpp.

References BB, polly::COMPLEXITY, S, 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 190 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 the object.

Definition at line 63 of file SCEVAffinator.h.

References LI.

◆ 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,
		bool	IsInsideDomain = true )

Translate a SCEV to an isl::pw_aff.

Parameters

E	The expression that is translated.
BB	The block in which `E` is executed.
RecordedAssumptions	If set, assumptions that make the translation valid are added here.
IsInsideDomain	If true, assumptions only need to apply during the execution of `BB`. That is, when we know that we are in its domain. Must be false if the SCEV is evaluated outside a ScopStmt, or for code that computes the domain (since while doing that, we don't know whether we are in the domain yet).

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

Definition at line 117 of file SCEVAffinator.cpp.

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

◆ 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 176 of file SCEVAffinator.cpp.

References CachedExpressions.

◆ 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::checked::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::checked::manage(), polly::recordAssumption(), RecordedAssumptions, and polly::UNSIGNED.

Referenced by visitUDivExpr(), and visitZeroExtendExpr().

◆ visit()

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

private

Definition at line 199 of file SCEVAffinator.cpp.

References addModuloSemantic(), BB, CachedExpressions, checkForWrapping(), combine(), computeModuloForExpr(), Ctx, Domain, polly::extractConstantFactor(), 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, isl_set_universe(), isl_space_copy(), isl_space_set_alloc(), isl_space_set_dim_id(), isl::checked::manage(), NumIterators, S, SE, and visitConstant().

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

◆ visitAddExpr()

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

private

Definition at line 384 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 408 of file SCEVAffinator.cpp.

References assert, combine(), Ctx, 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::checked::manage(), NumIterators, S, SE, and visit().

◆ visitConstant()

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

private

Definition at line 250 of file SCEVAffinator.cpp.

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

Referenced by visit().

◆ visitMulExpr()

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

private

Definition at line 396 of file SCEVAffinator.cpp.

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

◆ visitPtrToAddrExpr()

PWACtx SCEVAffinator::visitPtrToAddrExpr ( const llvm::SCEVPtrToAddrExpr * E )

private

Definition at line 276 of file SCEVAffinator.cpp.

References visit().

◆ visitPtrToIntExpr()

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

private

Definition at line 280 of file SCEVAffinator.cpp.

References visit().

◆ visitSDivInstruction()

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

private

Definition at line 522 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 480 of file SCEVAffinator.cpp.

◆ visitSignExtendExpr()

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

private

Definition at line 379 of file SCEVAffinator.cpp.

References visit().

◆ visitSMaxExpr()

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

private

Definition at line 447 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 459 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 539 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

◆ visitUDivExpr()

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

private

Definition at line 484 of file SCEVAffinator.cpp.

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

◆ visitUMaxExpr()

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

private

Definition at line 471 of file SCEVAffinator.cpp.

◆ visitUMinExpr()

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

private

Definition at line 475 of file SCEVAffinator.cpp.

◆ visitUnknown()

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

private

Definition at line 556 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 272 of file SCEVAffinator.cpp.

◆ visitZeroExtendExpr()

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

private

Definition at line 319 of file SCEVAffinator.cpp.

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

◆ llvm::SCEVVisitor< SCEVAffinator, PWACtx >

friend struct llvm::SCEVVisitor< SCEVAffinator, PWACtx >

friend

Definition at line 135 of file SCEVAffinator.h.

References SCEVAffinator().

Member Data Documentation

◆ BB

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

private

Definition at line 77 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 70 of file SCEVAffinator.h.

Referenced by hasNSWAddRecForLoop(), and visit().

◆ Ctx

isl::ctx polly::SCEVAffinator::Ctx

private

Definition at line 73 of file SCEVAffinator.h.

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

◆ IsInsideDomain

bool polly::SCEVAffinator::IsInsideDomain = true

private

Whether the evaluation takes place only when BB's domain has already been checked.

See also: getPwAff

Definition at line 82 of file SCEVAffinator.h.

Referenced by getPwAff(), and visitTruncateExpr().

◆ LI

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

private

Definition at line 76 of file SCEVAffinator.h.

Referenced by getLI(), getScope(), and SCEVAffinator().

◆ NumIterators

unsigned polly::SCEVAffinator::NumIterators

private

Definition at line 74 of file SCEVAffinator.h.

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

◆ RecordedAssumptions

RecordedAssumptionsTy* polly::SCEVAffinator::RecordedAssumptions = nullptr

private

Definition at line 84 of file SCEVAffinator.h.

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

◆ S

Scop* polly::SCEVAffinator::S

private

Definition at line 72 of file SCEVAffinator.h.

Referenced by complexityBailout(), getPwAff(), SCEVAffinator(), visit(), and visitAddRecExpr().

◆ SE

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

private

Definition at line 75 of file SCEVAffinator.h.

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

◆ TD

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

private

Target data for element size computing.

Definition at line 87 of file SCEVAffinator.h.

Referenced by addModuloSemantic(), computeModuloForExpr(), SCEVAffinator(), 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()

◆ visitPtrToAddrExpr()

◆ visitPtrToIntExpr()

◆ visitSDivInstruction()

◆ visitSequentialUMinExpr()

◆ visitSignExtendExpr()

◆ visitSMaxExpr()

◆ visitSMinExpr()

◆ visitSRemInstruction()

◆ visitTruncateExpr()

◆ visitUDivExpr()

◆ visitUMaxExpr()

◆ visitUMinExpr()

◆ visitUnknown()

◆ visitVScale()

◆ visitZeroExtendExpr()

Friends And Related Symbol Documentation

◆ llvm::SCEVVisitor< SCEVAffinator, PWACtx >

Member Data Documentation

◆ BB

◆ CachedExpressions

◆ Ctx

◆ IsInsideDomain

◆ LI

◆ NumIterators

◆ RecordedAssumptions

◆ S

◆ SE

◆ TD