Represent memory accesses in statements. More...

#include <ScopInfo.h>

Public Types
enum	AccessType { READ = 0x1 , MUST_WRITE = 0x2 , MAY_WRITE = 0x3 }
	The access type of a memory access. More...

enum	ReductionType { RT_NONE , RT_ADD , RT_MUL , RT_BOR , RT_BXOR , RT_BAND , RT_BOTTOM }
	Reduction access type. More...

using	SubscriptsTy = SmallVector< const SCEV *, 4 >

Public Member Functions
	MemoryAccess (ScopStmt Stmt, Instruction AccessInst, AccessType AccType, Value BaseAddress, Type ElemType, bool Affine, ArrayRef< const SCEV * > Subscripts, ArrayRef< const SCEV * > Sizes, Value *AccessValue, MemoryKind Kind)
	Create a new MemoryAccess.

	MemoryAccess (ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
	Create a new MemoryAccess that corresponds to `AccRel`.

	MemoryAccess (const MemoryAccess &)=delete

MemoryAccess &	operator= (const MemoryAccess &)=delete

	~MemoryAccess ()

void	addIncoming (BasicBlock IncomingBlock, Value IncomingValue)
	Add a new incoming block/value pairs for this PHI/ExitPHI access.

ArrayRef< std::pair< BasicBlock , Value > >	getIncoming () const
	Return the list of possible PHI/ExitPHI values.

enum AccessType	getType ()
	Get the type of a memory access.

bool	isReductionLike () const
	Is this a reduction like access?

bool	isRead () const
	Is this a read memory access?

bool	isMustWrite () const
	Is this a must-write memory access?

bool	isMayWrite () const
	Is this a may-write memory access?

bool	isWrite () const
	Is this a write memory access?

bool	isMemoryIntrinsic () const
	Is this a memory intrinsic access (memcpy, memset, memmove)?

bool	hasNewAccessRelation () const
	Check if a new access relation was imported or set by a pass.

isl::map	getLatestAccessRelation () const
	Return the newest access relation of this access.

isl::map	getAccessRelation () const
	Old name of getLatestAccessRelation().

isl::map	getAddressFunction () const
	Get an isl map describing the memory address accessed.

isl::pw_multi_aff	applyScheduleToAccessRelation (isl::union_map Schedule) const
	Return the access relation after the schedule was applied.

std::string	getOriginalAccessRelationStr () const
	Get an isl string representing the access function read from IR.

std::string	getNewAccessRelationStr () const
	Get an isl string representing a new access function, if available.

std::string	getAccessRelationStr () const
	Get an isl string representing the latest access relation.

Value *	getOriginalBaseAddr () const
	Get the original base address of this access (e.g.

isl::id	getOriginalArrayId () const
	Get the detection-time base array isl::id for this access.

isl::id	getLatestArrayId () const
	Get the base array isl::id for this access, modifiable through setNewAccessRelation().

isl::id	getArrayId () const
	Old name of getOriginalArrayId().

const ScopArrayInfo *	getOriginalScopArrayInfo () const
	Get the detection-time ScopArrayInfo object for the base address.

const ScopArrayInfo *	getLatestScopArrayInfo () const
	Get the ScopArrayInfo object for the base address, or the one set by setNewAccessRelation().

const ScopArrayInfo *	getScopArrayInfo () const
	Legacy name of getOriginalScopArrayInfo().

const std::string	getReductionOperatorStr () const
	Return a string representation of the access's reduction type.

Type *	getElementType () const
	Return the element type of the accessed array wrt. this access.

Value *	getAccessValue () const
	Return the access value of this memory access.

Value *	tryGetValueStored ()
	Return llvm::Value that is stored by this access, if available.

Instruction *	getAccessInstruction () const
	Return the access instruction of this memory access.

iterator_range< SubscriptsTy::const_iterator >	subscripts () const
	Return an iterator range containing the subscripts.

unsigned	getNumSubscripts () const
	Return the number of access function subscript.

const SCEV *	getSubscript (unsigned Dim) const
	Return the access function subscript in the dimension `Dim`.

isl::pw_aff	getPwAff (const SCEV *E)
	Compute the isl representation for the SCEV `E` wrt.

isl::set	getInvalidDomain () const
	Get the invalid domain for this access.

isl::set	getInvalidContext () const
	Get the invalid context for this access.

isl::set	getStride (isl::map Schedule) const
	Get the stride of this memory access in the specified Schedule.

bool	isStrideX (isl::map Schedule, int StrideWidth) const
	Is the stride of the access equal to a certain width? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

bool	isStrideOne (isl::map Schedule) const
	Is consecutive memory accessed for a given statement instance set? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

bool	isStrideZero (isl::map Schedule) const
	Is always the same memory accessed for a given statement instance set? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

MemoryKind	getOriginalKind () const
	Return the kind when this access was first detected.

MemoryKind	getLatestKind () const
	Return the kind considering a potential setNewAccessRelation.

bool	isOriginalArrayKind () const
	Whether this is an access of an explicit load or store in the IR.

bool	isLatestArrayKind () const
	Whether storage memory is either an custom .s2a/.phiops alloca (false) or an existing pointer into an array (true).

bool	isArrayKind () const
	Old name of isOriginalArrayKind.

bool	isOriginalScalarKind () const
	Whether this access is an array to a scalar memory object, without considering changes by setNewAccessRelation.

bool	isLatestScalarKind () const
	Whether this access is an array to a scalar memory object, also considering changes by setNewAccessRelation.

bool	isScalarKind () const
	Old name of isOriginalScalarKind.

bool	isOriginalValueKind () const
	Was this MemoryAccess detected as a scalar dependences?

bool	isLatestValueKind () const
	Is this MemoryAccess currently modeling scalar dependences?

bool	isValueKind () const
	Old name of isOriginalValueKind().

bool	isOriginalPHIKind () const
	Was this MemoryAccess detected as a special PHI node access?

bool	isLatestPHIKind () const
	Is this MemoryAccess modeling special PHI node accesses, also considering a potential change by setNewAccessRelation?

bool	isPHIKind () const
	Old name of isOriginalPHIKind.

bool	isOriginalExitPHIKind () const
	Was this MemoryAccess detected as the accesses of a PHI node in the SCoP's exit block?

bool	isLatestExitPHIKind () const
	Is this MemoryAccess modeling the accesses of a PHI node in the SCoP's exit block? Can be changed to an array access using setNewAccessRelation().

bool	isExitPHIKind () const
	Old name of isOriginalExitPHIKind().

bool	isOriginalAnyPHIKind () const
	Was this access detected as one of the two PHI types?

bool	isLatestAnyPHIKind () const
	Does this access originate from one of the two PHI types? Can be changed to an array access using setNewAccessRelation().

bool	isAnyPHIKind () const
	Old name of isOriginalAnyPHIKind().

ScopStmt *	getStatement () const
	Get the statement that contains this memory access.

ReductionType	getReductionType () const
	Get the reduction type of this access.

void	setAccessRelation (isl::map AccessRelation)
	Update the original access relation.

void	setNewAccessRelation (isl::map NewAccessRelation)
	Set the updated access relation read from JSCOP file.

bool	isLatestPartialAccess () const
	Return whether the MemoryyAccess is a partial access.

void	markAsReductionLike (ReductionType RT)
	Mark this a reduction like access.

void	realignParams ()
	Align the parameters in the access relation to the scop context.

void	updateDimensionality ()
	Update the dimensionality of the memory access.

isl::id	getId () const
	Get identifier for the memory access.

void	print (raw_ostream &OS) const
	Print the MemoryAccess.

void	dump () const
	Print the MemoryAccess to stderr.

bool	isAffine () const
	Is the memory access affine?

Static Public Member Functions
static const std::string	getReductionOperatorStr (ReductionType RT)
	Return a string representation of the reduction type `RT`.

Private Member Functions
isl::basic_map	createBasicAccessMap (ScopStmt *Statement)

isl::set	assumeNoOutOfBound ()

void	computeBoundsOnAccessRelation (unsigned ElementSize)
	Compute bounds on an over approximated access relation.

isl::map	getOriginalAccessRelation () const
	Get the original access function as read from IR.

isl::space	getOriginalAccessRelationSpace () const
	Return the space in which the access relation lives in.

isl::map	getNewAccessRelation () const
	Get the new access function imported or set by a pass.

void	foldAccessRelation ()
	Fold the memory access to consider parametric offsets.

void	buildMemIntrinsicAccessRelation ()
	Create the access relation for the underlying memory intrinsic.

void	buildAccessRelation (const ScopArrayInfo *SAI)
	Assemble the access relation from all available information.

void	wrapConstantDimensions ()
	Carry index overflows of dimensions with constant size to the next higher dimension.

Private Attributes
isl::id	Id
	A unique identifier for this memory access.

MemoryKind	Kind
	What is modeled by this MemoryAccess.

enum AccessType	AccType
	Whether it a reading or writing access, and if writing, whether it is conditional (MAY_WRITE).

ReductionType	RedType = RT_NONE
	Reduction type for reduction like accesses, RT_NONE otherwise.

ScopStmt *	Statement
	Parent ScopStmt of this access.

isl::set	InvalidDomain
	The domain under which this access is not modeled precisely.

AssertingVH< Value >	BaseAddr
	The base address (e.g., A for A[i+j]).

Type *	ElementType
	Type a single array element wrt. this access.

SmallVector< const SCEV *, 4 >	Sizes
	Size of each dimension of the accessed array.

Instruction *	AccessInstruction = nullptr
	The access instruction of this memory access.

SmallVector< std::pair< BasicBlock , Value >, 4 >	Incoming
	Incoming block and value of a PHINode.

AssertingVH< Value >	AccessValue
	The value associated with this memory access.

bool	IsAffine = true
	Are all the subscripts affine expression?

SubscriptsTy	Subscripts
	Subscript expression for each dimension.

isl::map	AccessRelation
	Relation from statement instances to the accessed array elements.

isl::map	NewAccessRelation
	Updated access relation read from JSCOP file.

Friends
class	Scop

class	ScopStmt

class	ScopBuilder

Detailed Description

Represent memory accesses in statements.

Definition at line 431 of file ScopInfo.h.

Member Typedef Documentation

◆ SubscriptsTy

using polly::MemoryAccess::SubscriptsTy = SmallVector<const SCEV *, 4>

Definition at line 477 of file ScopInfo.h.

Member Enumeration Documentation

◆ AccessType

enum polly::MemoryAccess::AccessType

The access type of a memory access.

There are three kind of access types:

A read access

A certain set of memory locations are read and may be used for internal calculations.

A must-write access

A certain set of memory locations is definitely written. The old value is replaced by a newly calculated value. The old value is not read or used at all.

A may-write access

A certain set of memory locations may be written. The memory location may contain a new value if there is actually a write or the old value may remain, if no write happens.

Enumerator
READ
MUST_WRITE
MAY_WRITE

Definition at line 457 of file ScopInfo.h.

◆ ReductionType

enum polly::MemoryAccess::ReductionType

Reduction access type.

Commutative and associative binary operations suitable for reductions

Enumerator
RT_NONE	Indicate no reduction at all.
RT_ADD	Addition.
RT_MUL	Multiplication.
RT_BOR	Bitwise Or.
RT_BXOR	Bitwise XOr.
RT_BAND	Bitwise And.
RT_BOTTOM	Pseudo type for the data flow analysis.

Definition at line 466 of file ScopInfo.h.

Constructor & Destructor Documentation

◆ MemoryAccess() [1/3]

MemoryAccess::MemoryAccess	(	ScopStmt *	Stmt,
		Instruction *	AccessInst,
		AccessType	AccType,
		Value *	BaseAddress,
		Type *	ElemType,
		bool	Affine,
		ArrayRef< const SCEV * >	Subscripts,
		ArrayRef< const SCEV * >	Sizes,
		Value *	AccessValue,
		MemoryKind	Kind
	)

Create a new MemoryAccess.

Parameters

Stmt	The parent statement.
AccessInst	The instruction doing the access.
BaseAddr	The accessed array's address.
ElemType	The type of the accessed array elements.
AccType	Whether read or write access.
IsAffine	Whether the subscripts are affine expressions.
Kind	The kind of memory accessed.
Subscripts	Subscript expressions
Sizes	Dimension lengths of the accessed array.

Definition at line 863 of file ScopInfo.cpp.

References AccType, isl::id::alloc(), polly::ScopStmt::getBaseName(), polly::Scop::getIslCtx(), polly::ScopStmt::getParent(), Id, and polly::ScopStmt::size().

◆ MemoryAccess() [2/3]

MemoryAccess::MemoryAccess	(	ScopStmt *	Stmt,
		AccessType	AccType,
		isl::map	AccRel
	)

Create a new MemoryAccess that corresponds to AccRel.

Along with Stmt and AccType it uses information about dimension lengths of the accessed array, the type of the accessed array elements, the name of the accessed array that is derived from the object accessible via AccRel.

Parameters

Stmt	The parent statement.
AccType	Whether read or write access.
AccRel	The access relation that describes the memory access.

Definition at line 882 of file ScopInfo.cpp.

References AccType, isl::id::alloc(), BaseAddr, ElementType, isl::map::get_tuple_id(), polly::ScopStmt::getBaseName(), polly::ScopArrayInfo::getFromId(), polly::Scop::getIslCtx(), polly::ScopStmt::getParent(), Id, NewAccessRelation, isl::out, polly::ScopStmt::size(), and Sizes.

◆ MemoryAccess() [3/3]

polly::MemoryAccess::MemoryAccess ( const MemoryAccess & )

delete

◆ ~MemoryAccess()

MemoryAccess::~MemoryAccess ( )

default

Member Function Documentation

◆ addIncoming()

void polly::MemoryAccess::addIncoming	(	BasicBlock *	IncomingBlock,
		Value *	IncomingValue
	)

inline

Add a new incoming block/value pairs for this PHI/ExitPHI access.

Parameters

IncomingBlock	The PHI's incoming block.
IncomingValue	The value when reaching the PHI from the `IncomingBlock`.

Definition at line 736 of file ScopInfo.h.

References assert, Incoming, isAnyPHIKind(), and isRead().

Referenced by polly::ScopBuilder::ensurePHIWrite().

◆ applyScheduleToAccessRelation()

isl::pw_multi_aff MemoryAccess::applyScheduleToAccessRelation ( isl::union_map Schedule ) const

Return the access relation after the schedule was applied.

Definition at line 582 of file ScopInfo.cpp.

References isl::map::apply_domain(), isl::pw_multi_aff::from_map(), isl::map::from_union_map(), getAddressFunction(), polly::ScopStmt::getDomain(), getStatement(), and isl::union_map::intersect_domain().

◆ assumeNoOutOfBound()

isl::set MemoryAccess::assumeNoOutOfBound ( )

private

◆ buildAccessRelation()

void MemoryAccess::buildAccessRelation ( const ScopArrayInfo * SAI )

private

Assemble the access relation from all available information.

In particular, used the information passes in the constructor and the parent ScopStmt set by setStatment().

Parameters

SAI	Info object for the accessed array.

Definition at line 817 of file ScopInfo.cpp.

References AccessRelation, assert, buildMemIntrinsicAccessRelation(), createBasicAccessMap(), isl::id::ctx(), Ctx, isl::set::empty(), isl::map::flat_range_product(), isl::map::from_pw_aff(), isl::set::get_space(), isl::space::get_tuple_id(), getAccessInstruction(), polly::ScopArrayInfo::getBasePtrId(), polly::ScopStmt::getDomain(), polly::ScopStmt::getDomainSpace(), polly::ScopStmt::getInvalidDomain(), polly::ScopStmt::getNumIterators(), getPwAff(), getStatement(), isl::map::gist_domain(), Id, isl::in, InvalidDomain, isl::map::is_null(), isAffine(), isl::out, isl::set, isl::map::set_tuple_id(), Statement, Subscripts, and isl::map::universe().

Referenced by polly::ScopBuilder::buildAccessRelations(), and polly::ScopStmt::ensureValueRead().

◆ buildMemIntrinsicAccessRelation()

void MemoryAccess::buildMemIntrinsicAccessRelation ( )

private

Create the access relation for the underlying memory intrinsic.

Definition at line 681 of file ScopInfo.cpp.

References AccessRelation, isl::map::align_params(), isl::map::apply_range(), assert, isl::map::from_pw_aff(), isl::map::get_space(), getPwAff(), getStatement(), isl::in, isMemoryIntrinsic(), isl::map::lex_gt(), isl::map::lower_bound_si(), isl::out, isl::space::range(), isl::map::set_tuple_id(), Sizes, Subscripts, isl::map::sum(), and isl::map::universe().

Referenced by buildAccessRelation().

◆ computeBoundsOnAccessRelation()

void MemoryAccess::computeBoundsOnAccessRelation ( unsigned ElementSize )

private

Compute bounds on an over approximated access relation.

Parameters

ElementSize The size of one element accessed.

Definition at line 705 of file ScopInfo.cpp.

References AccessRelation, addRangeBoundsToSet(), assert, getAccessInstruction(), polly::ScopStmt::getParent(), polly::Scop::getSE(), isl::map::intersect_range(), Range, isl::map::range(), isl::set, Statement, and polly::Value.

Referenced by updateDimensionality().

◆ createBasicAccessMap()

isl::basic_map MemoryAccess::createBasicAccessMap ( ScopStmt * Statement )

private

Definition at line 617 of file ScopInfo.cpp.

References isl::space::align_params(), isl::basic_map::from_domain_and_range(), polly::ScopStmt::getDomainSpace(), polly::ScopStmt::getIslCtx(), Statement, and isl::basic_set::universe().

Referenced by buildAccessRelation().

◆ dump()

LLVM_DUMP_METHOD void MemoryAccess::dump ( ) const

Print the MemoryAccess to stderr.

Definition at line 955 of file ScopInfo.cpp.

References print().

Referenced by checkCandidatePairAccesses().

◆ foldAccessRelation()

void MemoryAccess::foldAccessRelation ( )

private

Fold the memory access to consider parametric offsets.

To recover memory accesses with array size parameters in the subscript expression we post-process the delinearization results.

We would normally recover from an access A[exp0(i) * N + exp1(i)] into an array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the range of exp1(i) - may be preferable. Specifically, for cases where we know exp1(i) is negative, we want to choose the latter expression.

As we commonly do not have any information about the range of exp1(i), we do not choose one of the two options, but instead create a piecewise access function that adds the (-1, N) offsets as soon as exp1(i) becomes negative. For a 2D array such an access function is created by applying the piecewise map:

[i,j] -> [i, j] : j >= 0 [i,j] -> [i-1, j+N] : j < 0

We can generalize this mapping to arbitrary dimensions by applying this piecewise mapping pairwise from the rightmost to the leftmost access dimension. It would also be possible to cover a wider range by introducing more cases and adding multiple of Ns to these cases. However, this has not yet been necessary. The introduction of different cases necessarily complicates the memory access function, but cases that can be statically proven to not happen will be eliminated later on.

Definition at line 750 of file ScopInfo.cpp.

References AccessRelation, isl::map::add_constraint(), isl::space::align_params(), isl::constraint::alloc_equality(), isl::map::apply_range(), C, isl::map::equate(), isl::space::find_dim_by_id(), isl::space::get_dim_id(), isl::map::get_space(), isl::pw_aff::get_space(), isl::space::get_tuple_id(), polly::ScopArrayInfo::getBasePtrId(), polly::ScopStmt::getDomain(), polly::ScopStmt::getDomainSpace(), getPwAff(), getScopArrayInfo(), isl::map::gist_domain(), isl::in, isl::map::lower_bound_si(), isl::space::map_from_set(), isl::map::n_basic_map(), NewAccessRelation, isl::out, isl::param, PollyPreciseFoldAccesses(), isl::space::range(), isl::size::release(), isl::set, isl::map::set_tuple_id(), Sizes, Statement, Subscripts, isl::map::unite(), isl::map::universe(), and isl::map::upper_bound_si().

◆ getAccessInstruction()

Instruction * polly::MemoryAccess::getAccessInstruction ( ) const

inline

Return the access instruction of this memory access.

Definition at line 885 of file ScopInfo.h.

References AccessInstruction.

Referenced by polly::ScopStmt::addAccess(), polly::Scop::addAccessFunction(), polly::ZoneAlgorithm::addArrayReadAccess(), buildAccessRelation(), polly::RegionGenerator::buildExitPHI(), polly::ScopBuilder::canAlwaysBeHoisted(), polly::ScopBuilder::checkForReductions(), computeBoundsOnAccessRelation(), polly::ScopBuilder::getNonHoistableCtx(), polly::ZoneAlgorithm::getWrittenValue(), polly::ZoneAlgorithm::isCompatibleAccess(), isMemoryIntrinsic(), polly::ZoneAlgorithm::isNormalizable(), polly::IslNodeBuilder::preloadInvariantEquivClass(), polly::IslNodeBuilder::preloadInvariantLoad(), polly::Scop::removeAccessData(), polly::ScopStmt::removeAccessData(), polly::ScopStmt::removeMemoryAccess(), and polly::ScopStmt::removeSingleMemoryAccess().

◆ getAccessRelation()

isl::map polly::MemoryAccess::getAccessRelation ( ) const

inline

Old name of getLatestAccessRelation().

Definition at line 795 of file ScopInfo.h.

References getLatestAccessRelation().

Referenced by assumeNoOutOfBound(), checkCandidatePairAccesses(), polly::BlockGenerator::generateArrayStore(), getAccessRelationStr(), getAddressFunction(), polly::ScopBuilder::getNonHoistableCtx(), and getStride().

◆ getAccessRelationStr()

std::string MemoryAccess::getAccessRelationStr ( ) const

Get an isl string representing the latest access relation.

Definition at line 613 of file ScopInfo.cpp.

References getAccessRelation().

◆ getAccessValue()

Value * polly::MemoryAccess::getAccessValue ( ) const

inline

Return the access value of this memory access.

Definition at line 867 of file ScopInfo.h.

References AccessValue, and polly::Value.

Referenced by polly::ScopStmt::addAccess(), polly::Scop::addAccessFunction(), polly::BlockGenerator::generateLocationAccessed(), polly::RegionGenerator::getExitScalar(), polly::BlockGenerator::getImplicitAddress(), polly::ZoneAlgorithm::getWrittenValue(), isEscaping(), polly::Scop::removeAccessData(), and polly::ScopStmt::removeAccessData().

◆ getAddressFunction()

isl::map MemoryAccess::getAddressFunction ( ) const

Get an isl map describing the memory address accessed.

In most cases the memory address accessed is well described by the access relation obtained with getAccessRelation. However, in case of arrays accessed with types of different size the access relation maps one access to multiple smaller address locations. This method returns an isl map that relates each dynamic statement instance to the unique memory location that is loaded from / stored to.

For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method will return the address function { S[i] -> A[4i] }.

Returns: The address function for this memory access.

Definition at line 577 of file ScopInfo.cpp.

References getAccessRelation(), and isl::map::lexmin().

Referenced by applyScheduleToAccessRelation(), and polly::IslNodeBuilder::preloadInvariantLoad().

◆ getArrayId()

isl::id polly::MemoryAccess::getArrayId ( ) const

inline

Old name of getOriginalArrayId().

Definition at line 843 of file ScopInfo.h.

References getOriginalArrayId().

Referenced by getOriginalScopArrayInfo(), and tag().

◆ getElementType()

Type * polly::MemoryAccess::getElementType ( ) const

inline

Return the element type of the accessed array wrt. this access.

Definition at line 864 of file ScopInfo.h.

References ElementType.

Referenced by polly::ScopBuilder::buildAccessRelations(), and updateDimensionality().

◆ getId()

isl::id MemoryAccess::getId ( ) const

Get identifier for the memory access.

This identifier is unique for all accesses that belong to the same scop statement.

Definition at line 917 of file ScopInfo.cpp.

References Id.

Referenced by polly::BlockGenerator::generateArrayStore(), polly::BlockGenerator::generateLocationAccessed(), polly::BlockGenerator::getImplicitAddress(), and tag().

◆ getIncoming()

ArrayRef< std::pair< BasicBlock *, Value * > > polly::MemoryAccess::getIncoming ( ) const

inline

Return the list of possible PHI/ExitPHI values.

After code generation moves some PHIs around during region simplification, we cannot reliably locate the original PHI node and its incoming values anymore. For this reason we remember these explicitly for all PHI-kind accesses.

Definition at line 748 of file ScopInfo.h.

References assert, Incoming, and isAnyPHIKind().

Referenced by polly::RegionGenerator::buildExitPHI(), and polly::RegionGenerator::getExitScalar().

◆ getInvalidContext()

isl::set polly::MemoryAccess::getInvalidContext ( ) const

inline

Get the invalid context for this access.

Definition at line 907 of file ScopInfo.h.

References getInvalidDomain(), and isl::set::params().

◆ getInvalidDomain()

isl::set polly::MemoryAccess::getInvalidDomain ( ) const

inline

Get the invalid domain for this access.

Definition at line 904 of file ScopInfo.h.

References InvalidDomain.

Referenced by getInvalidContext().

◆ getLatestAccessRelation()

isl::map polly::MemoryAccess::getLatestAccessRelation ( ) const

inline

Return the newest access relation of this access.

There are two possibilities: 1) The original access relation read from the LLVM-IR. 2) A new access relation imported from a json file or set by another pass (e.g., for privatization).

