Build the Polly IR (Scop and ScopStmt) on a Region. More...

#include <ScopBuilder.h>

Public Member Functions
	ScopBuilder (Region *R, AssumptionCache &AC, AAResults &AA, const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, ScopDetection &SD, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE)

	ScopBuilder (const ScopBuilder &)=delete

ScopBuilder &	operator= (const ScopBuilder &)=delete

	~ScopBuilder ()=default

std::unique_ptr< Scop >	getScop ()
	Try to build the Polly IR of static control part on the current SESE-Region.

Private Types
using	AliasGroupTy = SmallVector< MemoryAccess *, 4 >
	A vector of memory accesses that belong to an alias group.

using	AliasGroupVectorTy = SmallVector< AliasGroupTy, 4 >
	A vector of alias groups.

using	LoopStackElementTy = LoopStackElement { Loop *L
	A loop stack element to keep track of per-loop information during schedule construction.

using	LoopStackTy = SmallVector< LoopStackElementTy, 4 >
	The loop stack used for schedule construction.

Private Member Functions
void	buildScop (Region &R, AssumptionCache &AC)

isl::set	adjustDomainDimensions (isl::set Dom, Loop OldL, Loop NewL)
	Adjust the dimensions of `Dom` that was constructed for `OldL` to be compatible to domains constructed for loop `NewL`.

bool	buildDomains (Region R, DenseMap< BasicBlock , isl::set > &InvalidDomainMap)
	Compute the domain for each basic block in `R`.

bool	buildDomainsWithBranchConstraints (Region R, DenseMap< BasicBlock , isl::set > &InvalidDomainMap)
	Compute the branching constraints for each basic block in `R`.

bool	buildConditionSets (BasicBlock BB, Instruction TI, Loop L, __isl_keep isl_set Domain, DenseMap< BasicBlock , isl::set > &InvalidDomainMap, SmallVectorImpl< __isl_give isl_set > &ConditionSets)
	Build the conditions sets for the terminator `TI` in the `Domain`.

bool	buildConditionSets (BasicBlock BB, Value Condition, Instruction TI, Loop L, __isl_keep isl_set Domain, DenseMap< BasicBlock , isl::set > &InvalidDomainMap, SmallVectorImpl< __isl_give isl_set * > &ConditionSets)
	Build the conditions sets for the branch condition `Condition` in the `Domain`.

bool	buildConditionSets (BasicBlock BB, SwitchInst SI, Loop L, __isl_keep isl_set Domain, DenseMap< BasicBlock , isl::set > &InvalidDomainMap, SmallVectorImpl< __isl_give isl_set > &ConditionSets)
	Build the conditions sets for the switch `SI` in the `Domain`.

__isl_give isl_set *	buildUnsignedConditionSets (BasicBlock BB, Value Condition, __isl_keep isl_set Domain, const SCEV SCEV_TestVal, const SCEV SCEV_UpperBound, DenseMap< BasicBlock , isl::set > &InvalidDomainMap, bool IsStrictUpperBound)
	Build condition sets for unsigned ICmpInst(s).

bool	propagateDomainConstraints (Region R, DenseMap< BasicBlock , isl::set > &InvalidDomainMap)
	Propagate the domain constraints through the region `R`.

void	propagateDomainConstraintsToRegionExit (BasicBlock BB, Loop BBLoop, SmallPtrSetImpl< BasicBlock * > &FinishedExitBlocks, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
	Propagate domains that are known due to graph properties.

bool	propagateInvalidStmtDomains (Region R, DenseMap< BasicBlock , isl::set > &InvalidDomainMap)
	Propagate invalid domains of statements through `R`.

isl::set	getPredecessorDomainConstraints (BasicBlock *BB, isl::set Domain)
	Compute the union of predecessor domains for `BB`.

bool	addLoopBoundsToHeaderDomain (Loop L, DenseMap< BasicBlock , isl::set > &InvalidDomainMap)
	Add loop carried constraints to the header block of the loop `L`.

__isl_give isl_pw_aff *	getPwAff (BasicBlock BB, DenseMap< BasicBlock , isl::set > &InvalidDomainMap, const SCEV *E, bool NonNegative=false)
	Compute the isl representation for the SCEV `E` in this BB.

void	buildInvariantEquivalenceClasses ()
	Create equivalence classes for required invariant accesses.

bool	buildAccessMultiDimFixed (MemAccInst Inst, ScopStmt *Stmt)
	Try to build a multi-dimensional fixed sized MemoryAccess from the Load/Store instruction.

bool	buildAccessMultiDimParam (MemAccInst Inst, ScopStmt *Stmt)
	Try to build a multi-dimensional parametric sized MemoryAccess.

bool	buildAccessMemIntrinsic (MemAccInst Inst, ScopStmt *Stmt)
	Try to build a MemoryAccess for a memory intrinsic.

bool	buildAccessCallInst (MemAccInst Inst, ScopStmt *Stmt)
	Try to build a MemoryAccess for a call instruction.

bool	buildAccessSingleDim (MemAccInst Inst, ScopStmt *Stmt)
	Build a single-dimensional parametric sized MemoryAccess from the Load/Store instruction.

void	finalizeAccesses ()
	Finalize all access relations.

void	updateAccessDimensionality ()
	Update access dimensionalities.

void	foldSizeConstantsToRight ()
	Fold size constants to the right.

void	foldAccessRelations ()
	Fold memory accesses to handle parametric offset.

void	assumeNoOutOfBounds ()
	Assume that all memory accesses are within bounds.

bool	buildAliasChecks ()
	Build the alias checks for this SCoP.

bool	buildAliasGroup (AliasGroupTy &AliasGroup, DenseSet< const ScopArrayInfo * > HasWriteAccess)
	Build a given alias group and its access data.

bool	buildAliasGroups ()
	Build all alias groups for this SCoP.

std::tuple< AliasGroupVectorTy, DenseSet< const ScopArrayInfo * > >	buildAliasGroupsForAccesses ()
	Build alias groups for all memory accesses in the Scop.

void	splitAliasGroupsByDomain (AliasGroupVectorTy &AliasGroups)
	Split alias groups by iteration domains.

void	buildMemoryAccess (MemAccInst Inst, ScopStmt *Stmt)
	Build an instance of MemoryAccess from the Load/Store instruction.

void	buildScalarDependences (ScopStmt UserStmt, Instruction Inst)
	Analyze and extract the cross-BB scalar dependences (or, dataflow dependencies) of an instruction.

void	buildEscapingDependences (Instruction *Inst)
	Build the escaping dependences for `Inst`.

void	buildPHIAccesses (ScopStmt PHIStmt, PHINode PHI, Region *NonAffineSubRegion, bool IsExitBlock=false)
	Create MemoryAccesses for the given PHI node in the given region.

void	buildAccessFunctions ()
	Build the access functions for the subregion `SR`.

bool	shouldModelInst (Instruction Inst, Loop L)
	Should an instruction be modeled in a ScopStmt.

void	buildSequentialBlockStmts (BasicBlock *BB, bool SplitOnStore=false)
	Create one or more ScopStmts for `BB`.

void	buildEqivClassBlockStmts (BasicBlock *BB)
	Create one or more ScopStmts for `BB` using equivalence classes.

void	buildStmts (Region &SR)
	Create ScopStmt for all BBs and non-affine subregions of `SR`.

void	buildAccessFunctions (ScopStmt Stmt, BasicBlock &BB, Region NonAffineSubRegion=nullptr)
	Build the access functions for the statement `Stmt` in or represented by `BB`.

MemoryAccess *	addMemoryAccess (ScopStmt Stmt, Instruction Inst, MemoryAccess::AccessType AccType, Value BaseAddress, Type ElemType, bool Affine, Value AccessValue, ArrayRef< const SCEV > Subscripts, ArrayRef< const SCEV * > Sizes, MemoryKind Kind)
	Create a new MemoryAccess object and add it to #AccFuncMap.

void	addArrayAccess (ScopStmt Stmt, MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value BaseAddress, Type ElemType, bool IsAffine, ArrayRef< const SCEV > Subscripts, ArrayRef< const SCEV * > Sizes, Value *AccessValue)
	Create a MemoryAccess that represents either a LoadInst or StoreInst.

void	ensureValueWrite (Instruction *Inst)
	Create a MemoryAccess for writing an llvm::Instruction.

void	ensureValueRead (Value V, ScopStmt UserStmt)
	Ensure an llvm::Value is available in the BB's statement, creating a MemoryAccess for reloading it if necessary.

void	ensurePHIWrite (PHINode PHI, ScopStmt IncomintStmt, BasicBlock IncomingBlock, Value IncomingValue, bool IsExitBlock)
	Create a write MemoryAccess for the incoming block of a phi node.

void	addUserContext ()
	Add user provided parameter constraints to context (command line).

void	addUserAssumptions (AssumptionCache &AC, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
	Add user provided parameter constraints to context (source code).

void	addRecordedAssumptions ()
	Add all recorded assumptions to the assumed context.

void	addPHIReadAccess (ScopStmt PHIStmt, PHINode PHI)
	Create a MemoryAccess for reading the value of a phi.

bool	calculateMinMaxAccess (AliasGroupTy AliasGroup, Scop::MinMaxVectorTy &MinMaxAccesses)
	Wrapper function to calculate minimal/maximal accesses to each array.

void	buildDomain (ScopStmt &Stmt)
	Build the domain of `Stmt`.

void	collectSurroundingLoops (ScopStmt &Stmt)
	Fill NestLoops with loops surrounding `Stmt`.

void	checkForReductions (ScopStmt &Stmt)
	Check for reductions in `Stmt`.

void	verifyInvariantLoads ()
	Verify that all required invariant loads have been hoisted.

void	hoistInvariantLoads ()
	Hoist invariant memory loads and check for required ones.

void	addInvariantLoads (ScopStmt &Stmt, InvariantAccessesTy &InvMAs)
	Add invariant loads listed in `InvMAs` with the domain of `Stmt`.

bool	canAlwaysBeHoisted (MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, bool MAInvalidCtxIsEmpty, bool NonHoistableCtxIsEmpty)
	Check if `MA` can always be hoisted without execution context.

bool	isRequiredInvariantLoad (LoadInst *LI) const
	Return true if and only if `LI` is a required invariant load.

bool	hasNonHoistableBasePtrInScop (MemoryAccess *MA, isl::union_map Writes)
	Check if the base ptr of `MA` is in the SCoP but not hoistable.

isl::set	getNonHoistableCtx (MemoryAccess *Access, isl::union_map Writes)
	Return the context under which the access cannot be hoisted.

void	collectCandidateReductionLoads (MemoryAccess StoreMA, SmallVectorImpl< MemoryAccess > &Loads)
	Collect loads which might form a reduction chain with `StoreMA`.

void	buildAccessRelations (ScopStmt &Stmt)
	Build the access relation of all memory accesses of `Stmt`.

void	canonicalizeDynamicBasePtrs ()
	Canonicalize arrays with base pointers from the same equivalence class.

void	buildSchedule ()
	Construct the schedule of this SCoP.

	LoopStackElement (Loop *L, isl::schedule S, unsigned NumBlocksProcessed)

void	buildSchedule (Region *R, LoopStackTy &LoopStack)
	Construct schedule information for a given Region and add the derived information to `LoopStack`.

void	buildSchedule (RegionNode *RN, LoopStackTy &LoopStack)
	Build Schedule for the region node `RN` and add the derived information to `LoopStack`.

Private Attributes
AAResults &	AA
	The AAResults to build AliasSetTracker.

const DataLayout &	DL
	Target data for element size computing.

DominatorTree &	DT
	DominatorTree to reason about guaranteed execution.

LoopInfo &	LI
	LoopInfo for information about loops.

ScopDetection &	SD
	Valid Regions for Scop.

ScalarEvolution &	SE
	The ScalarEvolution to help building Scop.

OptimizationRemarkEmitter &	ORE
	An optimization diagnostic interface to add optimization remarks.

SmallVector< std::pair< ScopStmt , Instruction >, 16 >	GlobalReads
	Set of instructions that might read any memory location.

SmallSetVector< Value *, 16 >	ArrayBasePointers
	Set of all accessed array base pointers.

std::unique_ptr< Scop >	scop

RecordedAssumptionsTy	RecordedAssumptions
	Collection to hold taken assumptions.

isl::schedule	Schedule

unsigned	NumBlocksProcessed

Detailed Description

Build the Polly IR (Scop and ScopStmt) on a Region.

Definition at line 33 of file ScopBuilder.h.

Member Typedef Documentation

◆ AliasGroupTy

using polly::ScopBuilder::AliasGroupTy = SmallVector<MemoryAccess *, 4>

private

A vector of memory accesses that belong to an alias group.

Definition at line 367 of file ScopBuilder.h.

◆ AliasGroupVectorTy

using polly::ScopBuilder::AliasGroupVectorTy = SmallVector<AliasGroupTy, 4>

private

A vector of alias groups.

Definition at line 370 of file ScopBuilder.h.

◆ LoopStackElementTy

using polly::ScopBuilder::LoopStackElementTy = LoopStackElement { Loop *L

private

A loop stack element to keep track of per-loop information during schedule construction.

Definition at line 715 of file ScopBuilder.h.

◆ LoopStackTy

using polly::ScopBuilder::LoopStackTy = SmallVector<LoopStackElementTy, 4>

private

The loop stack used for schedule construction.

The loop stack keeps track of schedule information for a set of nested loops as well as an (optional) 'nullptr' loop that models the outermost schedule dimension. The loops in a loop stack always have a parent-child relation where the loop at position n is the parent of the loop at position n + 1.

Definition at line 737 of file ScopBuilder.h.

Constructor & Destructor Documentation

◆ ScopBuilder() [1/2]

ScopBuilder::ScopBuilder	(	Region *	R,
		AssumptionCache &	AC,
		AAResults &	AA,
		const DataLayout &	DL,
		DominatorTree &	DT,
		LoopInfo &	LI,
		ScopDetection &	SD,
		ScalarEvolution &	SE,
		OptimizationRemarkEmitter &	ORE
	)

explicit

Definition at line 3653 of file ScopBuilder.cpp.

References buildScop(), DEBUG_TYPE, polly::getBBPairForRegion(), polly::getDebugLocations(), ORE, POLLY_DEBUG, RecordedAssumptions, and scop.

◆ ScopBuilder() [2/2]

polly::ScopBuilder::ScopBuilder ( const ScopBuilder & )

delete

◆ ~ScopBuilder()

polly::ScopBuilder::~ScopBuilder ( )

default

Member Function Documentation

◆ addArrayAccess()

void ScopBuilder::addArrayAccess	(	ScopStmt *	Stmt,
		MemAccInst	MemAccInst,
		MemoryAccess::AccessType	AccType,
		Value *	BaseAddress,
		Type *	ElemType,
		bool	IsAffine,
		ArrayRef< const SCEV * >	Subscripts,
		ArrayRef< const SCEV * >	Sizes,
		Value *	AccessValue
	)

private

Create a MemoryAccess that represents either a LoadInst or StoreInst.

Parameters

Stmt	The statement to add the MemoryAccess to.
MemAccInst	The LoadInst or StoreInst.
AccType	The kind of access.
BaseAddress	The accessed array's base address.
ElemType	The type of the accessed array elements.
IsAffine	Whether all subscripts are affine expressions.
Subscripts	Access subscripts per dimension.
Sizes	The array dimension's sizes.
AccessValue	Value read or written.

See also: MemoryKind

Definition at line 2152 of file ScopBuilder.cpp.

References addMemoryAccess(), polly::Array, and ArrayBasePointers.

Referenced by buildAccessCallInst(), buildAccessMemIntrinsic(), buildAccessMultiDimFixed(), buildAccessMultiDimParam(), buildAccessSingleDim(), and buildScop().

◆ addInvariantLoads()

void ScopBuilder::addInvariantLoads	(	ScopStmt &	Stmt,
		InvariantAccessesTy &	InvMAs
	)

private

Add invariant loads listed in InvMAs with the domain of Stmt.

Definition at line 2848 of file ScopBuilder.cpp.

References canAlwaysBeHoisted(), isl::set::coalesce(), polly::COMPLEXITY, isl::set::eliminate(), isl::set::find_dim_by_id(), polly::findValues(), isl::set::get_space(), polly::ScopStmt::getDomain(), polly::ScopStmt::getInvalidContext(), isl::set::gist_params(), isl::set::is_empty(), isl::set::is_equal(), isl::id::is_null(), isl::set::is_null(), polly::MaxDisjunctsInDomain, isl::set::n_basic_set(), isl::param, isl::set::params(), scop, SE, isl::set::subtract(), isl::set::unite(), isl::set::universe(), and unsignedFromIslSize().

Referenced by hoistInvariantLoads().

◆ addLoopBoundsToHeaderDomain()

bool ScopBuilder::addLoopBoundsToHeaderDomain	(	Loop *	L,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Add loop carried constraints to the header block of the loop L.

Parameters

L	The loop to process.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Returns: True if there was no problem and false otherwise.

Definition at line 730 of file ScopBuilder.cpp.

References isl::set::apply(), polly::AS_RESTRICTION, assert, buildConditionSets(), isl::set::complement(), createNextIterationMap(), isl::set::empty(), isl::map::equate(), isl::set::get(), isl::set::get_space(), isl::in, polly::INFINITELOOP, isl_set_free(), isl::map::lex_le(), LI, isl::set::lower_bound_si(), isl::manage(), isl::out, isl::set::params(), partitionSetParts(), isl::set::project_out(), polly::recordAssumption(), RecordedAssumptions, scop, isl::set, isl::set::subtract(), and isl::set::unite().

Referenced by propagateDomainConstraints().

◆ addMemoryAccess()

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

private

Create a new MemoryAccess object and add it to #AccFuncMap.

Parameters

Stmt	The statement where the access takes place.
Inst	The instruction doing the access. It is not necessarily inside `BB`.
AccType	The kind of access.
BaseAddress	The accessed array's base address.
ElemType	The type of the accessed array elements.
Affine	Whether all subscripts are affine expressions.
AccessValue	Value read or written.
Subscripts	Access subscripts per dimension.
Sizes	The array dimension's sizes.
Kind	The kind of memory accessed.

Returns: The created MemoryAccess, or nullptr if the access is not within the SCoP.

Definition at line 2114 of file ScopBuilder.cpp.

References polly::ScopStmt::addAccess(), DT, polly::ExitPHI, polly::ScopStmt::getRegion(), polly::ScopStmt::isBlockStmt(), polly::ScopStmt::isRegionStmt(), polly::MemoryAccess::MAY_WRITE, polly::MemoryAccess::MUST_WRITE, polly::PHI, and scop.

Referenced by addArrayAccess(), addPHIReadAccess(), ensurePHIWrite(), ensureValueRead(), and ensureValueWrite().

◆ addPHIReadAccess()

void ScopBuilder::addPHIReadAccess	(	ScopStmt *	PHIStmt,
		PHINode *	PHI
	)

private

Create a MemoryAccess for reading the value of a phi.

The modeling assumes that all incoming blocks write their incoming value to the same location. Thus, this access will read the incoming block's value as instructed by this PHI.

Parameters

PHIStmt	Statement `PHI` resides in.
PHI	PHINode under consideration; the READ access will be added here.

See also: ensurePHIWrite(); MemoryKind

Definition at line 2451 of file ScopBuilder.cpp.

References addMemoryAccess(), polly::PHI, and polly::MemoryAccess::READ.

Referenced by buildPHIAccesses().

◆ addRecordedAssumptions()

void ScopBuilder::addRecordedAssumptions ( )

private

Add all recorded assumptions to the assumed context.

Definition at line 1331 of file ScopBuilder.cpp.

References polly::AS_RESTRICTION, isl_set_intersect(), isl_set_params(), isl_set_subtract(), isl::manage(), RecordedAssumptions, and scop.

Referenced by buildScop().

◆ addUserAssumptions()

void ScopBuilder::addUserAssumptions	(	AssumptionCache &	AC,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Add user provided parameter constraints to context (source code).

Definition at line 1365 of file ScopBuilder.cpp.

References assert, buildConditionSets(), DEBUG_TYPE, DT, polly::extractConstantFactor(), polly::isAffineConstraint(), isl_dim_param, isl_id_free(), isl_id_get_user(), isl_set_complement(), isl_set_copy(), isl_set_free(), isl_set_get_dim_id(), isl_set_intersect(), isl_set_n_param(), isl_set_params(), isl_set_project_out(), LI, isl::manage(), ORE, scop, and SE.

Referenced by buildScop().

◆ addUserContext()

void ScopBuilder::addUserContext ( )

private

Add user provided parameter constraints to context (command line).

Definition at line 2693 of file ScopBuilder.cpp.

References isl::set::dim(), isl::space::dim(), isl::space::get_dim_id(), isl::set::get_dim_name(), isl::param, polly::rangeIslSize(), scop, isl::set::set_dim_id(), unsignedFromIslSize(), and UserContextStr().

Referenced by buildScop().

◆ adjustDomainDimensions()

isl::set ScopBuilder::adjustDomainDimensions	(	isl::set	Dom,
		Loop *	OldL,
		Loop *	NewL
	)

private

Adjust the dimensions of Dom that was constructed for OldL to be compatible to domains constructed for loop NewL.

This function assumes NewL and OldL are equal or there is a CFG edge from OldL to NewL.

Definition at line 294 of file ScopBuilder.cpp.

References isl::set::add_dims(), assert, isl::set::project_out(), scop, isl::set, isl::set::tuple_dim(), and unsignedFromIslSize().

Referenced by buildDomainsWithBranchConstraints(), getPredecessorDomainConstraints(), propagateDomainConstraintsToRegionExit(), and propagateInvalidStmtDomains().

◆ assumeNoOutOfBounds()

void ScopBuilder::assumeNoOutOfBounds ( )

private

Assume that all memory accesses are within bounds.

After we have built a model of all memory accesses, we need to assume that the model we built matches reality – aka. all modeled memory accesses always remain within bounds. We do this as last step, after all memory accesses have been modeled and canonicalized.

Definition at line 2329 of file ScopBuilder.cpp.

References polly::AS_ASSUMPTION, polly::INBOUNDS, PollyIgnoreInbounds(), polly::recordAssumption(), RecordedAssumptions, and scop.

Referenced by finalizeAccesses().

◆ buildAccessCallInst()

bool ScopBuilder::buildAccessCallInst	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Try to build a MemoryAccess for a call instruction.

Parameters

Inst	The call instruction that access the memory
Stmt	The parent statement of the instruction

Returns: True if the access could be built, False otherwise.

Definition at line 1637 of file ScopBuilder.cpp.

References AA, addArrayAccess(), GlobalReads, polly::isDebugCall(), polly::isIgnoredIntrinsic(), LI, polly::MemoryAccess::MAY_WRITE, polly::MemoryAccess::READ, and SE.

Referenced by buildMemoryAccess().

◆ buildAccessFunctions() [1/2]

void ScopBuilder::buildAccessFunctions ( )

private

Build the access functions for the subregion SR.

Definition at line 1754 of file ScopBuilder.cpp.

References buildAccessFunctions(), buildEscapingDependences(), and scop.

Referenced by buildAccessFunctions(), and buildScop().

◆ buildAccessFunctions() [2/2]

void ScopBuilder::buildAccessFunctions	(	ScopStmt *	Stmt,
		BasicBlock &	BB,
		Region *	NonAffineSubRegion = `nullptr`
	)

private

Build the access functions for the statement Stmt in or represented by BB.

Parameters

Stmt	Statement to add MemoryAccesses to.
BB	A basic block in `R`.
NonAffineSubRegion	The non affine sub-region `BB` is in.

Definition at line 2062 of file ScopBuilder.cpp.

References assert, buildMemoryAccess(), buildPHIAccesses(), buildScalarDependences(), polly::MemAccInst::dyn_cast(), polly::ScopStmt::getEntryBlock(), polly::ScopStmt::getInstructions(), polly::ScopDetection::isErrorBlock(), polly::isIgnoredIntrinsic(), polly::ScopStmt::isRegionStmt(), polly::PHI, polly::ScopStmt::represents(), scop, and SD.

◆ buildAccessMemIntrinsic()

bool ScopBuilder::buildAccessMemIntrinsic	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Try to build a MemoryAccess for a memory intrinsic.

Parameters

Inst	The instruction that access the memory
Stmt	The parent statement of the instruction

Returns: True if the access could be built, False otherwise.

Definition at line 1563 of file ScopBuilder.cpp.

References addArrayAccess(), assert, polly::ScopStmt::getSurroundingLoop(), polly::MemAccInst::getValueOperand(), polly::isAffineExpr(), LI, polly::MemoryAccess::MUST_WRITE, polly::MemoryAccess::READ, scop, and SE.

Referenced by buildMemoryAccess().

◆ buildAccessMultiDimFixed()

bool ScopBuilder::buildAccessMultiDimFixed	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Try to build a multi-dimensional fixed sized MemoryAccess from the Load/Store instruction.

Parameters

Inst	The Load/Store instruction that access the memory
Stmt	The parent statement of the instruction

Returns: True if the access could be built, False otherwise.

Definition at line 1442 of file ScopBuilder.cpp.

References addArrayAccess(), DL, polly::MemAccInst::getPointerOperand(), polly::ScopStmt::getSurroundingLoop(), polly::MemAccInst::getValueOperand(), polly::isAffineExpr(), polly::MemAccInst::isLoad(), polly::MemAccInst::isStore(), LI, polly::MemoryAccess::MUST_WRITE, polly::MemoryAccess::READ, scop, SE, and polly::Value.

Referenced by buildMemoryAccess().

◆ buildAccessMultiDimParam()

bool ScopBuilder::buildAccessMultiDimParam	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Try to build a multi-dimensional parametric sized MemoryAccess.

from the Load/Store instruction.

Parameters

Inst	The Load/Store instruction that access the memory
Stmt	The parent statement of the instruction

Returns: True if the access could be built, False otherwise.

Definition at line 1508 of file ScopBuilder.cpp.

References addArrayAccess(), assert, polly::DELINEARIZATION, DL, polly::MemAccInst::getPointerOperand(), polly::MemAccInst::getValueOperand(), polly::MemAccInst::isLoad(), polly::MemAccInst::isStore(), LI, polly::MemoryAccess::MUST_WRITE, polly::PollyDelinearize, polly::MemoryAccess::READ, scop, SE, and polly::Value.

Referenced by buildMemoryAccess().

◆ buildAccessRelations()

void ScopBuilder::buildAccessRelations ( ScopStmt & Stmt )

private

Build the access relation of all memory accesses of Stmt.

Definition at line 3084 of file ScopBuilder.cpp.

References polly::Array, polly::MemoryAccess::buildAccessRelation(), polly::ExitPHI, polly::MemoryAccess::getElementType(), polly::ScopStmt::getEntryBlock(), polly::MemoryAccess::getOriginalBaseAddr(), polly::MemoryAccess::isAffine(), polly::MemoryAccess::isExitPHIKind(), polly::MemoryAccess::isPHIKind(), polly::MemoryAccess::isValueKind(), polly::ScopStmt::MemAccs, polly::PHI, RecordedAssumptions, scop, polly::MemoryAccess::Sizes, polly::MemoryAccess::subscripts(), and polly::Value.

Referenced by buildScop().

◆ buildAccessSingleDim()

bool ScopBuilder::buildAccessSingleDim	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Build a single-dimensional parametric sized MemoryAccess from the Load/Store instruction.

Parameters

Inst	The Load/Store instruction that access the memory
Stmt	The parent statement of the instruction

Returns: True if the access could be built, False otherwise.

Definition at line 1684 of file ScopBuilder.cpp.

References addArrayAccess(), assert, polly::ScopStmt::contains(), polly::findLoops(), polly::MemAccInst::getPointerOperand(), polly::ScopStmt::getSurroundingLoop(), polly::MemAccInst::getValueOperand(), polly::isAffineExpr(), polly::MemAccInst::isLoad(), polly::MemAccInst::isStore(), LI, polly::MemoryAccess::MAY_WRITE, polly::MemoryAccess::MUST_WRITE, polly::MemoryAccess::READ, scop, SE, and polly::Value.

Referenced by buildMemoryAccess().

◆ buildAliasChecks()

bool ScopBuilder::buildAliasChecks ( )

private

Build the alias checks for this SCoP.

Definition at line 3228 of file ScopBuilder.cpp.

References polly::ALIASING, buildAliasGroups(), polly::Scop::incrementNumberOfAliasingAssumptions(), POLLY_DEBUG, polly::PollyUseRuntimeAliasChecks, and scop.

Referenced by buildScop().

◆ buildAliasGroup()

bool ScopBuilder::buildAliasGroup	(	AliasGroupTy &	AliasGroup,
		DenseSet< const ScopArrayInfo * >	HasWriteAccess
	)

private

Build a given alias group and its access data.

Parameters

AliasGroup	The alias group to build.
HasWriteAccess	A set of arrays through which memory is not only read, but also written.

Returns: True if no error occurred, false otherwise.

Definition at line 3327 of file ScopBuilder.cpp.

References polly::ALIASING, polly::Array, calculateMinMaxAccess(), DEBUG_TYPE, ORE, RunTimeChecksMaxArraysPerGroup(), and scop.

Referenced by buildAliasGroups().

◆ buildAliasGroups()

bool ScopBuilder::buildAliasGroups ( )

private

Build all alias groups for this SCoP.

Returns: True if no error occurred, false otherwise.

Definition at line 3295 of file ScopBuilder.cpp.

References buildAliasGroup(), buildAliasGroupsForAccesses(), polly::COMPLEXITY, isl_ctx_last_error(), isl_error_quota, OptComputeOut(), scop, and splitAliasGroupsByDomain().

Referenced by buildAliasChecks().

◆ buildAliasGroupsForAccesses()

std::tuple< ScopBuilder::AliasGroupVectorTy, DenseSet< const ScopArrayInfo * > > ScopBuilder::buildAliasGroupsForAccesses ( )

private

Build alias groups for all memory accesses in the Scop.

Using the alias analysis and an alias set tracker we build alias sets for all memory accesses inside the Scop. For each alias set we then map the aliasing pointers back to the memory accesses we know, thus obtain groups of memory accesses which might alias. We also collect the set of arrays through which memory is written.

Returns: A pair consistent of a vector of alias groups and a set of arrays through which memory is written.

Definition at line 3251 of file ScopBuilder.cpp.

References AA, polly::MemAccInst::getPointerOperand(), isl::set::is_empty(), scop, and polly::Value.

Referenced by buildAliasGroups().

◆ buildConditionSets() [1/3]

bool ScopBuilder::buildConditionSets	(	BasicBlock *	BB,
		Instruction *	TI,
		Loop *	L,
		__isl_keep isl_set *	Domain,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap,
		SmallVectorImpl< __isl_give isl_set * > &	ConditionSets
	)

private

Build the conditions sets for the terminator TI in the Domain.

This will fill ConditionSets with the conditions under which control will be moved from TI to its successors. Hence, ConditionSets will have as many elements as TI has successors.

Definition at line 566 of file ScopBuilder.cpp.

References assert, buildConditionSets(), Domain, polly::getConditionFromTerminator(), isl_set_copy(), and polly::Value.

Referenced by addLoopBoundsToHeaderDomain(), addUserAssumptions(), buildConditionSets(), and buildDomainsWithBranchConstraints().

◆ buildConditionSets() [2/3]

bool ScopBuilder::buildConditionSets	(	BasicBlock *	BB,
		SwitchInst *	SI,
		Loop *	L,
		__isl_keep isl_set *	Domain,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap,
		SmallVectorImpl< __isl_give isl_set * > &	ConditionSets
	)

private

Build the conditions sets for the switch SI in the Domain.

This will fill ConditionSets with the conditions under which control will be moved from SI to its successors. Hence, ConditionSets will have as many elements as SI has successors.

Definition at line 392 of file ScopBuilder.cpp.

References assert, buildConditionSet(), Domain, polly::getConditionFromTerminator(), getPwAff(), isl_pw_aff_free(), isl_set_coalesce(), isl_set_copy(), isl_set_intersect(), isl_set_subtract(), isl_set_union(), isl::manage(), isl::manage_copy(), isl::set::release(), SE, and polly::Value.

◆ buildConditionSets() [3/3]

bool ScopBuilder::buildConditionSets	(	BasicBlock *	BB,
		Value *	Condition,
		Instruction *	TI,
		Loop *	L,
		__isl_keep isl_set *	Domain,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap,
		SmallVectorImpl< __isl_give isl_set * > &	ConditionSets
	)

private

Build the conditions sets for the branch condition Condition in the Domain.

This will fill ConditionSets with the conditions under which control will be moved from TI to its successors. Hence, ConditionSets will have as many elements as TI has successors. If TI is nullptr the context under which Condition is true/false will be returned as the new elements of ConditionSets.

Definition at line 429 of file ScopBuilder.cpp.

References assert, buildConditionSet(), buildConditionSets(), buildUnsignedConditionSets(), polly::COMPLEXITY, Domain, getPwAff(), polly::getUniqueNonErrorValue(), isl_set_coalesce(), isl_set_copy(), isl_set_empty(), isl_set_free(), isl_set_get_space(), isl_set_intersect(), isl_set_n_basic_set(), isl_set_params(), isl_set_subtract(), isl_set_union(), isl_set_universe(), isl::manage(), polly::MaxDisjunctsInDomain, polly::PHI, isl::set::release(), scop, SD, SE, and polly::tryForwardThroughPHI().

◆ buildDomain()

void ScopBuilder::buildDomain ( ScopStmt & Stmt )

private

Build the domain of Stmt.

Definition at line 2457 of file ScopBuilder.cpp.

References isl::id::alloc(), polly::ScopStmt::Domain, polly::ScopStmt::getBaseName(), scop, and isl::set::set_tuple_id().

Referenced by buildScop().

◆ buildDomains()

bool ScopBuilder::buildDomains	(	Region *	R,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Compute the domain for each basic block in R.

Parameters

R	The region we currently traverse.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Returns: True if there was no problem and false otherwise.

Definition at line 831 of file ScopBuilder.cpp.

References buildDomainsWithBranchConstraints(), containsErrorBlock(), Domain, isl_set_empty(), isl_set_get_space(), isl_set_universe(), isl_space_set_alloc(), LI, isl::manage(), propagateDomainConstraints(), propagateInvalidStmtDomains(), scop, and SD.

Referenced by buildScop().

◆ buildDomainsWithBranchConstraints()

bool ScopBuilder::buildDomainsWithBranchConstraints	(	Region *	R,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Compute the branching constraints for each basic block in R.

Parameters

R	The region we currently build branching conditions for.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Returns: True if there was no problem and false otherwise.

Definition at line 871 of file ScopBuilder.cpp.

References adjustDomainDimensions(), assert, buildConditionSets(), buildDomainsWithBranchConstraints(), isl::set::coalesce(), polly::COMPLEXITY, containsErrorBlock(), isl::set::detect_equalities(), Domain, DT, isl::set::empty(), isl::set::get_space(), polly::getFirstNonBoxedLoopFor(), getRegionNodeBasicBlock(), polly::getRegionNodeLoop(), getRegionNodeSuccessor(), isl::set::is_null(), isl_set_free(), LI, isl::manage(), polly::MaxDisjunctsInDomain, isl::set::n_basic_set(), propagateDomainConstraintsToRegionExit(), scop, SD, isl::set::unite(), and unsignedFromIslSize().

Referenced by buildDomains(), and buildDomainsWithBranchConstraints().

◆ buildEqivClassBlockStmts()

void ScopBuilder::buildEqivClassBlockStmts ( BasicBlock * BB )

private

Create one or more ScopStmts for BB using equivalence classes.

Instructions of a basic block that belong to the same equivalence class are added to the same statement.

Definition at line 1945 of file ScopBuilder.cpp.

References isOrderedInstruction(), joinOperandTree(), joinOrderedInstructions(), joinOrderedPHIs(), LI, makeStmtName(), scop, and shouldModelInst().

Referenced by buildStmts().

◆ buildEscapingDependences()

void ScopBuilder::buildEscapingDependences ( Instruction * Inst )

private

Build the escaping dependences for Inst.

Search for uses of the llvm::Value defined by Inst that are not within the SCoP. If there is such use, add a SCALAR WRITE such that it is available after the SCoP as escaping value.

Parameters

Inst	The instruction to be analyzed.

Definition at line 1323 of file ScopBuilder.cpp.

References ensureValueWrite(), and scop.

Referenced by buildAccessFunctions().

◆ buildInvariantEquivalenceClasses()

void ScopBuilder::buildInvariantEquivalenceClasses ( )

private

Create equivalence classes for required invariant accesses.

These classes will consolidate multiple required invariant loads from the same address in order to keep the number of dimensions in the SCoP description small. For each such class equivalence class only one representing element, hence one required invariant load, will be chosen and modeled as parameter. The method Scop::getRepresentingInvariantLoadSCEV() will replace each element from an equivalence class with the representing element that is modeled. As a consequence Scop::getIdForParam() will only return an id for the representing element of each equivalence class, thus for each required invariant location.

Definition at line 811 of file ScopBuilder.cpp.

References scop, and SE.

Referenced by buildScop().

◆ buildMemoryAccess()

void ScopBuilder::buildMemoryAccess	(	MemAccInst	Inst,
		ScopStmt *	Stmt
	)

private

Build an instance of MemoryAccess from the Load/Store instruction.

Parameters

Inst	The Load/Store instruction that access the memory
Stmt	The parent statement of the instruction

Definition at line 1733 of file ScopBuilder.cpp.

References buildAccessCallInst(), buildAccessMemIntrinsic(), buildAccessMultiDimFixed(), buildAccessMultiDimParam(), and buildAccessSingleDim().

Referenced by buildAccessFunctions(), and buildScop().

◆ buildPHIAccesses()

void ScopBuilder::buildPHIAccesses	(	ScopStmt *	PHIStmt,
		PHINode *	PHI,
		Region *	NonAffineSubRegion,
		bool	IsExitBlock = `false`
	)

private

Create MemoryAccesses for the given PHI node in the given region.

Parameters

PHIStmt	The statement `PHI` resides in.
PHI	The PHI node to be handled
NonAffineSubRegion	The non affine sub-region `PHI` is in.
IsExitBlock	Flag to indicate that `PHI` is in the exit BB.

Definition at line 1081 of file ScopBuilder.cpp.

References addPHIReadAccess(), polly::canSynthesize(), ensurePHIWrite(), ensureValueRead(), LI, polly::PHI, scop, SE, and polly::Value.

Referenced by buildAccessFunctions(), and buildScop().

◆ buildScalarDependences()

void ScopBuilder::buildScalarDependences	(	ScopStmt *	UserStmt,
		Instruction *	Inst
	)

private

Analyze and extract the cross-BB scalar dependences (or, dataflow dependencies) of an instruction.

Parameters

UserStmt	The statement `Inst` resides in.
Inst	The instruction to be analyzed.

Definition at line 1123 of file ScopBuilder.cpp.

References assert, and ensureValueRead().

Referenced by buildAccessFunctions().

◆ buildSchedule() [1/3]

void ScopBuilder::buildSchedule ( )

private

Construct the schedule of this SCoP.

Definition at line 1178 of file ScopBuilder.cpp.

References assert, buildSchedule(), polly::getLoopSurroundingScop(), LI, Schedule, and scop.

Referenced by buildSchedule(), and buildScop().

◆ buildSchedule() [2/3]

void ScopBuilder::buildSchedule	(	Region *	R,
		LoopStackTy &	LoopStack
	)

private

Construct schedule information for a given Region and add the derived information to LoopStack.

To generate a schedule for the elements in a Region we traverse the Region in reverse-post-order and add the contained RegionNodes in traversal order to the schedule of the loop that is currently at the top of the LoopStack.

Given a Region we derive schedule information for all RegionNodes contained in this region ensuring that the assigned execution times correctly model the existing control flow relations.

Parameters

R	The region which to process.
LoopStack	A stack of loops that are currently under construction.

For loop-free codes, this results in a correct sequential ordering.

Example: bb1(0) / . bb2(1) bb3(2) \ / . bb4(3) bb5(4) \ / bb6(5)

Including loops requires additional processing. Whenever a loop header is encountered, the corresponding loop is added to the LoopStack. Starting from an empty schedule, we first process all RegionNodes that are within this loop and complete the sequential schedule at this loop-level before processing about any other nodes. To implement this loop-nodes-first-processing, the reverse post-order traversal is insufficient. Hence, we additionally check if the traversal yields sub-regions or blocks that are outside the last loop on the LoopStack. These region-nodes are then queue and only traverse after the all nodes within the current loop have been processed.

Definition at line 1210 of file ScopBuilder.cpp.

References buildSchedule(), polly::getLoopSurroundingScop(), polly::getRegionNodeLoop(), LI, and scop.

◆ buildSchedule() [3/3]

void ScopBuilder::buildSchedule	(	RegionNode *	RN,
		LoopStackTy &	LoopStack
	)

private

Build Schedule for the region node RN and add the derived information to LoopStack.

In case RN is a BasicBlock or a non-affine Region, we construct the schedule for this RN and also finalize loop schedules in case the current RN completes the loop.

In case RN is a not-non-affine Region, we delegate the construction to buildSchedule(Region *R, ...).

Parameters

RN	The RegionNode region traversed.
LoopStack	A stack of loops that are currently under construction.

If any of the loops has a disable_nonforced heuristic, mark the entire SCoP as such. The ISL rescheduler can only reschedule the SCoP in its entirety. TODO: ScopDetection could avoid including such loops or warp them as boxed loop. It still needs to pass-through loop with user-defined metadata.

Definition at line 1254 of file ScopBuilder.cpp.

References assert, buildSchedule(), isl::schedule_node::child(), combineInSequence(), polly::createIslLoopAttr(), Domain, isl::schedule::from_domain(), isl::schedule::get_domain(), isl::schedule::get_root(), isl::schedule_node::get_schedule(), polly::getNumBlocksInLoop(), polly::getNumBlocksInRegionNode(), polly::hasDisableAllTransformsHint(), isl::schedule_node::insert_mark(), isl::schedule::insert_partial_schedule(), isl::id::is_null(), isl::schedule::is_null(), mapToDimension(), NumBlocksProcessed, Schedule, and scop.

◆ buildScop()

void ScopBuilder::buildScop	(	Region &	R,
		AssumptionCache &	AC
	)

private

A map from basic blocks to their invalid domains.

Definition at line 3500 of file ScopBuilder.cpp.

References addArrayAccess(), addRecordedAssumptions(), addUserAssumptions(), addUserContext(), ArrayBasePointers, assert, buildAccessFunctions(), buildAccessRelations(), buildAliasChecks(), buildDomain(), buildDomains(), buildInvariantEquivalenceClasses(), buildMemoryAccess(), buildPHIAccesses(), buildSchedule(), buildStmts(), canonicalizeDynamicBasePtrs(), checkForReductions(), collectSurroundingLoops(), DetectReductions(), DT, finalizeAccesses(), polly::ScopDetection::getDetectionContext(), polly::ScopStmt::getEntryBlock(), polly::ScopDetection::getNextID(), polly::ScopStmt::getRegion(), getRegionNodeBasicBlock(), GlobalReads, hoistInvariantLoads(), polly::ScopStmt::isBlockStmt(), polly::ScopDetection::isErrorBlock(), LI, ORE, polly::PHI, POLLY_DEBUG, polly::PROFITABLE, polly::MemoryAccess::READ, scop, SD, SE, polly::ScopStmt::setInvalidDomain(), UnprofitableScalarAccs(), verifyInvariantLoads(), and verifyUses().

Referenced by ScopBuilder().

◆ buildSequentialBlockStmts()

void ScopBuilder::buildSequentialBlockStmts	(	BasicBlock *	BB,
		bool	SplitOnStore = `false`
	)

private

Create one or more ScopStmts for BB.

Consecutive instructions are associated to the same statement until a separator is found.

Definition at line 1814 of file ScopBuilder.cpp.

References LI, makeStmtName(), scop, and shouldModelInst().

Referenced by buildStmts().

◆ buildStmts()

void ScopBuilder::buildStmts ( Region & SR )

private

Create ScopStmt for all BBs and non-affine subregions of SR.

Parameters

SR	A subregion of `R`.

Some of the statements might be optimized away later when they do not access any memory and thus have no effect.

Definition at line 2029 of file ScopBuilder.cpp.

References buildEqivClassBlockStmts(), buildSequentialBlockStmts(), buildStmts(), polly::getFirstNonBoxedLoopFor(), LI, makeStmtName(), scop, shouldModelInst(), and StmtGranularity().

Referenced by buildScop(), and buildStmts().

◆ buildUnsignedConditionSets()

__isl_give isl_set * ScopBuilder::buildUnsignedConditionSets	(	BasicBlock *	BB,
		Value *	Condition,
		__isl_keep isl_set *	Domain,
		const SCEV *	SCEV_TestVal,
		const SCEV *	SCEV_UpperBound,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap,
		bool	IsStrictUpperBound
	)

private

Build condition sets for unsigned ICmpInst(s).

Special handling is required for unsigned operands to ensure that if MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst it should wrap around.

Parameters

IsStrictUpperBound holds information on the predicate relation between TestVal and UpperBound, i.e, TestVal < UpperBound OR TestVal <= UpperBound

Definition at line 362 of file ScopBuilder.cpp.

References getPwAff(), isl_local_space_from_space(), isl_pw_aff_copy(), isl_pw_aff_get_domain_space(), isl_pw_aff_le_set(), isl_pw_aff_lt_set(), isl_pw_aff_zero_on_domain(), and isl_set_intersect().

Referenced by buildConditionSets().

◆ calculateMinMaxAccess()

bool ScopBuilder::calculateMinMaxAccess	(	AliasGroupTy	AliasGroup,
		Scop::MinMaxVectorTy &	MinMaxAccesses
	)

private

Wrapper function to calculate minimal/maximal accesses to each array.

Definition at line 3198 of file ScopBuilder.cpp.

References buildMinMaxAccess(), isl::union_map::empty(), isl::union_set::get_set_list(), isl::union_map::intersect_domain(), isl::union_map::range(), scop, and isl::union_map::unite().

Referenced by buildAliasGroup().

◆ canAlwaysBeHoisted()

bool ScopBuilder::canAlwaysBeHoisted	(	MemoryAccess *	MA,
		bool	StmtInvalidCtxIsEmpty,
		bool	MAInvalidCtxIsEmpty,
		bool	NonHoistableCtxIsEmpty
	)

private

Check if MA can always be hoisted without execution context.

Definition at line 2812 of file ScopBuilder.cpp.

References DL, polly::MemoryAccess::getAccessInstruction(), isAParameter(), PollyAllowDereferenceOfAllFunctionParams(), scop, and polly::MemoryAccess::subscripts().

Referenced by addInvariantLoads().

◆ canonicalizeDynamicBasePtrs()

void ScopBuilder::canonicalizeDynamicBasePtrs ( )

private

Canonicalize arrays with base pointers from the same equivalence class.

Some context: in our normal model we assume that each base pointer is related to a single specific memory region, where memory regions associated with different base pointers are disjoint. Consequently we do not need to compute additional data dependences that model possible overlaps of these memory regions. To verify our assumption we compute alias checks that verify that modeled arrays indeed do not overlap. In case an overlap is detected the runtime check fails and we fall back to the original code.

In case of arrays where the base pointers are know to be identical, because they are dynamically loaded by accesses that are in the same invariant load equivalence class, such run-time alias check would always be false.

This function makes sure that we do not generate consistently failing run-time checks for code that contains distinct arrays with known equivalent base pointers. It identifies for each invariant load equivalence class a single canonical array and canonicalizes all memory accesses that reference arrays that have base pointers that are known to be equal to the base pointer of such a canonical array to this canonical array.

We currently do not canonicalize arrays for which certain memory accesses have been hoisted as loop invariant.

Definition at line 3054 of file ScopBuilder.cpp.

References polly::Array, findCanonicalArray(), polly::InvariantEquivClassTy::InvariantAccesses, polly::ScopArrayInfo::isCompatibleWith(), isUsedForIndirectHoistedLoad(), replaceBasePtrArrays(), and scop.

Referenced by buildScop().

◆ checkForReductions()

void ScopBuilder::checkForReductions ( ScopStmt & Stmt )

private

Check for reductions in Stmt.

Iterate over all store memory accesses and check for valid binary reduction like chains. For all candidates we check if they have the same base address and there are no other accesses which overlap with them. The base address check rules out impossible reductions candidates early. The overlap check, together with the "only one user" check in collectCandidateReductionLoads, guarantees that none of the intermediate results will escape during execution of the loop nest. We basically check here that no other memory access can access the same memory as the potential reduction.

Definition at line 2581 of file ScopBuilder.cpp.

References checkCandidatePairAccesses(), collectCandidateReductionLoads(), polly::ScopStmt::getDomain(), getReductionType(), polly::MemoryAccess::markAsReductionLike(), and polly::ScopStmt::MemAccs.

Referenced by buildScop().

◆ collectCandidateReductionLoads()

void ScopBuilder::collectCandidateReductionLoads	(	MemoryAccess *	StoreMA,
		SmallVectorImpl< MemoryAccess * > &	Loads
	)

private

Collect loads which might form a reduction chain with StoreMA.

Check if the stored value for StoreMA is a binary operator with one or two loads as operands. If the binary operand is commutative & associative, used only once (by StoreMA) and its load operands are also used only once, we have found a possible reduction chain. It starts at an operand load and includes the binary operator and StoreMA.

Note: We allow only one use to ensure the load and binary operator cannot escape this block or into any other store except StoreMA.

Definition at line 2968 of file ScopBuilder.cpp.

References DisableMultiplicativeReductions(), polly::MemoryAccess::getAccessInstruction(), polly::ScopStmt::getArrayAccessFor(), and polly::MemoryAccess::getStatement().

Referenced by checkForReductions().

◆ collectSurroundingLoops()

void ScopBuilder::collectSurroundingLoops ( ScopStmt & Stmt )

private

Fill NestLoops with loops surrounding Stmt.

Definition at line 2464 of file ScopBuilder.cpp.

References Domain, polly::ScopStmt::getDomain(), polly::ScopStmt::getEntryBlock(), polly::ScopStmt::getParent(), polly::ScopStmt::getRegion(), polly::Scop::getRegion(), polly::ScopStmt::isRegionStmt(), LI, and polly::ScopStmt::NestLoops.

Referenced by buildScop().

◆ ensurePHIWrite()

void ScopBuilder::ensurePHIWrite	(	PHINode *	PHI,
		ScopStmt *	IncomintStmt,
		BasicBlock *	IncomingBlock,
		Value *	IncomingValue,
		bool	IsExitBlock
	)

private

Create a write MemoryAccess for the incoming block of a phi node.

Each of the incoming blocks write their incoming value to be picked in the phi's block.

Parameters

PHI	PHINode under consideration.
IncomingStmt	The statement to add the MemoryAccess to.
IncomingBlock	Some predecessor block.
IncomingValue	`PHI's` value when coming from `IncomingBlock`.
IsExitBlock	When true, uses the .s2a alloca instead of the .phiops one. Required for values escaping through a PHINode in the SCoP region's exit block.

See also: addPHIReadAccess(); MemoryKind

Definition at line 2414 of file ScopBuilder.cpp.

References polly::MemoryAccess::addIncoming(), addMemoryAccess(), assert, ensureValueRead(), polly::ExitPHI, polly::ScopStmt::lookupPHIWriteOf(), polly::MemoryAccess::MUST_WRITE, polly::PHI, and scop.

Referenced by buildPHIAccesses().

◆ ensureValueRead()

void ScopBuilder::ensureValueRead	(	Value *	V,
		ScopStmt *	UserStmt
	)

private

Ensure an llvm::Value is available in the BB's statement, creating a MemoryAccess for reloading it if necessary.

Parameters

V	The value expected to be loaded.
UserStmt	Where to reload the value.

See also: ensureValueStore(); MemoryKind

Definition at line 2369 of file ScopBuilder.cpp.

References addMemoryAccess(), polly::VirtualUse::Block, polly::VirtualUse::Constant, polly::VirtualUse::create(), ensureValueWrite(), polly::ScopStmt::getSurroundingLoop(), polly::VirtualUse::Hoisted, polly::VirtualUse::Inter, polly::VirtualUse::Intra, polly::ScopStmt::lookupValueReadOf(), polly::ModelReadOnlyScalars, polly::MemoryAccess::READ, polly::VirtualUse::ReadOnly, scop, polly::VirtualUse::Synthesizable, and polly::Value.

Referenced by buildPHIAccesses(), buildScalarDependences(), and ensurePHIWrite().

◆ ensureValueWrite()

void ScopBuilder::ensureValueWrite ( Instruction * Inst )

private

Create a MemoryAccess for writing an llvm::Instruction.

The access will be created at the position of Inst.

Parameters

Inst	The instruction to be written.

See also: ensureValueRead(); MemoryKind

Definition at line 2343 of file ScopBuilder.cpp.

References addMemoryAccess(), polly::ScopStmt::lookupValueWriteOf(), polly::MemoryAccess::MUST_WRITE, scop, and polly::Value.

Referenced by buildEscapingDependences(), and ensureValueRead().

◆ finalizeAccesses()

void ScopBuilder::finalizeAccesses ( )

private

Finalize all access relations.

When building up access relations, temporary access relations that correctly represent each individual access are constructed. However, these access relations can be inconsistent or non-optimal when looking at the set of accesses as a whole. This function finalizes the memory accesses and constructs a globally consistent state.

Definition at line 2291 of file ScopBuilder.cpp.

References assumeNoOutOfBounds(), foldAccessRelations(), foldSizeConstantsToRight(), and updateAccessDimensionality().

Referenced by buildScop().

◆ foldAccessRelations()

void ScopBuilder::foldAccessRelations ( )

private

Fold memory accesses to handle parametric offset.

As a post-processing step, we 'fold' memory accesses to parametric offsets in the access functions.

See also: MemoryAccess::foldAccess for details.

Definition at line 2323 of file ScopBuilder.cpp.

References scop.

Referenced by finalizeAccesses().

◆ foldSizeConstantsToRight()

void ScopBuilder::foldSizeConstantsToRight ( )

private

Fold size constants to the right.

In case all memory accesses in a given dimension are multiplied with a common constant, we can remove this constant from the individual access functions and move it to the size of the memory access. We do this as this increases the size of the innermost dimension, consequently widens the valid range the array subscript in this dimension can evaluate to, and as a result increases the likelihood that our delinearization is correct.

Example:

A[][n] S[i,j] -> A[2i][2j+1] S[i,j] -> A[2i][2j]

=>

A[][2n] S[i,j] -> A[i][2j+1] S[i,j] -> A[i][2j]

Constants in outer dimensions can arise when the elements of a parametric multi-dimensional array are not elementary data types, but e.g., structures.

Definition at line 2193 of file ScopBuilder.cpp.

References isl::map::add_constraint(), isl::set::affine_hull(), isl::space::align_params(), isl::constraint::alloc_equality(), polly::APIntFromVal(), polly::Array, C, isl::union_set::contains(), isl::basic_set::dim(), isl::div, isl::map::domain(), isl::map::equate(), isl::union_set::extract_set(), isl::basic_set::fix_si(), isl::aff::get_denominator_val(), isl::basic_set::get_div(), isl::map::get_space(), isl::union_set::get_space(), isl::in, isl::basic_set::is_equal(), isl::val::is_int(), isl::set::is_subset(), isl::set::lower_bound_si(), isl::out, isl::set::project_out(), scop, SE, isl::set, isl::set::tuple_dim(), isl::map::universe(), and unsignedFromIslSize().

Referenced by finalizeAccesses().

◆ getNonHoistableCtx()

isl::set ScopBuilder::getNonHoistableCtx	(	MemoryAccess *	Access,
		isl::union_map	Writes
	)

private

Return the context under which the access cannot be hoisted.

Parameters

Access	The access to check.
Writes	The set of all memory writes in the scop.

Returns: Return the context under which the access cannot be hoisted or a nullptr if it cannot be hoisted at all.

Definition at line 2734 of file ScopBuilder.cpp.

References polly::AS_RESTRICTION, assert, DL, isl::map::get_space(), polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getAccessRelation(), polly::ScopStmt::getEntryBlock(), polly::MemoryAccess::getStatement(), hasNonHoistableBasePtrInScop(), isl::in, isl::map::intersect_domain(), isl::union_map::intersect_range(), polly::INVARIANTLOAD, isl::map::involves_dims(), isl::map::is_empty(), isl::set::is_empty(), isAccessRangeTooComplex(), polly::MemoryAccess::isAffine(), polly::MemoryAccess::isMemoryIntrinsic(), isRequiredInvariantLoad(), polly::MemoryAccess::isScalarKind(), polly::MemoryAccess::isWrite(), LI, polly::MaxDisjunctsInDomain, isl::set::n_basic_set(), isl::union_map::params(), isl::map::range(), isl::space::range(), isl::set::remove_divs(), scop, isl::set::universe(), and unsignedFromIslSize().

Referenced by hasNonHoistableBasePtrInScop(), and hoistInvariantLoads().

◆ getPredecessorDomainConstraints()

isl::set ScopBuilder::getPredecessorDomainConstraints	(	BasicBlock *	BB,
		isl::set	Domain
	)

private

Compute the union of predecessor domains for BB.

To compute the union of all domains of predecessors of BB this function applies similar reasoning on the CFG structure as described for

See also: propagateDomainConstraintsToRegionExit

Parameters

BB	The block for which the predecessor domains are collected.
Domain	The domain under which BB is executed.

Returns: The domain under which BB is executed.

Definition at line 675 of file ScopBuilder.cpp.

References adjustDomainDimensions(), Domain, DT, isl::set::empty(), polly::getFirstNonBoxedLoopFor(), LI, scop, isl::set::unite(), and isl::set::universe().

Referenced by propagateDomainConstraints().

◆ getPwAff()

__isl_give isl_pw_aff * ScopBuilder::getPwAff	(	BasicBlock *	BB,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap,
		const SCEV *	E,
		bool	NonNegative = `false`
	)

private

Compute the isl representation for the SCEV E in this BB.

Parameters

BB	The BB for which isl representation is to be computed.
InvalidDomainMap	A map of BB to their invalid domains.
E	The SCEV that should be translated.
NonNegative	Flag to indicate the `E` has to be non-negative.

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

Definition at line 346 of file ScopBuilder.cpp.

References RecordedAssumptions, and scop.

Referenced by buildConditionSets(), and buildUnsignedConditionSets().

◆ getScop()

std::unique_ptr< Scop > polly::ScopBuilder::getScop ( )

inline

Try to build the Polly IR of static control part on the current SESE-Region.

Returns: Give up the ownership of the scop object or static control part for the region

Definition at line 780 of file ScopBuilder.h.

References scop.

Referenced by polly::ScopInfo::recompute(), and polly::ScopInfoRegionPass::runOnRegion().

◆ hasNonHoistableBasePtrInScop()

bool ScopBuilder::hasNonHoistableBasePtrInScop	(	MemoryAccess *	MA,
		isl::union_map	Writes
	)

private

Check if the base ptr of MA is in the SCoP but not hoistable.

Definition at line 2679 of file ScopBuilder.cpp.

References getNonHoistableCtx(), polly::MemoryAccess::getOriginalBaseAddr(), isl::set::is_null(), scop, and polly::Value.

Referenced by getNonHoistableCtx().

◆ hoistInvariantLoads()

void ScopBuilder::hoistInvariantLoads ( )

private

Hoist invariant memory loads and check for required ones.

We first identify "common" invariant loads, thus loads that are invariant and can be hoisted. Then we check if all required invariant loads have been identified as (common) invariant. A load is a required invariant load if it was assumed to be invariant during SCoP detection, e.g., to assume loop bounds to be affine or runtime alias checks to be placeable. In case a required invariant load was not identified as (common) invariant we will drop this SCoP. An example for both "common" as well as required invariant loads is given below:

for (int i = 1; i < *LB[0]; i++) for (int j = 1; j < *LB[1]; j++) A[i][j] += A[0][0] + (*V);

Common inv. loads: V, A[0][0], LB[0], LB[1] Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)

Definition at line 2632 of file ScopBuilder.cpp.

References addInvariantLoads(), getNonHoistableCtx(), isl::set::is_null(), polly::PollyInvariantLoadHoisting, and scop.

Referenced by buildScop().

◆ isRequiredInvariantLoad()

bool polly::ScopBuilder::isRequiredInvariantLoad ( LoadInst * LI ) const

inlineprivate

Return true if and only if LI is a required invariant load.

Definition at line 650 of file ScopBuilder.h.

References LI, and scop.

Referenced by getNonHoistableCtx().

◆ LoopStackElement()

polly::ScopBuilder::LoopStackElement	(	Loop *	L,
		isl::schedule	S,
		unsigned	NumBlocksProcessed
	)

inlineprivate

Definition at line 726 of file ScopBuilder.h.

◆ operator=()

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

delete

◆ propagateDomainConstraints()

bool ScopBuilder::propagateDomainConstraints	(	Region *	R,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Propagate the domain constraints through the region R.

Parameters

R	The region we currently build branching conditions for.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Returns: True if there was no problem and false otherwise.

Definition at line 588 of file ScopBuilder.cpp.

References addLoopBoundsToHeaderDomain(), assert, Domain, getPredecessorDomainConstraints(), getRegionNodeBasicBlock(), polly::getRegionNodeLoop(), LI, propagateDomainConstraints(), and scop.

Referenced by buildDomains(), and propagateDomainConstraints().

◆ propagateDomainConstraintsToRegionExit()

void ScopBuilder::propagateDomainConstraintsToRegionExit	(	BasicBlock *	BB,
		Loop *	BBLoop,
		SmallPtrSetImpl< BasicBlock * > &	FinishedExitBlocks,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Propagate domains that are known due to graph properties.

As a CFG is mostly structured we use the graph properties to propagate domains without the need to compute all path conditions. In particular, if a block A dominates a block B and B post-dominates A we know that the domain of B is a superset of the domain of A. As we do not have post-dominator information available here we use the less precise region information. Given a region R, we know that the exit is always executed if the entry was executed, thus the domain of the exit is a superset of the domain of the entry. In case the exit can only be reached from within the region the domains are in fact equal. This function will use this property to avoid the generation of condition constraints that determine when a branch is taken. If BB is a region entry block we will propagate its domain to the region exit block. Additionally, we put the region exit block in the FinishedExitBlocks set so we can later skip edges from within the region to that block.

Parameters

BB	The block for which the domain is currently propagated.
BBLoop	The innermost affine loop surrounding `BB`.
FinishedExitBlocks	Set of region exits the domain was set for.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Definition at line 630 of file ScopBuilder.cpp.

References adjustDomainDimensions(), assert, Domain, isl::set::empty(), isl::set::get_space(), polly::getFirstNonBoxedLoopFor(), isl::set::is_null(), LI, scop, and isl::set::unite().

Referenced by buildDomainsWithBranchConstraints().

◆ propagateInvalidStmtDomains()

bool ScopBuilder::propagateInvalidStmtDomains	(	Region *	R,
		DenseMap< BasicBlock *, isl::set > &	InvalidDomainMap
	)

private

Propagate invalid domains of statements through R.

This method will propagate invalid statement domains through R and at the same time add error block domains to them. Additionally, the domains of error statements and those only reachable via error statements will be replaced by an empty set. Later those will be removed completely.

Parameters

R	The currently traversed region.
InvalidDomainMap	BB to InvalidDomain map for the BB of current region.

Returns: True if there was no problem and false otherwise.

Definition at line 999 of file ScopBuilder.cpp.

References adjustDomainDimensions(), polly::AS_RESTRICTION, assert, isl::set::coalesce(), polly::COMPLEXITY, containsErrorBlock(), Domain, DT, isl::set::empty(), polly::ERRORBLOCK, polly::getFirstNonBoxedLoopFor(), getRegionNodeBasicBlock(), polly::getRegionNodeLoop(), getRegionNodeSuccessor(), isl::set::intersect(), isl::set::is_empty(), LI, polly::MaxDisjunctsInDomain, isl::set::n_basic_set(), propagateInvalidStmtDomains(), polly::recordAssumption(), RecordedAssumptions, scop, SD, isl::set::unite(), and unsignedFromIslSize().

Referenced by buildDomains(), and propagateInvalidStmtDomains().

◆ shouldModelInst()

bool ScopBuilder::shouldModelInst	(	Instruction *	Inst,
		Loop *	L
	)

private

Should an instruction be modeled in a ScopStmt.

Parameters

Inst	The instruction to check.
L	The loop in which context the instruction is looked at.

Returns: True if the instruction should be modeled.

Definition at line 1776 of file ScopBuilder.cpp.

References polly::canSynthesize(), polly::isIgnoredIntrinsic(), scop, and SE.

Referenced by buildEqivClassBlockStmts(), buildSequentialBlockStmts(), and buildStmts().

◆ splitAliasGroupsByDomain()

void ScopBuilder::splitAliasGroupsByDomain ( AliasGroupVectorTy & AliasGroups )

private

Split alias groups by iteration domains.

We split each group based on the domains of the minimal/maximal accesses. That means two minimal/maximal accesses are only in a group if their access domains intersect. Otherwise, they are in different groups.

Parameters

AliasGroups The alias groups to split

Definition at line 3406 of file ScopBuilder.cpp.

References getAccessDomain(), isl::set::is_disjoint(), and isl::set::unite().

Referenced by buildAliasGroups().

◆ updateAccessDimensionality()

void ScopBuilder::updateAccessDimensionality ( )

private

Update access dimensionalities.

When detecting memory accesses different accesses to the same array may have built with different dimensionality, as outer zero-values dimensions may not have been recognized as separate dimensions. This function goes again over all memory accesses and updates their dimensionality to match the dimensionality of the underlying ScopArrayInfo object.

Definition at line 2298 of file ScopBuilder.cpp.

References polly::Array, isDivisible(), scop, and SE.

Referenced by finalizeAccesses().

◆ verifyInvariantLoads()

void ScopBuilder::verifyInvariantLoads ( )

private

Verify that all required invariant loads have been hoisted.

Invariant load hoisting is not guaranteed to hoist all loads that were assumed to be scop invariant during scop detection. This function checks for cases where the hoisting failed, but where it would have been necessary for our scop modeling to be correct. In case of insufficient hoisting the scop is marked as invalid.

In the example below Bound[1] is required to be invariant:

for (int i = 1; i < Bound[0]; i++) for (int j = 1; j < Bound[1]; j++) ...

Definition at line 2618 of file ScopBuilder.cpp.

References assert, polly::INVARIANTLOAD, LI, and scop.

Referenced by buildScop().

Member Data Documentation

◆ AA

AAResults& polly::ScopBuilder::AA

private

The AAResults to build AliasSetTracker.

Definition at line 36 of file ScopBuilder.h.

Referenced by buildAccessCallInst(), and buildAliasGroupsForAccesses().

◆ ArrayBasePointers

SmallSetVector<Value *, 16> polly::ScopBuilder::ArrayBasePointers

private

Set of all accessed array base pointers.

Definition at line 60 of file ScopBuilder.h.

Referenced by addArrayAccess(), and buildScop().

◆ DL

const DataLayout& polly::ScopBuilder::DL

private

Target data for element size computing.

Definition at line 39 of file ScopBuilder.h.

Referenced by buildAccessMultiDimFixed(), buildAccessMultiDimParam(), canAlwaysBeHoisted(), and getNonHoistableCtx().

◆ DT

DominatorTree& polly::ScopBuilder::DT

private

DominatorTree to reason about guaranteed execution.

Definition at line 42 of file ScopBuilder.h.

Referenced by addMemoryAccess(), addUserAssumptions(), buildDomainsWithBranchConstraints(), buildScop(), getPredecessorDomainConstraints(), and propagateInvalidStmtDomains().

◆ GlobalReads

SmallVector<std::pair<ScopStmt *, Instruction *>, 16> polly::ScopBuilder::GlobalReads

private

Set of instructions that might read any memory location.

Definition at line 57 of file ScopBuilder.h.

Referenced by buildAccessCallInst(), and buildScop().

◆ LI

LoopInfo& polly::ScopBuilder::LI

private

◆ NumBlocksProcessed

unsigned polly::ScopBuilder::NumBlocksProcessed

private

Definition at line 724 of file ScopBuilder.h.

Referenced by buildSchedule().

◆ ORE

OptimizationRemarkEmitter& polly::ScopBuilder::ORE

private

An optimization diagnostic interface to add optimization remarks.

Definition at line 54 of file ScopBuilder.h.

Referenced by addUserAssumptions(), buildAliasGroup(), buildScop(), and ScopBuilder().

◆ RecordedAssumptions

RecordedAssumptionsTy polly::ScopBuilder::RecordedAssumptions

private

Collection to hold taken assumptions.

There are two reasons why we want to record assumptions first before we add them to the assumed/invalid context: 1) If the SCoP is not profitable or otherwise invalid without the assumed/invalid context we do not have to compute it. 2) Information about the context are gathered rather late in the SCoP construction (basically after we know all parameters), thus the user might see overly complicated assumptions to be taken while they will only be simplified later on.

Definition at line 75 of file ScopBuilder.h.

Referenced by addLoopBoundsToHeaderDomain(), addRecordedAssumptions(), assumeNoOutOfBounds(), buildAccessRelations(), getPwAff(), propagateInvalidStmtDomains(), and ScopBuilder().

◆ Schedule

isl::schedule polly::ScopBuilder::Schedule

private

Definition at line 720 of file ScopBuilder.h.

Referenced by buildSchedule().

◆ scop

std::unique_ptr<Scop> polly::ScopBuilder::scop

private

Definition at line 63 of file ScopBuilder.h.

Referenced by addInvariantLoads(), addLoopBoundsToHeaderDomain(), addMemoryAccess(), addRecordedAssumptions(), addUserAssumptions(), addUserContext(), adjustDomainDimensions(), assumeNoOutOfBounds(), buildAccessFunctions(), buildAccessMemIntrinsic(), buildAccessMultiDimFixed(), buildAccessMultiDimParam(), buildAccessRelations(), buildAccessSingleDim(), buildAliasChecks(), buildAliasGroup(), buildAliasGroups(), buildAliasGroupsForAccesses(), buildConditionSets(), buildDomain(), buildDomains(), buildDomainsWithBranchConstraints(), buildEqivClassBlockStmts(), buildEscapingDependences(), buildInvariantEquivalenceClasses(), buildPHIAccesses(), buildSchedule(), buildScop(), buildSequentialBlockStmts(), buildStmts(), calculateMinMaxAccess(), canAlwaysBeHoisted(), canonicalizeDynamicBasePtrs(), ensurePHIWrite(), ensureValueRead(), ensureValueWrite(), foldAccessRelations(), foldSizeConstantsToRight(), getNonHoistableCtx(), getPredecessorDomainConstraints(), getPwAff(), getScop(), hasNonHoistableBasePtrInScop(), hoistInvariantLoads(), isRequiredInvariantLoad(), propagateDomainConstraints(), propagateDomainConstraintsToRegionExit(), propagateInvalidStmtDomains(), ScopBuilder(), shouldModelInst(), updateAccessDimensionality(), and verifyInvariantLoads().

◆ SD

ScopDetection& polly::ScopBuilder::SD

private

Valid Regions for Scop.

Definition at line 48 of file ScopBuilder.h.

Referenced by buildAccessFunctions(), buildConditionSets(), buildDomains(), buildDomainsWithBranchConstraints(), buildScop(), and propagateInvalidStmtDomains().

◆ SE

ScalarEvolution& polly::ScopBuilder::SE

private

The ScalarEvolution to help building Scop.

Definition at line 51 of file ScopBuilder.h.

Referenced by addInvariantLoads(), addUserAssumptions(), buildAccessCallInst(), buildAccessMemIntrinsic(), buildAccessMultiDimFixed(), buildAccessMultiDimParam(), buildAccessSingleDim(), buildConditionSets(), buildInvariantEquivalenceClasses(), buildPHIAccesses(), buildScop(), foldSizeConstantsToRight(), shouldModelInst(), and updateAccessDimensionality().

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

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ AliasGroupTy

◆ AliasGroupVectorTy

◆ LoopStackElementTy

◆ LoopStackTy

Constructor & Destructor Documentation

◆ ScopBuilder() [1/2]

◆ ScopBuilder() [2/2]

◆ ~ScopBuilder()

Member Function Documentation

◆ addArrayAccess()

◆ addInvariantLoads()

◆ addLoopBoundsToHeaderDomain()

◆ addMemoryAccess()

◆ addPHIReadAccess()

◆ addRecordedAssumptions()

◆ addUserAssumptions()

◆ addUserContext()

◆ adjustDomainDimensions()

◆ assumeNoOutOfBounds()

◆ buildAccessCallInst()

◆ buildAccessFunctions() [1/2]

◆ buildAccessFunctions() [2/2]

◆ buildAccessMemIntrinsic()

◆ buildAccessMultiDimFixed()

◆ buildAccessMultiDimParam()

◆ buildAccessRelations()

◆ buildAccessSingleDim()

◆ buildAliasChecks()

◆ buildAliasGroup()

◆ buildAliasGroups()

◆ buildAliasGroupsForAccesses()

◆ buildConditionSets() [1/3]

◆ buildConditionSets() [2/3]

◆ buildConditionSets() [3/3]

◆ buildDomain()

◆ buildDomains()

◆ buildDomainsWithBranchConstraints()

◆ buildEqivClassBlockStmts()

◆ buildEscapingDependences()

◆ buildInvariantEquivalenceClasses()

◆ buildMemoryAccess()

◆ buildPHIAccesses()

◆ buildScalarDependences()

◆ buildSchedule() [1/3]

◆ buildSchedule() [2/3]

◆ buildSchedule() [3/3]

◆ buildScop()

◆ buildSequentialBlockStmts()

◆ buildStmts()

◆ buildUnsignedConditionSets()

◆ calculateMinMaxAccess()

◆ canAlwaysBeHoisted()

◆ canonicalizeDynamicBasePtrs()

◆ checkForReductions()

◆ collectCandidateReductionLoads()

◆ collectSurroundingLoops()

◆ ensurePHIWrite()

◆ ensureValueRead()

◆ ensureValueWrite()

◆ finalizeAccesses()

◆ foldAccessRelations()

◆ foldSizeConstantsToRight()

◆ getNonHoistableCtx()

◆ getPredecessorDomainConstraints()

◆ getPwAff()

◆ getScop()

◆ hasNonHoistableBasePtrInScop()

◆ hoistInvariantLoads()

◆ isRequiredInvariantLoad()

◆ LoopStackElement()

◆ operator=()

◆ propagateDomainConstraints()

◆ propagateDomainConstraintsToRegionExit()

◆ propagateInvalidStmtDomains()