As 2) is by construction "newer" than 1) we return the new access relation if present.

Definition at line 789 of file ScopInfo.h.

References getNewAccessRelation(), getOriginalAccessRelation(), and hasNewAccessRelation().

Referenced by getAccessRelation(), polly::ZoneAlgorithm::getAccessRelationFor(), and isLatestPartialAccess().

◆ getLatestArrayId()

isl::id MemoryAccess::getLatestArrayId ( ) const

Get the base array isl::id for this access, modifiable through setNewAccessRelation().

Definition at line 571 of file ScopInfo.cpp.

References isl::map::get_tuple_id(), getOriginalArrayId(), hasNewAccessRelation(), NewAccessRelation, and isl::out.

Referenced by getLatestScopArrayInfo().

◆ getLatestKind()

MemoryKind polly::MemoryAccess::getLatestKind ( ) const

inline

Return the kind considering a potential setNewAccessRelation.

Definition at line 939 of file ScopInfo.h.

References polly::ScopArrayInfo::getKind(), and getLatestScopArrayInfo().

Referenced by isLatestArrayKind(), isLatestExitPHIKind(), isLatestPHIKind(), isLatestScalarKind(), and isLatestValueKind().

◆ getLatestScopArrayInfo()

const ScopArrayInfo * MemoryAccess::getLatestScopArrayInfo ( ) const

Get the ScopArrayInfo object for the base address, or the one set by setNewAccessRelation().

Definition at line 560 of file ScopInfo.cpp.

References isl::id::get_user(), and getLatestArrayId().

Referenced by getLatestKind(), polly::BlockGenerator::getOrCreateAlloca(), and polly::ZoneAlgorithm::getWrittenValue().

◆ getNewAccessRelation()

isl::map MemoryAccess::getNewAccessRelation ( ) const

private

Get the new access function imported or set by a pass.

Definition at line 605 of file ScopInfo.cpp.

References NewAccessRelation.

Referenced by getLatestAccessRelation().

◆ getNewAccessRelationStr()

std::string MemoryAccess::getNewAccessRelationStr ( ) const

Get an isl string representing a new access function, if available.

Definition at line 609 of file ScopInfo.cpp.

References NewAccessRelation.

Referenced by print().

◆ getNumSubscripts()

unsigned polly::MemoryAccess::getNumSubscripts ( ) const

inline

Return the number of access function subscript.

Definition at line 893 of file ScopInfo.h.

References Subscripts.

◆ getOriginalAccessRelation()

isl::map MemoryAccess::getOriginalAccessRelation ( ) const

private

Get the original access function as read from IR.

Definition at line 593 of file ScopInfo.cpp.

References AccessRelation.

Referenced by getLatestAccessRelation().

◆ getOriginalAccessRelationSpace()

isl::space MemoryAccess::getOriginalAccessRelationSpace ( ) const

private

Return the space in which the access relation lives in.

Definition at line 601 of file ScopInfo.cpp.

References AccessRelation, and isl::map::get_space().

Referenced by assumeNoOutOfBound().

◆ getOriginalAccessRelationStr()

std::string MemoryAccess::getOriginalAccessRelationStr ( ) const

Get an isl string representing the access function read from IR.

Definition at line 597 of file ScopInfo.cpp.

References AccessRelation.

Referenced by print().

◆ getOriginalArrayId()

isl::id MemoryAccess::getOriginalArrayId ( ) const

Get the detection-time base array isl::id for this access.

Definition at line 567 of file ScopInfo.cpp.

References AccessRelation, isl::map::get_tuple_id(), and isl::out.

Referenced by getArrayId(), and getLatestArrayId().

◆ getOriginalBaseAddr()

Value * polly::MemoryAccess::getOriginalBaseAddr ( ) const

inline

Get the original base address of this access (e.g.

A for A[i+j]) when detected.

This address may differ from the base address referenced by the original ScopArrayInfo to which this array belongs, as this memory access may have been canonicalized to a ScopArrayInfo which has a different but identically-valued base pointer in case invariant load hoisting is enabled.

Definition at line 833 of file ScopInfo.h.

References BaseAddr, and polly::Value.

Referenced by polly::ScopBuilder::buildAccessRelations(), polly::ScopBuilder::hasNonHoistableBasePtrInScop(), polly::Scop::lookupBasePtrAccess(), and polly::IslNodeBuilder::preloadInvariantEquivClass().

◆ getOriginalKind()

MemoryKind polly::MemoryAccess::getOriginalKind ( ) const

inline

Return the kind when this access was first detected.

Definition at line 932 of file ScopInfo.h.

References assert, getOriginalScopArrayInfo(), and Kind.

Referenced by isOriginalArrayKind(), isOriginalExitPHIKind(), isOriginalPHIKind(), isOriginalScalarKind(), and isOriginalValueKind().

◆ getOriginalScopArrayInfo()

const ScopArrayInfo * MemoryAccess::getOriginalScopArrayInfo ( ) const

Get the detection-time ScopArrayInfo object for the base address.

Definition at line 553 of file ScopInfo.cpp.

References isl::id::get_user(), and getArrayId().

Referenced by polly::Scop::addAccessData(), getOriginalKind(), getScopArrayInfo(), and polly::ZoneAlgorithm::isNormalizable().

◆ getPwAff()

isl::pw_aff MemoryAccess::getPwAff ( const SCEV * E )

Compute the isl representation for the SCEV E wrt.

this access.

Note that this function will also adjust the invalid context accordingly.

Definition at line 958 of file ScopInfo.cpp.

References polly::ScopStmt::getDomain(), getStatement(), isl::set::intersect(), InvalidDomain, isl::set::reset_tuple_id(), and isl::set::unite().

Referenced by buildAccessRelation(), buildMemIntrinsicAccessRelation(), and foldAccessRelation().

◆ getReductionOperatorStr() [1/2]

const std::string MemoryAccess::getReductionOperatorStr ( ) const

Return a string representation of the access's reduction type.

Definition at line 913 of file ScopInfo.cpp.

References getReductionOperatorStr(), and getReductionType().

Referenced by getBrokenReductionsStr(), getReductionOperatorStr(), and polly::operator<<().

◆ getReductionOperatorStr() [2/2]

const std::string MemoryAccess::getReductionOperatorStr ( MemoryAccess::ReductionType RT )

static

Return a string representation of the reduction type RT.

Definition at line 531 of file ScopInfo.cpp.

References RT_ADD, RT_BAND, RT_BOR, RT_BOTTOM, RT_BXOR, RT_MUL, and RT_NONE.

◆ getReductionType()

ReductionType polly::MemoryAccess::getReductionType ( ) const

inline

Get the reduction type of this access.

Definition at line 1034 of file ScopInfo.h.

References RedType.

Referenced by getReductionOperatorStr(), and print().

◆ getScopArrayInfo()

const ScopArrayInfo * polly::MemoryAccess::getScopArrayInfo ( ) const

inline

Legacy name of getOriginalScopArrayInfo().

Definition at line 853 of file ScopInfo.h.

References getOriginalScopArrayInfo().

Referenced by assumeNoOutOfBound(), foldAccessRelation(), polly::Scop::getAccesses(), isUsedForIndirectHoistedLoad(), polly::IslNodeBuilder::preloadInvariantEquivClass(), polly::Scop::removeAccessData(), updateDimensionality(), and wrapConstantDimensions().

◆ getStatement()

ScopStmt * polly::MemoryAccess::getStatement ( ) const

inline

Get the statement that contains this memory access.

Definition at line 1031 of file ScopInfo.h.

References Statement.

Referenced by polly::ZoneAlgorithm::addArrayReadAccess(), polly::ZoneAlgorithm::addArrayWriteAccess(), applyScheduleToAccessRelation(), buildAccessRelation(), polly::RegionGenerator::buildExitPHI(), buildMemIntrinsicAccessRelation(), polly::VirtualUse::create(), getAccessDomain(), polly::ZoneAlgorithm::getDomainFor(), polly::RegionGenerator::getExitScalar(), polly::BlockGenerator::getImplicitAddress(), polly::ScopBuilder::getNonHoistableCtx(), getPwAff(), polly::ZoneAlgorithm::getScatterFor(), polly::ZoneAlgorithm::getWrittenValue(), isEscaping(), isLatestPartialAccess(), setNewAccessRelation(), and updateDimensionality().

◆ getStride()

isl::set MemoryAccess::getStride ( isl::map Schedule ) const

Get the stride of this memory access in the specified Schedule.

Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

Definition at line 1000 of file ScopInfo.cpp.

References AccessRelation, isl::map::apply_domain(), isl::map::apply_range(), isl::map::deltas(), isl::map::get_space(), getAccessRelation(), getEqualAndLarger(), isl::map::lexmin(), isl::space::range(), and isl::map::reverse().

Referenced by isStrideX().

◆ getSubscript()

const SCEV * polly::MemoryAccess::getSubscript ( unsigned Dim ) const

inline

Return the access function subscript in the dimension Dim.

Definition at line 896 of file ScopInfo.h.

References Subscripts.

◆ getType()

enum AccessType polly::MemoryAccess::getType ( )

inline

Get the type of a memory access.

Definition at line 754 of file ScopInfo.h.

References AccType.

◆ hasNewAccessRelation()

bool polly::MemoryAccess::hasNewAccessRelation ( ) const

inline

Check if a new access relation was imported or set by a pass.

Definition at line 777 of file ScopInfo.h.

References isl::map::is_null(), and NewAccessRelation.

Referenced by getLatestAccessRelation(), getLatestArrayId(), and print().

◆ isAffine()

bool polly::MemoryAccess::isAffine ( ) const

inline

Is the memory access affine?

Definition at line 1085 of file ScopInfo.h.

References IsAffine.

Referenced by buildAccessRelation(), polly::ScopBuilder::buildAccessRelations(), polly::ScopBuilder::getNonHoistableCtx(), and updateDimensionality().

◆ isAnyPHIKind()

bool polly::MemoryAccess::isAnyPHIKind ( ) const

inline

Old name of isOriginalAnyPHIKind().

Definition at line 1028 of file ScopInfo.h.

References isOriginalAnyPHIKind().

Referenced by polly::ScopStmt::addAccess(), addIncoming(), polly::RegionGenerator::getExitScalar(), getIncoming(), and tryGetValueStored().

◆ isArrayKind()

bool polly::MemoryAccess::isArrayKind ( ) const

inline

Old name of isOriginalArrayKind.

Definition at line 955 of file ScopInfo.h.

References isOriginalArrayKind().

Referenced by polly::ScopStmt::addAccess(), and polly::IslNodeBuilder::preloadInvariantEquivClass().

◆ isExitPHIKind()

bool polly::MemoryAccess::isExitPHIKind ( ) const

inline

Old name of isOriginalExitPHIKind().

Definition at line 1014 of file ScopInfo.h.

References isOriginalExitPHIKind().

Referenced by polly::ScopBuilder::buildAccessRelations().

◆ isLatestAnyPHIKind()

bool polly::MemoryAccess::isLatestAnyPHIKind ( ) const

inline

Does this access originate from one of the two PHI types? Can be changed to an array access using setNewAccessRelation().

Definition at line 1023 of file ScopInfo.h.

References isLatestExitPHIKind(), and isLatestPHIKind().

◆ isLatestArrayKind()

bool polly::MemoryAccess::isLatestArrayKind ( ) const

inline

Whether storage memory is either an custom .s2a/.phiops alloca (false) or an existing pointer into an array (true).

Definition at line 950 of file ScopInfo.h.

References polly::Array, and getLatestKind().

Referenced by polly::ZoneAlgorithm::addArrayReadAccess(), polly::ZoneAlgorithm::addArrayWriteAccess(), polly::BlockGenerator::getImplicitAddress(), polly::BlockGenerator::getOrCreateAlloca(), and polly::ZoneAlgorithm::isCompatibleAccess().

◆ isLatestExitPHIKind()

bool polly::MemoryAccess::isLatestExitPHIKind ( ) const

inline

Is this MemoryAccess modeling the accesses of a PHI node in the SCoP's exit block? Can be changed to an array access using setNewAccessRelation().

Definition at line 1009 of file ScopInfo.h.

References polly::ExitPHI, and getLatestKind().

Referenced by isLatestAnyPHIKind().

◆ isLatestPartialAccess()

bool MemoryAccess::isLatestPartialAccess ( ) const

Return whether the MemoryyAccess is a partial access.

That is, the access is not executed in some instances of the parent statement's domain.

Definition at line 1095 of file ScopInfo.cpp.

References isl::map::domain(), polly::ScopStmt::getDomain(), getLatestAccessRelation(), getStatement(), and isl::set::is_subset().

◆ isLatestPHIKind()

bool polly::MemoryAccess::isLatestPHIKind ( ) const

inline

Is this MemoryAccess modeling special PHI node accesses, also considering a potential change by setNewAccessRelation?

Definition at line 995 of file ScopInfo.h.

References getLatestKind(), and polly::PHI.

Referenced by isLatestAnyPHIKind().

◆ isLatestScalarKind()

bool polly::MemoryAccess::isLatestScalarKind ( ) const

inline

Whether this access is an array to a scalar memory object, also considering changes by setNewAccessRelation.

Definition at line 968 of file ScopInfo.h.

References polly::Array, and getLatestKind().

◆ isLatestValueKind()

bool polly::MemoryAccess::isLatestValueKind ( ) const

inline

Is this MemoryAccess currently modeling scalar dependences?

Definition at line 981 of file ScopInfo.h.

References getLatestKind(), and polly::Value.

◆ isMayWrite()

bool polly::MemoryAccess::isMayWrite ( ) const

inline

Is this a may-write memory access?

Definition at line 766 of file ScopInfo.h.

References AccType, and MAY_WRITE.

Referenced by polly::ZoneAlgorithm::addArrayWriteAccess(), polly::Scop::getMayWrites(), and isWrite().

◆ isMemoryIntrinsic()

bool polly::MemoryAccess::isMemoryIntrinsic ( ) const

inline

Is this a memory intrinsic access (memcpy, memset, memmove)?

Definition at line 772 of file ScopInfo.h.

References getAccessInstruction().

Referenced by buildMemIntrinsicAccessRelation(), and polly::ScopBuilder::getNonHoistableCtx().

◆ isMustWrite()

bool polly::MemoryAccess::isMustWrite ( ) const

inline

Is this a must-write memory access?

Definition at line 763 of file ScopInfo.h.

References AccType, and MUST_WRITE.

Referenced by polly::ZoneAlgorithm::addArrayWriteAccess(), polly::Scop::getMustWrites(), polly::ZoneAlgorithm::getWrittenValue(), and isWrite().

◆ isOriginalAnyPHIKind()

bool polly::MemoryAccess::isOriginalAnyPHIKind ( ) const

inline

Was this access detected as one of the two PHI types?

Definition at line 1017 of file ScopInfo.h.

References isOriginalExitPHIKind(), and isOriginalPHIKind().

Referenced by polly::Scop::addAccessData(), isAnyPHIKind(), polly::Scop::removeAccessData(), and polly::ScopStmt::removeAccessData().

◆ isOriginalArrayKind()

bool polly::MemoryAccess::isOriginalArrayKind ( ) const

inline

Whether this is an access of an explicit load or store in the IR.

Definition at line 944 of file ScopInfo.h.

References polly::Array, and getOriginalKind().

Referenced by polly::ZoneAlgorithm::getWrittenValue(), and isArrayKind().

◆ isOriginalExitPHIKind()

bool polly::MemoryAccess::isOriginalExitPHIKind ( ) const

inline

Was this MemoryAccess detected as the accesses of a PHI node in the SCoP's exit block?

Definition at line 1002 of file ScopInfo.h.

References polly::ExitPHI, and getOriginalKind().

Referenced by isExitPHIKind(), and isOriginalAnyPHIKind().

◆ isOriginalPHIKind()

bool polly::MemoryAccess::isOriginalPHIKind ( ) const

inline

Was this MemoryAccess detected as a special PHI node access?

Definition at line 989 of file ScopInfo.h.

References getOriginalKind(), and polly::PHI.

Referenced by polly::Scop::addAccessFunction(), polly::ZoneAlgorithm::isNormalizable(), isOriginalAnyPHIKind(), isPHIKind(), and polly::Scop::removeAccessData().

◆ isOriginalScalarKind()

bool polly::MemoryAccess::isOriginalScalarKind ( ) const

inline

Whether this access is an array to a scalar memory object, without considering changes by setNewAccessRelation.

Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or MemoryKind::ExitPHI.

Definition at line 962 of file ScopInfo.h.

References polly::Array, and getOriginalKind().

Referenced by isScalarKind().

◆ isOriginalValueKind()

bool polly::MemoryAccess::isOriginalValueKind ( ) const

inline

Was this MemoryAccess detected as a scalar dependences?

Definition at line 976 of file ScopInfo.h.

References getOriginalKind(), and polly::Value.

Referenced by polly::Scop::addAccessData(), polly::Scop::addAccessFunction(), isEscaping(), isValueKind(), polly::Scop::removeAccessData(), and polly::ScopStmt::removeAccessData().

◆ isPHIKind()

bool polly::MemoryAccess::isPHIKind ( ) const

inline

Old name of isOriginalPHIKind.

Definition at line 998 of file ScopInfo.h.

References isOriginalPHIKind().

Referenced by polly::ScopBuilder::buildAccessRelations().

◆ isRead()

bool polly::MemoryAccess::isRead ( ) const

inline

Is this a read memory access?

Definition at line 760 of file ScopInfo.h.

References AccType, and READ.

Referenced by polly::ScopStmt::addAccess(), polly::Scop::addAccessData(), polly::Scop::addAccessFunction(), polly::ZoneAlgorithm::addArrayReadAccess(), addIncoming(), polly::ScopBuilder::checkForReductions(), polly::Scop::getReads(), polly::ZoneAlgorithm::isNormalizable(), polly::IslNodeBuilder::preloadInvariantEquivClass(), polly::Scop::removeAccessData(), polly::ScopStmt::removeAccessData(), and setNewAccessRelation().

◆ isReductionLike()

bool polly::MemoryAccess::isReductionLike ( ) const

inline

Is this a reduction like access?

Definition at line 757 of file ScopInfo.h.

References RedType, and RT_NONE.

◆ isScalarKind()

bool polly::MemoryAccess::isScalarKind ( ) const

inline

Old name of isOriginalScalarKind.

Definition at line 973 of file ScopInfo.h.

References isOriginalScalarKind().

Referenced by polly::ScopBuilder::getNonHoistableCtx(), and print().

◆ isStrideOne()

bool MemoryAccess::isStrideOne ( isl::map Schedule ) const

Is consecutive memory accessed for a given statement instance set? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

Definition at line 1036 of file ScopInfo.cpp.

References isStrideX().

◆ isStrideX()

bool MemoryAccess::isStrideX	(	isl::map	Schedule,
		int	StrideWidth
	)		const

Is the stride of the access equal to a certain width? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

Definition at line 1017 of file ScopInfo.cpp.

References isl::set::fix_si(), isl::set::get_space(), getStride(), isl::set::is_subset(), isl::set, isl::set::tuple_dim(), isl::set::universe(), and unsignedFromIslSize().

Referenced by isStrideOne(), and isStrideZero().

◆ isStrideZero()

bool MemoryAccess::isStrideZero ( isl::map Schedule ) const

Is always the same memory accessed for a given statement instance set? Schedule is a map from the statement to a schedule where the innermost dimension is the dimension of the innermost loop containing the statement.

Definition at line 1032 of file ScopInfo.cpp.

References isStrideX().

◆ isValueKind()

bool polly::MemoryAccess::isValueKind ( ) const

inline

Old name of isOriginalValueKind().

Definition at line 986 of file ScopInfo.h.

References isOriginalValueKind().

Referenced by polly::ScopStmt::addAccess(), and polly::ScopBuilder::buildAccessRelations().

◆ isWrite()

bool polly::MemoryAccess::isWrite ( ) const

inline

Is this a write memory access?

Definition at line 769 of file ScopInfo.h.

References isMayWrite(), and isMustWrite().

Referenced by polly::ScopStmt::addAccess(), polly::Scop::addAccessData(), polly::Scop::addAccessFunction(), polly::ZoneAlgorithm::addArrayWriteAccess(), polly::ScopBuilder::getNonHoistableCtx(), polly::Scop::getWrites(), polly::Scop::removeAccessData(), polly::ScopStmt::removeAccessData(), and tryGetValueStored().

◆ markAsReductionLike()

void polly::MemoryAccess::markAsReductionLike ( ReductionType RT )

inline

Mark this a reduction like access.

Definition at line 1053 of file ScopInfo.h.

References RedType.

◆ operator=()

MemoryAccess & polly::MemoryAccess::operator= ( const MemoryAccess & )

delete

◆ print()

void MemoryAccess::print ( raw_ostream & OS ) const

Print the MemoryAccess.

Parameters

OS	The output stream the MemoryAccess is printed to.

Definition at line 933 of file ScopInfo.cpp.

References AccType, getNewAccessRelationStr(), getOriginalAccessRelationStr(), getReductionType(), hasNewAccessRelation(), isScalarKind(), MAY_WRITE, MUST_WRITE, and READ.

Referenced by dump().

◆ realignParams()

void MemoryAccess::realignParams ( )

Align the parameters in the access relation to the scop context.

Definition at line 901 of file ScopInfo.cpp.

References AccessRelation, isl::map::align_params(), isl::set::align_params(), Ctx, polly::Scop::getContext(), polly::ScopStmt::getParent(), isl::map::gist_params(), isl::set::gist_params(), InvalidDomain, and Statement.

Referenced by polly::ScopStmt::realignParams().

◆ setAccessRelation()

void MemoryAccess::setAccessRelation ( isl::map AccessRelation )

Update the original access relation.

We need to update the original access relation during scop construction, when unifying the memory accesses that access the same scop array info object. After the scop has been constructed, the original access relation should not be changed any more. Instead setNewAccessRelation should be called.

Definition at line 1040 of file ScopInfo.cpp.

References AccessRelation.

◆ setNewAccessRelation()

void MemoryAccess::setNewAccessRelation ( isl::map NewAccessRelation )

Set the updated access relation read from JSCOP file.

Definition at line 1044 of file ScopInfo.cpp.

References assert, isl::space::dim(), isl::map::domain(), isl::space::domain(), isl::map::get_space(), isl::space::get_tuple_id(), isl::id::get_user(), polly::Scop::getBestKnownDefinedBehaviorContext(), polly::ScopStmt::getDomain(), polly::ScopStmt::getDomainSpace(), polly::ScopStmt::getParent(), getStatement(), isl::map::gist_domain(), isl::map::gist_params(), isl::space::has_equal_tuples(), isl::space::has_tuple_id(), isl::set::intersect_params(), isl::boolean::is_false(), isl::map::is_null(), isl::set::is_subset(), isRead(), polly::Scop::lookupInvariantEquivClass(), NewAccessRelation, isl::set, and unsignedFromIslSize().

◆ subscripts()

iterator_range< SubscriptsTy::const_iterator > polly::MemoryAccess::subscripts ( ) const

inline

Return an iterator range containing the subscripts.

Definition at line 888 of file ScopInfo.h.

References Subscripts.

Referenced by polly::ScopBuilder::buildAccessRelations(), and polly::ScopBuilder::canAlwaysBeHoisted().

◆ tryGetValueStored()

Value * polly::MemoryAccess::tryGetValueStored ( )

inline

Return llvm::Value that is stored by this access, if available.

PHI nodes may not have a unique value available that is stored, as in case of region statements one out of possibly several llvm::Values might be stored. In this case nullptr is returned.

Definition at line 874 of file ScopInfo.h.

References AccessValue, assert, Incoming, isAnyPHIKind(), isWrite(), and polly::Value.

◆ updateDimensionality()

void MemoryAccess::updateDimensionality ( )

Update the dimensionality of the memory access.

During scop construction some memory accesses may not be constructed with their full dimensionality, but outer dimensions may have been omitted if they took the value 'zero'. By updating the dimensionality of the statement we add additional zero-valued dimensions to match the dimensionality of the ScopArrayInfo object that belongs to this memory access.

Definition at line 442 of file ScopInfo.cpp.

References AccessRelation, isl::map::add_constraint(), isl::constraint::alloc_inequality(), isl::map::apply_range(), assert, C, computeBoundsOnAccessRelation(), isl::space::ctx(), Ctx, isl::space::dim(), isl::map::equate(), isl::map::fix_si(), isl::map::floordiv_val(), isl::map::from_domain_and_range(), isl::map::get_space(), getElementType(), polly::ScopArrayInfo::getElemSizeInBytes(), polly::ScopStmt::getEntryBlock(), getScopArrayInfo(), getStatement(), isl::in, isAffine(), isl::out, isl::space::range(), isl::set, isl::set::universe(), unsignedFromIslSize(), and wrapConstantDimensions().

◆ wrapConstantDimensions()

void MemoryAccess::wrapConstantDimensions ( )

private

Carry index overflows of dimensions with constant size to the next higher dimension.

For dimensions that have constant size, modulo the index by the size and add up the carry (floored division) to the next higher dimension. This is how overflow is defined in row-major order. It happens e.g. when ScalarEvolution computes the offset to the base pointer and would algebraically sum up all lower dimensions' indices of constant size.

Example: float (*A)[4]; A[1][6] -> A[2][2]

Definition at line 390 of file ScopInfo.cpp.

References AccessRelation, isl::aff::add(), isl::map::apply_range(), isl::space::ctx(), Ctx, isl::map::detect_equalities(), isl::aff::div(), isl::aff::floor(), isl::map::from_multi_aff(), getScopArrayInfo(), isl::multi_aff::identity(), isl::space::map_from_domain_and_range(), isl::aff::mod(), isl::aff::pullback(), isl::set, isl::multi_aff::set_aff(), polly::valFromAPInt(), and isl::aff::var_on_domain().

Referenced by updateDimensionality().

Friends And Related Function Documentation

◆ Scop

friend class Scop

friend

Definition at line 432 of file ScopInfo.h.

◆ ScopBuilder

friend class ScopBuilder

friend

Definition at line 434 of file ScopInfo.h.

◆ ScopStmt

friend class ScopStmt

friend

Definition at line 433 of file ScopInfo.h.

Member Data Documentation

◆ AccessInstruction

Instruction* polly::MemoryAccess::AccessInstruction = nullptr

private

The access instruction of this memory access.

For memory accesses of kind MemoryKind::Array the access instruction is the Load or Store instruction performing the access.

For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the access instruction of a load access is the PHI instruction. The access instruction of a PHI-store is the incoming's block's terminator instruction.

For memory accesses of kind MemoryKind::Value the access instruction of a load access is nullptr because generally there can be multiple instructions in the statement using the same llvm::Value. The access instruction of a write access is the instruction that defines the llvm::Value.

Definition at line 569 of file ScopInfo.h.

Referenced by getAccessInstruction().

◆ AccessRelation

isl::map polly::MemoryAccess::AccessRelation

private

Relation from statement instances to the accessed array elements.

In the common case this relation is a function that maps a set of loop indices to the memory address from which a value is loaded/stored:

 for i
   for j

S: A[i + 3 j] = ...

=> { S[i,j] -> A[i + 3j] }

In case the exact access function is not known, the access relation may also be a one to all mapping { S[i,j] -> A[o] } describing that any element accessible through A might be accessed.

In case of an access to a larger element belonging to an array that also contains smaller elements, the access relation models the larger access with multiple smaller accesses of the size of the minimal array element type:

 short *A;

 for i

S: A[i] = *((double*)&A[4 * i]);

=> { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }

Definition at line 618 of file ScopInfo.h.

Referenced by buildAccessRelation(), buildMemIntrinsicAccessRelation(), computeBoundsOnAccessRelation(), foldAccessRelation(), getOriginalAccessRelation(), getOriginalAccessRelationSpace(), getOriginalAccessRelationStr(), getOriginalArrayId(), getStride(), realignParams(), setAccessRelation(), updateDimensionality(), and wrapConstantDimensions().

◆ AccessValue

AssertingVH<Value> polly::MemoryAccess::AccessValue

private

The value associated with this memory access.

For array memory accesses (MemoryKind::Array) it is the loaded result or the stored value. If the access instruction is a memory intrinsic it the access value is also the memory intrinsic.
For accesses of kind MemoryKind::Value it is the access instruction itself.
For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the PHI node itself (for both, READ and WRITE accesses).

Definition at line 584 of file ScopInfo.h.

Referenced by getAccessValue(), and tryGetValueStored().

◆ AccType

enum AccessType polly::MemoryAccess::AccType

private

Whether it a reading or writing access, and if writing, whether it is conditional (MAY_WRITE).

Definition at line 492 of file ScopInfo.h.

Referenced by getType(), isMayWrite(), isMustWrite(), isRead(), MemoryAccess(), and print().

◆ BaseAddr

AssertingVH<Value> polly::MemoryAccess::BaseAddr

private

The base address (e.g., A for A[i+j]).

The BaseAddr of a memory access of kind MemoryKind::Array is the base pointer of the memory access. The BaseAddr of a memory access of kind MemoryKind::PHI or MemoryKind::ExitPHI is the PHI node itself. The BaseAddr of a memory access of kind MemoryKind::Value is the instruction defining the value.

Definition at line 542 of file ScopInfo.h.

Referenced by getOriginalBaseAddr(), and MemoryAccess().

◆ ElementType

Type* polly::MemoryAccess::ElementType

private

Type a single array element wrt. this access.

Definition at line 545 of file ScopInfo.h.

Referenced by getElementType(), and MemoryAccess().

◆ Id

isl::id polly::MemoryAccess::Id

private

A unique identifier for this memory access.

The identifier is unique between all memory accesses belonging to the same scop statement.

Definition at line 484 of file ScopInfo.h.

Referenced by buildAccessRelation(), getId(), and MemoryAccess().

◆ Incoming

SmallVector<std::pair<BasicBlock *, Value *>, 4> polly::MemoryAccess::Incoming

private

Incoming block and value of a PHINode.

Definition at line 572 of file ScopInfo.h.

Referenced by addIncoming(), getIncoming(), and tryGetValueStored().

◆ InvalidDomain

isl::set polly::MemoryAccess::InvalidDomain

private

The domain under which this access is not modeled precisely.

The invalid domain for an access describes all parameter combinations under which the statement looks to be executed but is in fact not because some assumption/restriction makes the access invalid.

Definition at line 528 of file ScopInfo.h.

Referenced by buildAccessRelation(), getInvalidDomain(), getPwAff(), and realignParams().

◆ IsAffine

bool polly::MemoryAccess::IsAffine = true

private

Are all the subscripts affine expression?

Definition at line 587 of file ScopInfo.h.

Referenced by isAffine().

◆ Kind

MemoryKind polly::MemoryAccess::Kind

private

What is modeled by this MemoryAccess.

See also: MemoryKind

Definition at line 488 of file ScopInfo.h.

Referenced by getOriginalKind().

◆ NewAccessRelation

isl::map polly::MemoryAccess::NewAccessRelation

private

Updated access relation read from JSCOP file.

Definition at line 621 of file ScopInfo.h.

Referenced by foldAccessRelation(), getLatestArrayId(), getNewAccessRelation(), getNewAccessRelationStr(), hasNewAccessRelation(), MemoryAccess(), and setNewAccessRelation().

◆ RedType

ReductionType polly::MemoryAccess::RedType = RT_NONE

private

Reduction type for reduction like accesses, RT_NONE otherwise.

An access is reduction like if it is part of a load-store chain in which both access the same memory location (use the same LLVM-IR value as pointer reference). Furthermore, between the load and the store there is exactly one binary operator which is known to be associative and commutative.

TODO:

We can later lift the constraint that the same LLVM-IR value defines the memory location to handle scops such as the following:

for i for j sum[i+j] = sum[i] + 3;

Here not all iterations access the same memory location, but iterations for which j = 0 holds do. After lifting the equality check in ScopBuilder, subsequent transformations do not only need check if a statement is reduction like, but they also need to verify that the reduction property is only exploited for statement instances that load from and store to the same data location. Doing so at dependence analysis time could allow us to handle the above example.

Definition at line 518 of file ScopInfo.h.

Referenced by getReductionType(), isReductionLike(), and markAsReductionLike().

◆ Sizes

SmallVector<const SCEV *, 4> polly::MemoryAccess::Sizes

private

Size of each dimension of the accessed array.

Definition at line 548 of file ScopInfo.h.

Referenced by polly::ScopBuilder::buildAccessRelations(), buildMemIntrinsicAccessRelation(), foldAccessRelation(), and MemoryAccess().

◆ Statement

ScopStmt* polly::MemoryAccess::Statement

private

Parent ScopStmt of this access.

Definition at line 521 of file ScopInfo.h.

Referenced by assumeNoOutOfBound(), buildAccessRelation(), computeBoundsOnAccessRelation(), createBasicAccessMap(), foldAccessRelation(), getStatement(), and realignParams().

◆ Subscripts

SubscriptsTy polly::MemoryAccess::Subscripts

private

Subscript expression for each dimension.

Definition at line 590 of file ScopInfo.h.

Referenced by buildAccessRelation(), buildMemIntrinsicAccessRelation(), foldAccessRelation(), getNumSubscripts(), getSubscript(), and subscripts().

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

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ SubscriptsTy

Member Enumeration Documentation

◆ AccessType

◆ ReductionType

Constructor & Destructor Documentation

◆ MemoryAccess() [1/3]

◆ MemoryAccess() [2/3]

◆ MemoryAccess() [3/3]

◆ ~MemoryAccess()

Member Function Documentation

◆ addIncoming()

◆ applyScheduleToAccessRelation()

◆ assumeNoOutOfBound()

◆ buildAccessRelation()

◆ buildMemIntrinsicAccessRelation()

◆ computeBoundsOnAccessRelation()

◆ createBasicAccessMap()

◆ dump()

◆ foldAccessRelation()

◆ getAccessInstruction()

◆ getAccessRelation()

◆ getAccessRelationStr()

◆ getAccessValue()

◆ getAddressFunction()

◆ getArrayId()

◆ getElementType()

◆ getId()

◆ getIncoming()

◆ getInvalidContext()

◆ getInvalidDomain()

◆ getLatestAccessRelation()

◆ getLatestArrayId()

◆ getLatestKind()

◆ getLatestScopArrayInfo()

◆ getNewAccessRelation()

◆ getNewAccessRelationStr()

◆ getNumSubscripts()

◆ getOriginalAccessRelation()

◆ getOriginalAccessRelationSpace()

◆ getOriginalAccessRelationStr()

◆ getOriginalArrayId()

◆ getOriginalBaseAddr()

◆ getOriginalKind()

◆ getOriginalScopArrayInfo()

◆ getPwAff()

◆ getReductionOperatorStr() [1/2]

◆ getReductionOperatorStr() [2/2]

◆ getReductionType()

◆ getScopArrayInfo()

◆ getStatement()

◆ getStride()

◆ getSubscript()

◆ getType()

◆ hasNewAccessRelation()

◆ isAffine()

◆ isAnyPHIKind()

◆ isArrayKind()

◆ isExitPHIKind()

◆ isLatestAnyPHIKind()

◆ isLatestArrayKind()

◆ isLatestExitPHIKind()

◆ isLatestPartialAccess()

◆ isLatestPHIKind()

◆ isLatestScalarKind()

◆ isLatestValueKind()

◆ isMayWrite()

◆ isMemoryIntrinsic()

◆ isMustWrite()

◆ isOriginalAnyPHIKind()

◆ isOriginalArrayKind()

◆ isOriginalExitPHIKind()

◆ isOriginalPHIKind()