Static Control Part. More...

#include <ScopInfo.h>

Classes
struct	ScopStatistics

Public Types
using	MinMaxAccessTy = std::pair< isl::pw_multi_aff, isl::pw_multi_aff >
	Type to represent a pair of minimal/maximal access to an array.

using	MinMaxVectorTy = SmallVector< MinMaxAccessTy, 4 >
	Vector of minimal/maximal accesses to different arrays.

using	MinMaxVectorPairTy = std::pair< MinMaxVectorTy, MinMaxVectorTy >
	Pair of minimal/maximal access vectors representing read write and read only accesses.

using	MinMaxVectorPairVectorTy = SmallVector< MinMaxVectorPairTy, 4 >
	Vector of pair of minimal/maximal access vectors representing non read only and read only accesses for each alias group.

Private Types
using	StmtSet = std::list< ScopStmt >

using	ArrayInfoMapTy = std::map< std::pair< AssertingVH< const Value >, MemoryKind >, std::unique_ptr< ScopArrayInfo > >

using	ArrayNameMapTy = StringMap< std::unique_ptr< ScopArrayInfo > >

using	ArrayInfoSetTy = SetVector< ScopArrayInfo * >

Private Member Functions
	Scop (Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE, int ID)
	Scop constructor; invoked from ScopBuilder::buildScop.

MemoryAccess *	lookupBasePtrAccess (MemoryAccess *MA)
	Return the access for the base ptr of `MA` if any.

void	createParameterId (const SCEV *Param)
	Create an id for `Param` and store it in the ParameterIds map.

void	buildContext ()
	Build the Context of the Scop.

void	addParameterBounds ()
	Add the bounds of the parameters to the context.

void	simplifyContexts ()
	Simplify the assumed and invalid context.

void	addScopStmt (BasicBlock BB, StringRef Name, Loop SurroundingLoop, std::vector< Instruction * > Instructions)
	Create a new SCoP statement for `BB`.

void	addScopStmt (Region R, StringRef Name, Loop SurroundingLoop, std::vector< Instruction * > EntryBlockInstructions)
	Create a new SCoP statement for `R`.

void	removeFromStmtMap (ScopStmt &Stmt)
	Removes `Stmt` from the StmtMap.

void	removeStmtNotInDomainMap ()
	Removes all statements where the entry block of the statement does not have a corresponding domain in the domain map (or it is empty).

isl::union_map	getAccessesOfType (std::function< bool(MemoryAccess &)> Predicate)
	Collect all memory access relations of a given type.

Private Attributes
std::shared_ptr< isl_ctx >	IslCtx
	Isl context.

ScalarEvolution *	SE

DominatorTree *	DT

Region &	R
	The underlying Region.

std::optional< std::string >	name
	The name of the SCoP (identical to the regions name)

AccFuncVector	AccessFunctions

bool	IsOptimized = false
	Flag to indicate that the scheduler actually optimized the SCoP.

bool	HasSingleExitEdge
	True if the underlying region has a single exiting block.

bool	HasErrorBlock = false
	Flag to remember if the SCoP contained an error block or not.

unsigned	MaxLoopDepth = 0
	Max loop depth.

unsigned	CopyStmtsNum = 0
	Number of copy statements.

StmtSet	Stmts
	The statements in this Scop.

ParameterSetTy	Parameters
	Parameters of this Scop.

DenseMap< const SCEV *, isl::id >	ParameterIds
	Mapping from parameters to their ids.

ScopDetection::DetectionContext &	DC
	The context of the SCoP created during SCoP detection.

OptimizationRemarkEmitter &	ORE
	OptimizationRemarkEmitter object for displaying diagnostic remarks.

DenseMap< BasicBlock , std::vector< ScopStmt > >	StmtMap
	A map from basic blocks to vector of SCoP statements.

DenseMap< Instruction , ScopStmt >	InstStmtMap
	A map from instructions to SCoP statements.

DenseMap< BasicBlock *, isl::set >	DomainMap
	A map from basic blocks to their domains.

isl::set	Context
	Constraints on parameters.

SCEVAffinator	Affinator
	The affinator used to translate SCEVs to isl expressions.

ArrayInfoMapTy	ScopArrayInfoMap
	A map to remember ScopArrayInfo objects for all base pointers.

ArrayNameMapTy	ScopArrayNameMap
	A map to remember ScopArrayInfo objects for all names of memory references.

ArrayInfoSetTy	ScopArrayInfoSet
	A set to remember ScopArrayInfo objects.

isl::set	AssumedContext
	The assumptions under which this scop was built.

isl::set	InvalidContext
	The restrictions under which this SCoP was built.

isl::set	DefinedBehaviorContext
	The context under which the SCoP must have defined behavior.

isl::schedule	Schedule
	The schedule of the SCoP.

bool	HasDisableHeuristicsHint = false
	Is this Scop marked as not to be transformed by an optimization heuristic?

bool	ScheduleModified = false
	Whether the schedule has been modified after derived from the CFG by ScopBuilder.

MinMaxVectorPairVectorTy	MinMaxAliasGroups
	The set of minimal/maximal accesses for each alias group.

ValueToValueMap	InvEquivClassVMap
	Mapping from invariant loads to the representing invariant load of their equivalence class.

InvariantEquivClassesTy	InvariantEquivClasses
	List of invariant accesses.

long	ArrayIdx = 0
	The smallest array index not yet assigned.

long	StmtIdx = 0
	The smallest statement index not yet assigned.

const int	ID
	A number that uniquely represents a Scop within its function.

DenseMap< Value , MemoryAccess >	ValueDefAccs
	Map of values to the MemoryAccess that writes its definition.

DenseMap< PHINode , MemoryAccess >	PHIReadAccs
	Map of values to the MemoryAccess that reads a PHI.

DenseMap< const ScopArrayInfo , SmallVector< MemoryAccess , 4 > >	ValueUseAccs
	List of all uses (i.e.

DenseMap< const ScopArrayInfo , SmallVector< MemoryAccess , 4 > >	PHIIncomingAccs
	List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or MemoryKind::ExitPHI scalar.

Friends
class	ScopBuilder

Helper functions for printing the Scop.
using	array_iterator = ArrayInfoSetTy::iterator

using	const_array_iterator = ArrayInfoSetTy::const_iterator

using	array_range = iterator_range< ArrayInfoSetTy::iterator >

using	const_array_range = iterator_range< ArrayInfoSetTy::const_iterator >

void	printContext (raw_ostream &OS) const

void	printArrayInfo (raw_ostream &OS) const

void	printStatements (raw_ostream &OS, bool PrintInstructions) const

void	printAliasAssumptions (raw_ostream &OS) const

	Scop (const Scop &)=delete

Scop &	operator= (const Scop &)=delete

	~Scop ()

unsigned	getCopyStmtsNum ()
	Get the count of copy statements added to this Scop.

ScopStmt *	addScopStmt (isl::map SourceRel, isl::map TargetRel, isl::set Domain)
	Create a new copy statement.

void	addAccessFunction (MemoryAccess *Access)
	Add the access function to all MemoryAccess objects of the Scop created in this pass.

void	addAccessData (MemoryAccess *Access)
	Add metadata for `Access`.

void	addInvariantEquivClass (const InvariantEquivClassTy &InvariantEquivClass)
	Add new invariant access equivalence class.

void	addInvariantLoadMapping (const Value LoadInst, Value ClassRep)
	Add mapping from invariant loads to the representing invariant load of their equivalence class.

void	removeAccessData (MemoryAccess *Access)
	Remove the metadata stored for `Access`.

ScalarEvolution *	getSE () const
	Return the scalar evolution.

DominatorTree *	getDT () const
	Return the dominator tree.

LoopInfo *	getLI () const
	Return the LoopInfo used for this Scop.

size_t	getNumParams () const
	Get the count of parameters used in this Scop.

bool	isParam (const SCEV *Param) const
	Return whether given SCEV is used as the parameter in this Scop.

void	addParams (const ParameterSetTy &NewParameters)
	Take a list of parameters and add the new ones to the scop.

iterator_range< ParameterSetTy::iterator >	parameters () const
	Return an iterator range containing the scop parameters.

iterator_range< InvariantEquivClassesTy::iterator >	invariantEquivClasses ()
	Return an iterator range containing invariant accesses.

iterator_range< AccFuncVector::iterator >	access_functions ()
	Return an iterator range containing all the MemoryAccess objects of the Scop.

bool	isEmpty () const
	Return whether this scop is empty, i.e.

StringRef	getName ()

array_iterator	array_begin ()

array_iterator	array_end ()

const_array_iterator	array_begin () const

const_array_iterator	array_end () const

array_range	arrays ()

const_array_range	arrays () const

isl::id	getIdForParam (const SCEV *Parameter) const
	Return the isl_id that represents a certain parameter.

const Region &	getRegion () const
	Get the maximum region of this static control part.

Region &	getRegion ()

Function &	getFunction () const
	Return the function this SCoP is in.

bool	contains (const Loop *L) const
	Check if `L` is contained in the SCoP.

bool	contains (const BasicBlock *BB) const
	Check if `BB` is contained in the SCoP.

bool	contains (const Instruction *I) const
	Check if `I` is contained in the SCoP.

BasicBlock *	getExit () const
	Return the unique exit block of the SCoP.

BasicBlock *	getExitingBlock () const
	Return the unique exiting block of the SCoP if any.

BasicBlock *	getEntry () const
	Return the unique entry block of the SCoP.

BasicBlock *	getEnteringBlock () const
	Return the unique entering block of the SCoP if any.

bool	isExit (BasicBlock *BB) const
	Return true if `BB` is the exit block of the SCoP.

Region::block_range	blocks () const
	Return a range of all basic blocks in the SCoP.

bool	isDominatedBy (const DominatorTree &DT, BasicBlock *BB) const
	Return true if and only if `BB` dominates the SCoP.

unsigned	getMaxLoopDepth () const
	Get the maximum depth of the loop.

InvariantEquivClassTy *	lookupInvariantEquivClass (Value *Val)
	Return the invariant equivalence class for `Val` if any.

InvariantEquivClassesTy &	getInvariantAccesses ()
	Return the set of invariant accesses.

bool	hasInvariantAccesses ()
	Check if the scop has any invariant access.

void	markAsOptimized ()
	Mark the SCoP as optimized by the scheduler.

bool	isOptimized () const
	Check if the SCoP has been optimized by the scheduler.

int	getID () const
	Return the ID of the Scop.

std::pair< std::string, std::string >	getEntryExitStr () const
	Get the name of the entry and exit blocks of this Scop.

std::string	getNameStr () const
	Get the name of this Scop.

isl::set	getContext () const
	Get the constraint on parameter of this Scop.

isl::set	getDefinedBehaviorContext () const
	Return the context where execution behavior is defined.

isl::set	getBestKnownDefinedBehaviorContext () const
	Return the define behavior context, or if not available, its approximation from all other contexts.

isl::space	getParamSpace () const
	Return space of isl context parameters.

isl::space	getFullParamSpace () const
	Return the full space of parameters.

isl::set	getAssumedContext () const
	Get the assumed context for this Scop.

bool	hasFeasibleRuntimeContext () const
	Return true if the optimized SCoP can be executed.

bool	isEffectiveAssumption (isl::set Set, AssumptionSign Sign)
	Check if the assumption in `Set` is trivial or not.

bool	trackAssumption (AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB)
	Track and report an assumption.

void	intersectDefinedBehavior (isl::set Set, AssumptionSign Sign)
	Add the conditions from `Set` (or subtract them if `Sign` is AS_RESTRICTION) to the defined behaviour context.

void	addAssumption (AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB, bool RTC=true)
	Add assumptions to assumed context.

void	invalidate (AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB=nullptr)
	Mark the scop as invalid.

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

bool	hasTrivialInvalidContext () const
	Return true if and only if the InvalidContext is trivial (=empty).

const MinMaxVectorPairVectorTy &	getAliasGroups () const
	Return all alias groups for this SCoP.

void	addAliasGroup (MinMaxVectorTy &MinMaxAccessesReadWrite, MinMaxVectorTy &MinMaxAccessesReadOnly)

void	removeStmts (function_ref< bool(ScopStmt &)> ShouldDelete, bool AfterHoisting=true)
	Remove statements from the list of scop statements.

std::string	getContextStr () const
	Get an isl string representing the context.

std::string	getAssumedContextStr () const
	Get an isl string representing the assumed context.

std::string	getInvalidContextStr () const
	Get an isl string representing the invalid context.

ArrayRef< ScopStmt * >	getStmtListFor (BasicBlock *BB) const
	Return the list of ScopStmts that represent the given `BB`.

ScopStmt *	getIncomingStmtFor (const Use &U) const
	Get the statement to put a PHI WRITE into.

ScopStmt *	getLastStmtFor (BasicBlock *BB) const
	Return the last statement representing `BB`.

ArrayRef< ScopStmt * >	getStmtListFor (Region *R) const
	Return the ScopStmts that represents the Region `R`, or nullptr if it is not represented by any statement in this Scop.

ArrayRef< ScopStmt * >	getStmtListFor (RegionNode *RN) const
	Return the ScopStmts that represents `RN`; can return nullptr if the RegionNode is not within the SCoP or has been removed due to simplifications.

ScopStmt *	getStmtFor (Instruction *Inst) const
	Return the ScopStmt an instruction belongs to, or nullptr if it does not belong to any statement in this Scop.

size_t	getSize () const
	Return the number of statements in the SCoP.

static void	incrementNumberOfAliasingAssumptions (unsigned Step)
	Increment actual number of aliasing assumptions taken.

Statements Iterators
These iterators iterate over all statements of this Scop.
using	iterator = StmtSet::iterator

using	const_iterator = StmtSet::const_iterator

using	reverse_iterator = StmtSet::reverse_iterator

using	const_reverse_iterator = StmtSet::const_reverse_iterator

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

const InvariantLoadsSetTy &	getRequiredInvariantLoads () const
	Return the set of required invariant loads.

void	addRequiredInvariantLoad (LoadInst *LI)
	Add `LI` to the set of required invariant loads.

const BoxedLoopsSetTy &	getBoxedLoops () const
	Return the set of boxed (thus overapproximated) loops.

bool	isNonAffineSubRegion (const Region *R)
	Return true if and only if `R` is a non-affine subregion.

const MapInsnToMemAcc &	getInsnToMemAccMap () const

ScopArrayInfo *	getOrCreateScopArrayInfo (Value BasePtr, Type ElementType, ArrayRef< const SCEV * > Sizes, MemoryKind Kind, const char *BaseName=nullptr)
	Return the (possibly new) ScopArrayInfo object for `Access`.

ScopArrayInfo *	createScopArrayInfo (Type *ElementType, const std::string &BaseName, const std::vector< unsigned > &Sizes)
	Create an array and return the corresponding ScopArrayInfo object.

ScopArrayInfo *	getScopArrayInfoOrNull (Value *BasePtr, MemoryKind Kind)
	Return the cached ScopArrayInfo object for `BasePtr`.

ScopArrayInfo *	getScopArrayInfo (Value *BasePtr, MemoryKind Kind)
	Return the cached ScopArrayInfo object for `BasePtr`.

void	invalidateScopArrayInfo (Value *BasePtr, MemoryKind Kind)
	Invalidate ScopArrayInfo object for base address.

void	setContext (isl::set NewContext)
	Set new isl context.

void	updateMaxLoopDepth (unsigned Depth)
	Update maximal loop depth.

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

bool	isProfitable (bool ScalarsAreUnprofitable) const
	Return true if this SCoP can be profitably optimized.

bool	hasErrorBlock () const
	Return true if the SCoP contained at least one error block.

void	notifyErrorBlock ()
	Notify SCoP that it contains an error block.

bool	hasSingleExitEdge () const
	Return true if the underlying region has a single exiting block.

void	print (raw_ostream &OS, bool PrintInstructions) const
	Print the static control part.

void	dump () const
	Print the ScopStmt to stderr.

isl::ctx	getIslCtx () const
	Get the isl context of this static control part.

const std::shared_ptr< isl_ctx > &	getSharedIslCtx () const
	Directly return the shared_ptr of the context.

PWACtx	getPwAff (const SCEV E, BasicBlock BB=nullptr, bool NonNegative=false, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
	Compute the isl representation for the SCEV `E`.

isl::pw_aff	getPwAffOnly (const SCEV E, BasicBlock BB=nullptr, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
	Compute the isl representation for the SCEV `E`.

bool	hasNSWAddRecForLoop (Loop *L)
	Check if an <nsw> AddRec for the loop L is cached.

isl::set	getDomainConditions (const ScopStmt *Stmt) const
	Return the domain of `Stmt`.

isl::set	getDomainConditions (BasicBlock *BB) const
	Return the domain of `BB`.

isl::set &	getOrInitEmptyDomain (BasicBlock *BB)
	Return the domain of `BB`. If it does not exist, create an empty one.

bool	isDomainDefined (BasicBlock *BB) const
	Check if domain is determined for `BB`.

void	setDomain (BasicBlock *BB, isl::set &Domain)
	Set domain for `BB`.

isl::union_set	getDomains () const
	Get a union set containing the iteration domains of all statements.

isl::union_map	getMayWrites ()
	Get a union map of all may-writes performed in the SCoP.

isl::union_map	getMustWrites ()
	Get a union map of all must-writes performed in the SCoP.

isl::union_map	getWrites ()
	Get a union map of all writes performed in the SCoP.

isl::union_map	getReads ()
	Get a union map of all reads performed in the SCoP.

isl::union_map	getAccesses ()
	Get a union map of all memory accesses performed in the SCoP.

isl::union_map	getAccesses (ScopArrayInfo *Array)
	Get a union map of all memory accesses performed in the SCoP.

isl::union_map	getSchedule () const
	Get the schedule of all the statements in the SCoP.

isl::schedule	getScheduleTree () const
	Get a schedule tree describing the schedule of all statements.

void	setSchedule (isl::union_map NewSchedule)
	Update the current schedule.

void	setScheduleTree (isl::schedule NewSchedule)
	Update the current schedule.

bool	isOriginalSchedule () const
	Whether the schedule is the original schedule as derived from the CFG by ScopBuilder.

bool	restrictDomains (isl::union_set Domain)
	Intersects the domains of all statements in the SCoP.

int	getRelativeLoopDepth (const Loop *L) const
	Get the depth of a loop relative to the outermost loop in the Scop.

ScopArrayInfo *	getArrayInfoByName (const std::string BaseName)
	Find the ScopArrayInfo associated with an isl Id that has name `Name`.

void	simplifySCoP (bool AfterHoisting)
	Simplify the SCoP representation.

long	getNextArrayIdx ()
	Get the next free array index.

long	getNextStmtIdx ()
	Get the next free statement index.

const SCEV *	getRepresentingInvariantLoadSCEV (const SCEV *S) const
	Get the representing SCEV for `S` if applicable, otherwise `S`.

MemoryAccess *	getValueDef (const ScopArrayInfo *SAI) const
	Return the MemoryAccess that writes an llvm::Value, represented by a ScopArrayInfo.

ArrayRef< MemoryAccess * >	getValueUses (const ScopArrayInfo *SAI) const
	Return all MemoryAccesses that us an llvm::Value, represented by a ScopArrayInfo.

MemoryAccess *	getPHIRead (const ScopArrayInfo *SAI) const
	Return the MemoryAccess that represents an llvm::PHINode.

ArrayRef< MemoryAccess * >	getPHIIncomings (const ScopArrayInfo *SAI) const
	Return all MemoryAccesses for all incoming statements of a PHINode, represented by a ScopArrayInfo.

bool	isEscaping (Instruction *Inst)
	Return whether `Inst` has a use outside of this SCoP.

ScopStatistics	getStatistics () const
	Collect statistic about this SCoP.

bool	hasDisableHeuristicsHint () const
	Is this Scop marked as not to be transformed by an optimization heuristic? In this case, only user-directed transformations are allowed.

void	markDisableHeuristics ()
	Mark this Scop to not apply an optimization heuristic.

Detailed Description

Static Control Part.

A Scop is the polyhedral representation of a control flow region detected by the Scop detection. It is generated by translating the LLVM-IR and abstracting its effects.

A Scop consists of a set of:

A set of statements executed in the Scop.
A set of global parameters Those parameters are scalar integer values, which are constant during execution.
A context This context contains information about the values the parameters can take and relations between different parameters.

Definition at line 1628 of file ScopInfo.h.

Member Typedef Documentation

◆ array_iterator

using polly::Scop::array_iterator = ArrayInfoSetTy::iterator

Definition at line 2051 of file ScopInfo.h.

◆ array_range

using polly::Scop::array_range = iterator_range<ArrayInfoSetTy::iterator>

Definition at line 2053 of file ScopInfo.h.

◆ ArrayInfoMapTy

using polly::Scop::ArrayInfoMapTy = std::map<std::pair<AssertingVH<const Value>, MemoryKind>, std::unique_ptr<ScopArrayInfo> >

private

Definition at line 1720 of file ScopInfo.h.

◆ ArrayInfoSetTy

using polly::Scop::ArrayInfoSetTy = SetVector<ScopArrayInfo *>

private

Definition at line 1726 of file ScopInfo.h.

◆ ArrayNameMapTy

using polly::Scop::ArrayNameMapTy = StringMap<std::unique_ptr<ScopArrayInfo> >

private

Definition at line 1724 of file ScopInfo.h.

◆ const_array_iterator

using polly::Scop::const_array_iterator = ArrayInfoSetTy::const_iterator

Definition at line 2052 of file ScopInfo.h.

◆ const_array_range

using polly::Scop::const_array_range = iterator_range<ArrayInfoSetTy::const_iterator>

Definition at line 2054 of file ScopInfo.h.

◆ const_iterator

using polly::Scop::const_iterator = StmtSet::const_iterator

Definition at line 2348 of file ScopInfo.h.

◆ const_reverse_iterator

using polly::Scop::const_reverse_iterator = StmtSet::const_reverse_iterator

Definition at line 2356 of file ScopInfo.h.

◆ iterator

using polly::Scop::iterator = StmtSet::iterator

Definition at line 2347 of file ScopInfo.h.

◆ MinMaxAccessTy

using polly::Scop::MinMaxAccessTy = std::pair<isl::pw_multi_aff, isl::pw_multi_aff>

Type to represent a pair of minimal/maximal access to an array.

Definition at line 1631 of file ScopInfo.h.

◆ MinMaxVectorPairTy

using polly::Scop::MinMaxVectorPairTy = std::pair<MinMaxVectorTy, MinMaxVectorTy>

Pair of minimal/maximal access vectors representing read write and read only accesses.

Definition at line 1638 of file ScopInfo.h.

◆ MinMaxVectorPairVectorTy

using polly::Scop::MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>

Vector of pair of minimal/maximal access vectors representing non read only and read only accesses for each alias group.

Definition at line 1642 of file ScopInfo.h.

◆ MinMaxVectorTy

using polly::Scop::MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>

Vector of minimal/maximal accesses to different arrays.

Definition at line 1634 of file ScopInfo.h.

◆ reverse_iterator

using polly::Scop::reverse_iterator = StmtSet::reverse_iterator

Definition at line 2355 of file ScopInfo.h.

◆ StmtSet

using polly::Scop::StmtSet = std::list<ScopStmt>

private

Definition at line 1687 of file ScopInfo.h.

Constructor & Destructor Documentation

◆ Scop() [1/2]

Scop::Scop	(	Region &	R,
		ScalarEvolution &	SE,
		LoopInfo &	LI,
		DominatorTree &	DT,
		ScopDetection::DetectionContext &	DC,
		OptimizationRemarkEmitter &	ORE,
		int	ID
	)

private

Scop constructor; invoked from ScopBuilder::buildScop.

Definition at line 1600 of file ScopInfo.cpp.

References buildContext(), getIslCtx(), ISL_ARG_ALL, isl_ctx_parse_options(), ISL_ON_ERROR_ABORT, isl_options_set_on_error(), isl_options_set_schedule_serialize_sccs(), IslArgs(), IslCtx, and IslOnErrorAbort().

◆ Scop() [2/2]

polly::Scop::Scop ( const Scop & )

delete

◆ ~Scop()

Scop::~Scop ( )

default

Member Function Documentation

◆ access_functions()

iterator_range< AccFuncVector::iterator > polly::Scop::access_functions ( )

inline

Return an iterator range containing all the MemoryAccess objects of the Scop.

Definition at line 2037 of file ScopInfo.h.

References AccessFunctions.

◆ addAccessData()

void Scop::addAccessData ( MemoryAccess * Access )

Add metadata for Access.

Definition at line 2411 of file ScopInfo.cpp.

References assert, polly::MemoryAccess::getOriginalScopArrayInfo(), polly::MemoryAccess::isOriginalAnyPHIKind(), polly::MemoryAccess::isOriginalValueKind(), polly::MemoryAccess::isRead(), polly::MemoryAccess::isWrite(), PHIIncomingAccs, and ValueUseAccs.

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

◆ addAccessFunction()

void polly::Scop::addAccessFunction ( MemoryAccess * Access )

inline

Add the access function to all MemoryAccess objects of the Scop created in this pass.

Definition at line 1970 of file ScopInfo.h.

References AccessFunctions, assert, polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getAccessValue(), polly::MemoryAccess::isOriginalPHIKind(), polly::MemoryAccess::isOriginalValueKind(), polly::MemoryAccess::isRead(), polly::MemoryAccess::isWrite(), polly::PHI, PHIReadAccs, and ValueDefAccs.

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

◆ addAliasGroup()

void polly::Scop::addAliasGroup	(	MinMaxVectorTy &	MinMaxAccessesReadWrite,
		MinMaxVectorTy &	MinMaxAccessesReadOnly
	)

inline

Definition at line 2281 of file ScopInfo.h.

References MinMaxAliasGroups.

◆ addAssumption()

void Scop::addAssumption	(	AssumptionKind	Kind,
		isl::set	Set,
		DebugLoc	Loc,
		AssumptionSign	Sign,
		BasicBlock *	BB,
		bool	RTC = `true`
	)

Add assumptions to assumed context.

The assumptions added will be assumed to hold during the execution of the scop. However, as they are generally not statically provable, at code generation time run-time checks will be generated that ensure the assumptions hold.

WARNING: We currently exploit in simplifyAssumedContext the knowledge that assumptions do not change the set of statement instances executed.

Parameters

Kind	The assumption kind describing the underlying cause.
Set	The relations between parameters that are assumed to hold.
Loc	The location in the source that caused this assumption.
Sign	Enum to indicate if the assumptions in `Set` are positive (needed/assumptions) or negative (invalid/restrictions).
BB	The block in which this assumption was taken. Used to calculate hotness when emitting remark.
RTC	Does the assumption require a runtime check?

Definition at line 2006 of file ScopInfo.cpp.

References polly::AS_ASSUMPTION, AssumedContext, isl::set::coalesce(), getContext(), isl::set::gist_params(), isl::set::intersect(), intersectDefinedBehavior(), InvalidContext, trackAssumption(), and isl::set::unite().

Referenced by invalidate().

◆ addInvariantEquivClass()

void polly::Scop::addInvariantEquivClass ( const InvariantEquivClassTy & InvariantEquivClass )

inline

Add new invariant access equivalence class.

Definition at line 1991 of file ScopInfo.h.

References InvariantEquivClasses.

◆ addInvariantLoadMapping()

void polly::Scop::addInvariantLoadMapping	(	const Value *	LoadInst,
		Value *	ClassRep
	)

inline

Add mapping from invariant loads to the representing invariant load of their equivalence class.

Definition at line 1997 of file ScopInfo.h.

References InvEquivClassVMap.

◆ addParameterBounds()

void Scop::addParameterBounds ( )

private

Add the bounds of the parameters to the context.

Definition at line 1498 of file ScopInfo.cpp.

References addRangeBoundsToSet(), polly::AS_ASSUMPTION, Context, intersectDefinedBehavior(), isl::param, Parameters, and SE.

Referenced by realignParams().

◆ addParams()

void Scop::addParams ( const ParameterSetTy & NewParameters )

Take a list of parameters and add the new ones to the scop.

Definition at line 1469 of file ScopInfo.cpp.

References createParameterId(), polly::extractConstantFactor(), getRepresentingInvariantLoadSCEV(), Parameters, and SE.

◆ addRequiredInvariantLoad()

void polly::Scop::addRequiredInvariantLoad ( LoadInst * LI )

inline

Add LI to the set of required invariant loads.

Definition at line 2370 of file ScopInfo.h.

References DC, and polly::ScopDetection::DetectionContext::RequiredILS.

◆ addScopStmt() [1/3]

void Scop::addScopStmt	(	BasicBlock *	BB,
		StringRef	Name,
		Loop *	SurroundingLoop,
		std::vector< Instruction * >	Instructions
	)

private

Create a new SCoP statement for BB.

A new statement for BB will be created and added to the statement vector and map.

Parameters

BB	The basic block we build the statement for.
Name	The name of the new statement.
SurroundingLoop	The loop the created statement is contained in.
Instructions	The instructions in the statement.

Definition at line 2296 of file ScopInfo.cpp.

References assert, InstStmtMap, StmtMap, and Stmts.

◆ addScopStmt() [2/3]

ScopStmt * Scop::addScopStmt	(	isl::map	SourceRel,
		isl::map	TargetRel,
		isl::set	Domain
	)

Create a new copy statement.

A new statement will be created and added to the statement vector.

Parameters

SourceRel	The source location.
TargetRel	The target location.
Domain	The original domain under which the copy statement would be executed.

Definition at line 2333 of file ScopInfo.cpp.

References assert, CopyStmtsNum, Domain, isl::map::domain(), and Stmts.

◆ addScopStmt() [3/3]

void Scop::addScopStmt	(	Region *	R,
		StringRef	Name,
		Loop *	SurroundingLoop,
		std::vector< Instruction * >	EntryBlockInstructions
	)

private

Create a new SCoP statement for R.

A new statement for R will be created and added to the statement vector and map.

Parameters

R	The region we build the statement for.
Name	The name of the new statement.
SurroundingLoop	The loop the created statement is contained in.
EntryBlockInstructions	The (interesting) instructions in the entry block of the region statement.

Definition at line 2309 of file ScopInfo.cpp.

References assert, InstStmtMap, R, StmtMap, and Stmts.

◆ array_begin() [1/2]

array_iterator polly::Scop::array_begin ( )

inline

Definition at line 2056 of file ScopInfo.h.

References ScopArrayInfoSet.

Referenced by arrays().

◆ array_begin() [2/2]

const_array_iterator polly::Scop::array_begin ( ) const

inline

Definition at line 2060 of file ScopInfo.h.

References ScopArrayInfoSet.

◆ array_end() [1/2]

array_iterator polly::Scop::array_end ( )

inline

Definition at line 2058 of file ScopInfo.h.

References ScopArrayInfoSet.

Referenced by arrays().

◆ array_end() [2/2]

const_array_iterator polly::Scop::array_end ( ) const

inline

Definition at line 2064 of file ScopInfo.h.

References ScopArrayInfoSet.

◆ arrays() [1/2]

array_range polly::Scop::arrays ( )

inline

Definition at line 2068 of file ScopInfo.h.

References array_begin(), and array_end().

Referenced by getArrayInfoByName(), and printArrayInfo().

◆ arrays() [2/2]

const_array_range polly::Scop::arrays ( ) const

inline

Definition at line 2072 of file ScopInfo.h.

References array_begin(), and array_end().

◆ begin() [1/2]

iterator polly::Scop::begin ( )

inline

Definition at line 2350 of file ScopInfo.h.

References Stmts.

◆ begin() [2/2]

const_iterator polly::Scop::begin ( ) const

inline

Definition at line 2352 of file ScopInfo.h.

References Stmts.

◆ blocks()

Region::block_range polly::Scop::blocks ( ) const

inline

Return a range of all basic blocks in the SCoP.

Definition at line 2117 of file ScopInfo.h.

References R.

◆ buildContext()

void Scop::buildContext ( )

private

Build the Context of the Scop.

Definition at line 1490 of file ScopInfo.cpp.

References AssumedContext, Context, DefinedBehaviorContext, isl::set::empty(), getIslCtx(), InvalidContext, isl::space::params_alloc(), and isl::set::universe().

Referenced by Scop().

◆ contains() [1/3]

bool polly::Scop::contains ( const BasicBlock * BB ) const

inline

Check if BB is contained in the SCoP.

Definition at line 2096 of file ScopInfo.h.

References R.

◆ contains() [2/3]

bool polly::Scop::contains ( const Instruction * I ) const

inline

Check if I is contained in the SCoP.

Definition at line 2099 of file ScopInfo.h.

References R.

◆ contains() [3/3]

bool polly::Scop::contains ( const Loop * L ) const

inline

Check if L is contained in the SCoP.

Definition at line 2093 of file ScopInfo.h.

References R.

Referenced by polly::addReferencesFromStmt(), and isEscaping().

◆ createParameterId()

void Scop::createParameterId ( const SCEV * Param )

private

Create an id for Param and store it in the ParameterIds map.

Definition at line 1436 of file ScopInfo.cpp.

References isl::id::alloc(), assert, polly::getIslCompatibleName(), getIslCtx(), getNumParams(), ParameterIds, Parameters, polly::UseInstructionNames, and polly::Value.

Referenced by addParams().

◆ createScopArrayInfo()

ScopArrayInfo * Scop::createScopArrayInfo	(	Type *	ElementType,
		const std::string &	BaseName,
		const std::vector< unsigned > &	Sizes
	)

Create an array and return the corresponding ScopArrayInfo object.

Parameters

ElementType	The type of the elements stored in this array.
BaseName	The name of this memory reference.
Sizes	The sizes of dimensions.

Definition at line 1760 of file ScopInfo.cpp.

References polly::Array, polly::getConstant(), getContext(), getOrCreateScopArrayInfo(), getSE(), and size.

◆ dump()

LLVM_DUMP_METHOD void Scop::dump ( ) const

Print the ScopStmt to stderr.

Definition at line 2162 of file ScopInfo.cpp.

References print().

◆ end() [1/2]

iterator polly::Scop::end ( )

inline

Definition at line 2351 of file ScopInfo.h.

References Stmts.

◆ end() [2/2]

const_iterator polly::Scop::end ( ) const

inline

Definition at line 2353 of file ScopInfo.h.

References Stmts.

◆ getAccesses() [1/2]

isl::union_map Scop::getAccesses ( )

Get a union map of all memory accesses performed in the SCoP.

Definition at line 2243 of file ScopInfo.cpp.

References getAccessesOfType().

◆ getAccesses() [2/2]

isl::union_map Scop::getAccesses ( ScopArrayInfo * Array )

Get a union map of all memory accesses performed in the SCoP.

Parameters

Array The array to which the accesses should belong.

Definition at line 2247 of file ScopInfo.cpp.

References polly::Array, getAccessesOfType(), and polly::MemoryAccess::getScopArrayInfo().

◆ getAccessesOfType()

isl::union_map Scop::getAccessesOfType ( std::function< bool(MemoryAccess &)> Predicate )

private

Collect all memory access relations of a given type.

Parameters

Predicate A predicate function that returns true if an access is of a given type.

Returns: The set of memory accesses in the scop that match the predicate.

Definition at line 2209 of file ScopInfo.cpp.

References isl::union_map::coalesce(), Domain, isl::union_map::empty(), getIslCtx(), isl::map::intersect_domain(), and isl::union_map::unite().

Referenced by getAccesses(), getMayWrites(), getMustWrites(), getReads(), and getWrites().

◆ getAliasGroups()

const MinMaxVectorPairVectorTy & polly::Scop::getAliasGroups ( ) const

inline

Return all alias groups for this SCoP.

Definition at line 2277 of file ScopInfo.h.

References MinMaxAliasGroups.

Referenced by benefitsFromPolly().

◆ getArrayInfoByName()

ScopArrayInfo * Scop::getArrayInfoByName ( const std::string BaseName )

Find the ScopArrayInfo associated with an isl Id that has name Name.

Definition at line 2403 of file ScopInfo.cpp.

References arrays().

◆ getAssumedContext()

isl::set Scop::getAssumedContext ( ) const

Get the assumed context for this Scop.

Returns: The assumed context of this Scop.

Definition at line 1841 of file ScopInfo.cpp.

References assert, AssumedContext, and isl::set::is_null().

Referenced by hasFeasibleRuntimeContext().

◆ getAssumedContextStr()

std::string Scop::getAssumedContextStr ( ) const

Get an isl string representing the assumed context.

Definition at line 1792 of file ScopInfo.cpp.

References assert, AssumedContext, and isl::set::is_null().

◆ getBestKnownDefinedBehaviorContext()

isl::set polly::Scop::getBestKnownDefinedBehaviorContext ( ) const

inline

Return the define behavior context, or if not available, its approximation from all other contexts.

Definition at line 2169 of file ScopInfo.h.

References AssumedContext, Context, DefinedBehaviorContext, isl::set::intersect_params(), InvalidContext, isl::set::is_null(), and isl::set::subtract().

Referenced by polly::MemoryAccess::setNewAccessRelation().

◆ getBoxedLoops()

const BoxedLoopsSetTy & polly::Scop::getBoxedLoops ( ) const

inline

Return the set of boxed (thus overapproximated) loops.

Definition at line 2373 of file ScopInfo.h.

References polly::ScopDetection::DetectionContext::BoxedLoopsSet, and DC.

Referenced by getStatistics().

◆ getContext()

isl::set Scop::getContext ( ) const

Get the constraint on parameter of this Scop.

Returns: The constraint on parameter of this Scop.

Definition at line 1824 of file ScopInfo.cpp.

References Context.

Referenced by addAssumption(), polly::IslNodeBuilder::createNewAccesses(), createScopArrayInfo(), polly::BlockGenerator::generateConditionalExecution(), polly::BlockGenerator::generateScalarLoads(), getContextStr(), getParamSpace(), getStatistics(), polly::MemoryAccess::realignParams(), polly::ScopStmt::realignParams(), and realignParams().

◆ getContextStr()

std::string Scop::getContextStr ( ) const

Get an isl string representing the context.

Definition at line 1788 of file ScopInfo.cpp.

References getContext().

◆ getCopyStmtsNum()

unsigned polly::Scop::getCopyStmtsNum ( )

inline

Get the count of copy statements added to this Scop.

Returns: The count of copy statements added to this Scop.

Definition at line 1955 of file ScopInfo.h.

References CopyStmtsNum.

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

◆ getDefinedBehaviorContext()

isl::set polly::Scop::getDefinedBehaviorContext ( ) const

inline

Return the context where execution behavior is defined.

Might return nullptr.

Definition at line 2165 of file ScopInfo.h.

References DefinedBehaviorContext.

◆ getDomainConditions() [1/2]

isl::set Scop::getDomainConditions ( BasicBlock * BB ) const

Return the domain of BB.

Parameters

BB	The block for which the conditions should be returned.

Definition at line 1588 of file ScopInfo.cpp.

References DomainMap, getDomainConditions(), and R.

◆ getDomainConditions() [2/2]

isl::set Scop::getDomainConditions ( const ScopStmt * Stmt ) const

Return the domain of Stmt.

Parameters

Stmt	The statement for which the conditions should be returned.

Definition at line 1584 of file ScopInfo.cpp.

References getDomainConditions(), and polly::ScopStmt::getEntryBlock().

Referenced by getDomainConditions().

◆ getDomains()

isl::union_set Scop::getDomains ( ) const

Get a union set containing the iteration domains of all statements.

Definition at line 2192 of file ScopInfo.cpp.

References Domain, polly::ScopStmt::getDomain(), getIslCtx(), isl_space_params_alloc(), isl_union_set_add_set(), isl_union_set_empty(), isl::manage(), and isl::set::release().

Referenced by getScheduleTree(), hasFeasibleRuntimeContext(), and setSchedule().

◆ getDT()

DominatorTree * polly::Scop::getDT ( ) const

inline

Return the dominator tree.

Definition at line 2008 of file ScopInfo.h.

References DT.

◆ getEnteringBlock()

BasicBlock * polly::Scop::getEnteringBlock ( ) const

inline

Return the unique entering block of the SCoP if any.

Definition at line 2111 of file ScopInfo.h.

References R.

◆ getEntry()

BasicBlock * polly::Scop::getEntry ( ) const

inline

Return the unique entry block of the SCoP.

Definition at line 2108 of file ScopInfo.h.

References R.

Referenced by isDominatedBy().

◆ getEntryExitStr()

std::pair< std::string, std::string > Scop::getEntryExitStr ( ) const

Get the name of the entry and exit blocks of this Scop.

These along with the function name can uniquely identify a Scop.

Returns: std::pair whose first element is the entry name & second element is the exit name.

Definition at line 1807 of file ScopInfo.cpp.

References R.

Referenced by getNameStr().

◆ getExit()

BasicBlock * polly::Scop::getExit ( ) const

inline

Return the unique exit block of the SCoP.

Definition at line 2102 of file ScopInfo.h.

References R.

Referenced by isExit().

◆ getExitingBlock()

BasicBlock * polly::Scop::getExitingBlock ( ) const

inline

Return the unique exiting block of the SCoP if any.

Definition at line 2105 of file ScopInfo.h.

References R.

◆ getFullParamSpace()

isl::space Scop::getFullParamSpace ( ) const

Return the full space of parameters.

getParamSpace will only return the parameters of the context that are actually constrained, whereas getFullParamSpace will return all

Definition at line 1828 of file ScopInfo.cpp.

References getIdForParam(), getIslCtx(), isl::param, ParameterIds, Parameters, isl::space::params_alloc(), and isl::space::set_dim_id().

Referenced by realignParams().

◆ getFunction()

Function & polly::Scop::getFunction ( ) const

inline

Return the function this SCoP is in.

Definition at line 2090 of file ScopInfo.h.

References Function, and R.

Referenced by getOrCreateScopArrayInfo(), and print().

◆ getID()

int polly::Scop::getID ( ) const

inline

Return the ID of the Scop.

Definition at line 2145 of file ScopInfo.h.

References ID.

◆ getIdForParam()

isl::id Scop::getIdForParam ( const SCEV * Parameter ) const

Return the isl_id that represents a certain parameter.

Parameters

Parameter A SCEV that was recognized as a Parameter.

Returns: The corresponding isl_id or NULL otherwise.

Definition at line 1480 of file ScopInfo.cpp.

References getRepresentingInvariantLoadSCEV(), and ParameterIds.

Referenced by getFullParamSpace().

◆ getIncomingStmtFor()

ScopStmt * Scop::getIncomingStmtFor ( const Use & U ) const

Get the statement to put a PHI WRITE into.

Parameters

U	The operand of a PHINode.

Definition at line 2355 of file ScopInfo.cpp.

References getLastStmtFor(), getStmtFor(), and polly::PHI.

◆ getInsnToMemAccMap()

const MapInsnToMemAcc & polly::Scop::getInsnToMemAccMap ( ) const

inline

Definition at line 2380 of file ScopInfo.h.

References DC, and polly::ScopDetection::DetectionContext::InsnToMemAcc.

◆ getInvalidContext()

isl::set Scop::getInvalidContext ( ) const

Get the invalid context for this Scop.

Returns: The invalid context of this Scop.

Definition at line 2050 of file ScopInfo.cpp.

References InvalidContext.

Referenced by hasFeasibleRuntimeContext().

◆ getInvalidContextStr()

std::string Scop::getInvalidContextStr ( ) const

Get an isl string representing the invalid context.

Definition at line 1797 of file ScopInfo.cpp.

References InvalidContext.

◆ getInvariantAccesses()

InvariantEquivClassesTy & polly::Scop::getInvariantAccesses ( )

inline

Return the set of invariant accesses.

Definition at line 2131 of file ScopInfo.h.

References InvariantEquivClasses.

◆ getIslCtx()

isl::ctx Scop::getIslCtx ( ) const

Get the isl context of this static control part.

Returns: The isl context of this static control part.

Definition at line 2165 of file ScopInfo.cpp.

References IslCtx.

Referenced by buildContext(), polly::IslNodeBuilder::createNewAccesses(), createParameterId(), getAccessesOfType(), getDomains(), getFullParamSpace(), polly::ScopStmt::getIslCtx(), getOrCreateScopArrayInfo(), polly::MemoryAccess::MemoryAccess(), and Scop().

◆ getLastStmtFor()

ScopStmt * Scop::getLastStmtFor ( BasicBlock * BB ) const

Return the last statement representing BB.

Of the sequence of statements that represent a BB, this is the last one to be executed. It is typically used to determine which instruction to add a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required to be executed last, only that the incoming value is available in it.

Definition at line 2372 of file ScopInfo.cpp.

References getStmtListFor().

Referenced by getIncomingStmtFor().

◆ getLI()

LoopInfo * polly::Scop::getLI ( ) const

inline

Return the LoopInfo used for this Scop.

Definition at line 2011 of file ScopInfo.h.

References Affinator, and polly::SCEVAffinator::getLI().

Referenced by findReferencesInStmt(), and getStatistics().

◆ getMaxLoopDepth()

unsigned polly::Scop::getMaxLoopDepth ( ) const

inline

Get the maximum depth of the loop.

Returns: The maximum depth of the loop.

Definition at line 2125 of file ScopInfo.h.

References MaxLoopDepth.

Referenced by print().

◆ getMayWrites()

isl::union_map Scop::getMayWrites ( )

Get a union map of all may-writes performed in the SCoP.

Definition at line 2231 of file ScopInfo.cpp.

References getAccessesOfType(), and polly::MemoryAccess::isMayWrite().

◆ getMustWrites()

isl::union_map Scop::getMustWrites ( )

Get a union map of all must-writes performed in the SCoP.

Definition at line 2227 of file ScopInfo.cpp.

References getAccessesOfType(), and polly::MemoryAccess::isMustWrite().

◆ getName()

StringRef polly::Scop::getName ( )

inline

Definition at line 2045 of file ScopInfo.h.

References name, and R.

◆ getNameStr()

std::string Scop::getNameStr ( ) const

Get the name of this Scop.

Definition at line 1801 of file ScopInfo.cpp.

References getEntryExitStr().

Referenced by print().

◆ getNextArrayIdx()

long polly::Scop::getNextArrayIdx ( )

inline

Get the next free array index.

This function returns a unique index which can be used to identify an array.

Definition at line 2600 of file ScopInfo.h.

References ArrayIdx.

◆ getNextStmtIdx()

long polly::Scop::getNextStmtIdx ( )

inline

Get the next free statement index.

This function returns a unique index which can be used to identify a statement.

Definition at line 2606 of file ScopInfo.h.

References StmtIdx.

◆ getNumParams()

size_t polly::Scop::getNumParams ( ) const

inline

Get the count of parameters used in this Scop.

Returns: The count of parameters used in this Scop.

Definition at line 2016 of file ScopInfo.h.

References Parameters.

Referenced by createParameterId().

◆ getOrCreateScopArrayInfo()

ScopArrayInfo * Scop::getOrCreateScopArrayInfo	(	Value *	BasePtr,
		Type *	ElementType,
		ArrayRef< const SCEV * >	Sizes,
		MemoryKind	Kind,
		const char *	BaseName = `nullptr`
	)

Return the (possibly new) ScopArrayInfo object for Access.

Parameters

ElementType	The type of the elements stored in this array.
Kind	The kind of the array info object.
BaseName	The optional name of this memory reference.

Definition at line 1736 of file ScopInfo.cpp.

References assert, polly::DELINEARIZATION, getFunction(), getIslCtx(), invalidate(), ScopArrayInfoMap, ScopArrayInfoSet, and ScopArrayNameMap.

Referenced by createScopArrayInfo(), and polly::ScopStmt::ensureValueRead().

◆ getOrInitEmptyDomain()

isl::set & polly::Scop::getOrInitEmptyDomain ( BasicBlock * BB )

inline

Return the domain of BB. If it does not exist, create an empty one.

Definition at line 2518 of file ScopInfo.h.

References DomainMap.

◆ getParamSpace()

isl::space Scop::getParamSpace ( ) const

Return space of isl context parameters.

Returns the set of context parameters that are currently constrained. In case the full set of parameters is needed, see @getFullParamSpace.

Definition at line 1826 of file ScopInfo.cpp.

References isl::set::get_space(), and getContext().

Referenced by invalidate(), and simplifyContexts().

◆ getPHIIncomings()

ArrayRef< MemoryAccess * > Scop::getPHIIncomings ( const ScopArrayInfo * SAI ) const

Return all MemoryAccesses for all incoming statements of a PHINode, represented by a ScopArrayInfo.

Definition at line 2464 of file ScopInfo.cpp.

References assert, polly::ScopArrayInfo::isExitPHIKind(), polly::ScopArrayInfo::isPHIKind(), and PHIIncomingAccs.

◆ getPHIRead()

MemoryAccess * Scop::getPHIRead ( const ScopArrayInfo * SAI ) const

Return the MemoryAccess that represents an llvm::PHINode.

ExitPHIs's PHINode is not within the SCoPs. This function returns nullptr for them.

Definition at line 2454 of file ScopInfo.cpp.

References assert, polly::ScopArrayInfo::getBasePtr(), polly::ScopArrayInfo::isExitPHIKind(), polly::ScopArrayInfo::isPHIKind(), polly::PHI, and PHIReadAccs.

◆ getPwAff()

__isl_give PWACtx Scop::getPwAff	(	const SCEV *	E,
		BasicBlock *	BB = `nullptr`,
		bool	NonNegative = `false`,
		RecordedAssumptionsTy *	RecordedAssumptions = `nullptr`
	)

Compute the isl representation for the SCEV E.

Parameters

E	The SCEV that should be translated.
BB	An (optional) basic block in which the isl_pw_aff is computed. SCEVs known to not reference any loops in the SCoP can be passed without a `BB`.
NonNegative	Flag to indicate the `E` has to be non-negative.

Note that this function will always return a valid isl_pw_aff. However, if the translation of E was deemed to complex the SCoP is invalidated and a dummy value of appropriate dimension is returned. This allows to bail for complex cases without "error handling code" needed on the users side.

Definition at line 2167 of file ScopInfo.cpp.

References Affinator, polly::COMPLEXITY, polly::SCEVAffinator::getPwAff(), invalidate(), SE, and polly::SCEVAffinator::takeNonNegativeAssumption().

Referenced by getPwAffOnly().

◆ getPwAffOnly()

isl::pw_aff Scop::getPwAffOnly	(	const SCEV *	E,
		BasicBlock *	BB = `nullptr`,
		RecordedAssumptionsTy *	RecordedAssumptions = `nullptr`
	)

Compute the isl representation for the SCEV E.

This function is like

See also: Scop::getPwAff() but strips away the invalid domain part associated with the piecewise affine function.

Definition at line 2202 of file ScopInfo.cpp.

References getPwAff().

◆ getReads()

isl::union_map Scop::getReads ( )

Get a union map of all reads performed in the SCoP.

Definition at line 2239 of file ScopInfo.cpp.

References getAccessesOfType(), and polly::MemoryAccess::isRead().

◆ getRegion() [1/2]

Region & polly::Scop::getRegion ( )

inline

Definition at line 2087 of file ScopInfo.h.

References R.

◆ getRegion() [2/2]

const Region & polly::Scop::getRegion ( ) const

inline

Get the maximum region of this static control part.

Returns: The maximum region of this static control part.

Definition at line 2086 of file ScopInfo.h.

References R.

Referenced by polly::ScopBuilder::collectSurroundingLoops(), and polly::IslNodeBuilder::createNewAccesses().

◆ getRelativeLoopDepth()

int Scop::getRelativeLoopDepth ( const Loop * L ) const

Get the depth of a loop relative to the outermost loop in the Scop.

This will return 0 if L is an outermost loop in the SCoP >0 for other loops in the SCoP -1 if L is nullptr or there is no outermost loop in the SCoP

Definition at line 2389 of file ScopInfo.cpp.

References assert, and R.

◆ getRepresentingInvariantLoadSCEV()

const SCEV * Scop::getRepresentingInvariantLoadSCEV ( const SCEV * S ) const

Get the representing SCEV for S if applicable, otherwise S.

Invariant loads of the same location are put in an equivalence class and only one of them is chosen as a representing element that will be modeled as a parameter. The others have to be normalized, i.e., replaced by the representing element of their equivalence class, in order to get the correct parameter value, e.g., in the SCEVAffinator.

Parameters

S	The SCEV to normalize.

Returns: The representing SCEV for invariant loads or S if none.

Definition at line 1425 of file ScopInfo.cpp.

References InvEquivClassVMap, and SE.

Referenced by addParams(), and getIdForParam().

◆ getRequiredInvariantLoads()

const InvariantLoadsSetTy & polly::Scop::getRequiredInvariantLoads ( ) const

inline

Return the set of required invariant loads.

Definition at line 2365 of file ScopInfo.h.

References DC, and polly::ScopDetection::DetectionContext::RequiredILS.

◆ getSchedule()

isl::union_map Scop::getSchedule ( ) const

Get the schedule of all the statements in the SCoP.

Returns: The schedule of all the statements in the SCoP, if the schedule of the Scop does not contain extension nodes, and nullptr, otherwise.

Definition at line 2252 of file ScopInfo.cpp.

References getScheduleTree().

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

◆ getScheduleTree()

isl::schedule Scop::getScheduleTree ( ) const

Get a schedule tree describing the schedule of all statements.

Definition at line 2257 of file ScopInfo.cpp.

References getDomains(), isl::schedule::intersect_domain(), and Schedule.

Referenced by getSchedule().

◆ getScopArrayInfo()

ScopArrayInfo * Scop::getScopArrayInfo	(	Value *	BasePtr,
		MemoryKind	Kind
	)

Return the cached ScopArrayInfo object for BasePtr.

Parameters

BasePtr	The base pointer the object has been stored for.
Kind	The kind of array info object.

Returns: The ScopArrayInfo pointer (may assert if no such pointer is available).

Definition at line 1782 of file ScopInfo.cpp.

References assert, and getScopArrayInfoOrNull().

◆ getScopArrayInfoOrNull()

ScopArrayInfo * Scop::getScopArrayInfoOrNull	(	Value *	BasePtr,
		MemoryKind	Kind
	)

Return the cached ScopArrayInfo object for BasePtr.

Parameters

BasePtr	The base pointer the object has been stored for.
Kind	The kind of array info object.

Returns: The ScopArrayInfo pointer or NULL if no such pointer is available.

Definition at line 1777 of file ScopInfo.cpp.

References ScopArrayInfoMap.

Referenced by getScopArrayInfo().

◆ getSE()

ScalarEvolution * Scop::getSE ( ) const

Return the scalar evolution.

Definition at line 2294 of file ScopInfo.cpp.

References SE.

Referenced by polly::MemoryAccess::computeBoundsOnAccessRelation(), createScopArrayInfo(), and polly::IslNodeBuilder::createSubstitutions().

◆ getSharedIslCtx()

const std::shared_ptr< isl_ctx > & polly::Scop::getSharedIslCtx ( ) const

inline

Directly return the shared_ptr of the context.

Definition at line 2478 of file ScopInfo.h.

References IslCtx.

Referenced by runIslAst().

◆ getSize()

size_t polly::Scop::getSize ( ) const

inline

Return the number of statements in the SCoP.

Definition at line 2341 of file ScopInfo.h.

References Stmts.

◆ getStatistics()

Scop::ScopStatistics Scop::getStatistics ( ) const

Collect statistic about this SCoP.

These are most commonly used for LLVM's static counters (Statistic.h) in various places. If statistics are disabled, only zeros are returned to avoid the overhead.

Definition at line 2495 of file ScopInfo.cpp.

◆ getStmtFor()

ScopStmt * polly::Scop::getStmtFor ( Instruction * Inst ) const

inline

Return the ScopStmt an instruction belongs to, or nullptr if it does not belong to any statement in this Scop.

Definition at line 2336 of file ScopInfo.h.

References InstStmtMap.

Referenced by getIncomingStmtFor(), and lookupBasePtrAccess().

◆ getStmtListFor() [1/3]

ArrayRef< ScopStmt * > Scop::getStmtListFor ( BasicBlock * BB ) const

Return the list of ScopStmts that represent the given BB.

Definition at line 2348 of file ScopInfo.cpp.

References StmtMap.

Referenced by getLastStmtFor(), and getStmtListFor().

◆ getStmtListFor() [2/3]

ArrayRef< ScopStmt * > Scop::getStmtListFor ( Region * R ) const

Return the ScopStmts that represents the Region R, or nullptr if it is not represented by any statement in this Scop.

Definition at line 2385 of file ScopInfo.cpp.

References getStmtListFor(), and R.

◆ getStmtListFor() [3/3]

ArrayRef< ScopStmt * > Scop::getStmtListFor ( RegionNode * RN ) const

Return the ScopStmts that represents RN; can return nullptr if the RegionNode is not within the SCoP or has been removed due to simplifications.

Definition at line 2379 of file ScopInfo.cpp.

References getStmtListFor().

◆ getValueDef()

MemoryAccess * Scop::getValueDef ( const ScopArrayInfo * SAI ) const

Return the MemoryAccess that writes an llvm::Value, represented by a ScopArrayInfo.

There can be at most one such MemoryAccess per llvm::Value in the SCoP. Zero is possible for read-only values.

Definition at line 2436 of file ScopInfo.cpp.

References assert, polly::ScopArrayInfo::getBasePtr(), polly::ScopArrayInfo::isValueKind(), and ValueDefAccs.

◆ getValueUses()

ArrayRef< MemoryAccess * > Scop::getValueUses ( const ScopArrayInfo * SAI ) const

Return all MemoryAccesses that us an llvm::Value, represented by a ScopArrayInfo.

Definition at line 2446 of file ScopInfo.cpp.

References assert, polly::ScopArrayInfo::isValueKind(), and ValueUseAccs.

◆ getWrites()

isl::union_map Scop::getWrites ( )

Get a union map of all writes performed in the SCoP.

Definition at line 2235 of file ScopInfo.cpp.

References getAccessesOfType(), and polly::MemoryAccess::isWrite().

◆ hasDisableHeuristicsHint()

bool polly::Scop::hasDisableHeuristicsHint ( ) const

inline

Is this Scop marked as not to be transformed by an optimization heuristic? In this case, only user-directed transformations are allowed.

Definition at line 2666 of file ScopInfo.h.

References HasDisableHeuristicsHint.

◆ hasErrorBlock()

bool polly::Scop::hasErrorBlock ( ) const

inline

Return true if the SCoP contained at least one error block.

Definition at line 2452 of file ScopInfo.h.

References HasErrorBlock.

◆ hasFeasibleRuntimeContext()

bool Scop::hasFeasibleRuntimeContext ( ) const

Return true if the optimized SCoP can be executed.

In addition to the runtime check context this will also utilize the domain constraints to decide it the optimized version can actually be executed.

Returns: True if the optimized SCoP can be executed.

Definition at line 1874 of file ScopInfo.cpp.

References Context, getAssumedContext(), getDomains(), getInvalidContext(), isl::set::intersect_params(), isl::set::is_empty(), isl::boolean::is_false(), isl::set::is_subset(), params, and Stmts.

◆ hasInvariantAccesses()

bool polly::Scop::hasInvariantAccesses ( )

inline

Check if the scop has any invariant access.

Definition at line 2136 of file ScopInfo.h.

References InvariantEquivClasses.

◆ hasNSWAddRecForLoop()

bool polly::Scop::hasNSWAddRecForLoop ( Loop * L )

inline

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

Definition at line 2505 of file ScopInfo.h.

References Affinator, and polly::SCEVAffinator::hasNSWAddRecForLoop().

◆ hasSingleExitEdge()

bool polly::Scop::hasSingleExitEdge ( ) const

inline

Return true if the underlying region has a single exiting block.

Definition at line 2458 of file ScopInfo.h.

References HasSingleExitEdge.

Referenced by isEscaping().

◆ hasTrivialInvalidContext()

bool polly::Scop::hasTrivialInvalidContext ( ) const

inline

Return true if and only if the InvalidContext is trivial (=empty).

Definition at line 2274 of file ScopInfo.h.

References InvalidContext, and isl::set::is_empty().

◆ incrementNumberOfAliasingAssumptions()

void Scop::incrementNumberOfAliasingAssumptions ( unsigned Step )

static

Increment actual number of aliasing assumptions taken.

Parameters

Step	Number of new aliasing assumptions which should be added to the number of already taken assumptions.

Definition at line 2491 of file ScopInfo.cpp.

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

◆ intersectDefinedBehavior()

void Scop::intersectDefinedBehavior	(	isl::set	Set,
		AssumptionSign	Sign
	)

Add the conditions from Set (or subtract them if Sign is AS_RESTRICTION) to the defined behaviour context.

Definition at line 2025 of file ScopInfo.cpp.

References polly::AS_ASSUMPTION, DefinedBehaviorContext, isl::set::intersect(), isl::set::is_null(), MaxDisjunktsInDefinedBehaviourContext, isl::set::n_basic_set(), isl::size::release(), simplify, and isl::set::subtract().

Referenced by addAssumption(), and addParameterBounds().

◆ invalidate()

void Scop::invalidate	(	AssumptionKind	Kind,
		DebugLoc	Loc,
		BasicBlock *	BB = `nullptr`
	)

Mark the scop as invalid.

This method adds an assumption to the scop that is always invalid. As a result, the scop will not be optimized later on. This function is commonly called when a condition makes it impossible (or too compile time expensive) to process this scop any further.

Parameters

Kind	The assumption kind describing the underlying cause.
Loc	The location in the source that triggered .
BB	The BasicBlock where it was triggered.

Definition at line 2045 of file ScopInfo.cpp.

References addAssumption(), polly::AS_ASSUMPTION, isl::set::empty(), getParamSpace(), and POLLY_DEBUG.

Referenced by getOrCreateScopArrayInfo(), and getPwAff().

◆ invalidateScopArrayInfo()

void polly::Scop::invalidateScopArrayInfo	(	Value *	BasePtr,
		MemoryKind	Kind
	)

inline

Invalidate ScopArrayInfo object for base address.

Parameters

BasePtr	The base pointer of the ScopArrayInfo object to invalidate.
Kind	The Kind of the ScopArrayInfo object.

Definition at line 2423 of file ScopInfo.h.

References ScopArrayInfoMap, and ScopArrayInfoSet.

◆ invariantEquivClasses()

iterator_range< InvariantEquivClassesTy::iterator > polly::Scop::invariantEquivClasses ( )

inline

Return an iterator range containing invariant accesses.

Definition at line 2030 of file ScopInfo.h.

References InvariantEquivClasses.

◆ isDomainDefined()

bool polly::Scop::isDomainDefined ( BasicBlock * BB ) const

inline

Check if domain is determined for BB.

Definition at line 2521 of file ScopInfo.h.

References DomainMap.

◆ isDominatedBy()

bool Scop::isDominatedBy	(	const DominatorTree &	DT,
		BasicBlock *	BB
	)		const

Return true if and only if BB dominates the SCoP.

Definition at line 1486 of file ScopInfo.cpp.

References DT, and getEntry().

◆ isEffectiveAssumption()

bool Scop::isEffectiveAssumption	(	isl::set	Set,
		AssumptionSign	Sign
	)

Check if the assumption in Set is trivial or not.

Parameters

Set	The relations between parameters that are assumed to hold.
Sign	Enum to indicate if the assumptions in `Set` are positive (needed/assumptions) or negative (invalid/restrictions).

Returns: True if the assumption Set is not trivial.

Definition at line 1926 of file ScopInfo.cpp.

References polly::AS_ASSUMPTION, AssumedContext, Context, InvalidContext, isl::set::is_disjoint(), and isl::set::is_subset().

Referenced by trackAssumption().

◆ isEmpty()

bool polly::Scop::isEmpty ( ) const

inline

Return whether this scop is empty, i.e.

contains no statements that could be executed.

Definition at line 2043 of file ScopInfo.h.

References Stmts.

Referenced by isProfitable().

◆ isEscaping()

bool Scop::isEscaping ( Instruction * Inst )

Return whether Inst has a use outside of this SCoP.

Definition at line 2472 of file ScopInfo.cpp.

References assert, contains(), polly::getUseBlock(), hasSingleExitEdge(), and isExit().

◆ isExit()

bool polly::Scop::isExit ( BasicBlock * BB ) const

inline

Return true if BB is the exit block of the SCoP.

Definition at line 2114 of file ScopInfo.h.

References getExit().

Referenced by isEscaping().

◆ isNonAffineSubRegion()

bool polly::Scop::isNonAffineSubRegion ( const Region * R )

inline

Return true if and only if R is a non-affine subregion.

Definition at line 2376 of file ScopInfo.h.

References DC, polly::ScopDetection::DetectionContext::NonAffineSubRegionSet, and R.

◆ isOptimized()

bool polly::Scop::isOptimized ( ) const

inline

Check if the SCoP has been optimized by the scheduler.

Definition at line 2142 of file ScopInfo.h.

References IsOptimized.

Referenced by benefitsFromPolly().

◆ isOriginalSchedule()

bool polly::Scop::isOriginalSchedule ( ) const

inline

Whether the schedule is the original schedule as derived from the CFG by ScopBuilder.

Definition at line 2570 of file ScopInfo.h.

References ScheduleModified.

◆ isParam()

bool polly::Scop::isParam ( const SCEV * Param ) const

inline

Return whether given SCEV is used as the parameter in this Scop.

Definition at line 2019 of file ScopInfo.h.

References Parameters.

◆ isProfitable()

bool Scop::isProfitable ( bool ScalarsAreUnprofitable ) const

Return true if this SCoP can be profitably optimized.

Parameters

ScalarsAreUnprofitable Never consider statements with scalar writes as profitably optimizable.

Returns: Whether this SCoP can be profitably optimized.

Definition at line 1846 of file ScopInfo.cpp.

References isEmpty(), and polly::PollyProcessUnprofitable.

◆ lookupBasePtrAccess()

MemoryAccess * Scop::lookupBasePtrAccess ( MemoryAccess * MA )

private

Return the access for the base ptr of MA if any.

Definition at line 1886 of file ScopInfo.cpp.

References polly::MemoryAccess::getOriginalBaseAddr(), getStmtFor(), and polly::Value.

◆ lookupInvariantEquivClass()

InvariantEquivClassTy * Scop::lookupInvariantEquivClass ( Value * Val )

Return the invariant equivalence class for Val if any.

Definition at line 1713 of file ScopInfo.cpp.

References InvariantEquivClasses, InvEquivClassVMap, SE, and polly::Value.

Referenced by polly::MemoryAccess::setNewAccessRelation().

◆ markAsOptimized()

void polly::Scop::markAsOptimized ( )

inline

Mark the SCoP as optimized by the scheduler.

Definition at line 2139 of file ScopInfo.h.

References IsOptimized.

◆ markDisableHeuristics()

void polly::Scop::markDisableHeuristics ( )

inline

Mark this Scop to not apply an optimization heuristic.

Definition at line 2669 of file ScopInfo.h.

References HasDisableHeuristicsHint.

◆ notifyErrorBlock()

void polly::Scop::notifyErrorBlock ( )

inline

Notify SCoP that it contains an error block.

Definition at line 2455 of file ScopInfo.h.

References HasErrorBlock.

◆ operator=()

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

delete

◆ parameters()

iterator_range< ParameterSetTy::iterator > polly::Scop::parameters ( ) const

inline

Return an iterator range containing the scop parameters.

Definition at line 2025 of file ScopInfo.h.

References Parameters.

◆ print()

void Scop::print	(	raw_ostream &	OS,
		bool	PrintInstructions
	)		const

Print the static control part.

Parameters

OS	The output stream the static control part is printed to.
PrintInstructions	Whether to print the statement's instructions as well.

Definition at line 2139 of file ScopInfo.cpp.

References getFunction(), getMaxLoopDepth(), getNameStr(), InvariantEquivClasses, printAliasAssumptions(), printArrayInfo(), printContext(), and printStatements().

Referenced by dump().

◆ printAliasAssumptions()

void Scop::printAliasAssumptions ( raw_ostream & OS ) const

private

Definition at line 2073 of file ScopInfo.cpp.

References MinMaxAliasGroups.

Referenced by print().

◆ printArrayInfo()

void Scop::printArrayInfo ( raw_ostream & OS ) const

private

Definition at line 2123 of file ScopInfo.cpp.

References polly::Array, and arrays().

Referenced by print().

◆ printContext()

void Scop::printContext ( raw_ostream & OS ) const

private

Definition at line 2052 of file ScopInfo.cpp.

References AssumedContext, Context, DefinedBehaviorContext, InvalidContext, isl::set::is_null(), and Parameters.

Referenced by print().

◆ printStatements()

void Scop::printStatements	(	raw_ostream &	OS,
		bool	PrintInstructions
	)		const

private

Definition at line 2112 of file ScopInfo.cpp.

References polly::ScopStmt::print().

Referenced by print().

◆ rbegin() [1/2]

reverse_iterator polly::Scop::rbegin ( )

inline

Definition at line 2358 of file ScopInfo.h.

References Stmts.

◆ rbegin() [2/2]

const_reverse_iterator polly::Scop::rbegin ( ) const

inline

Definition at line 2360 of file ScopInfo.h.

References Stmts.

◆ realignParams()

void Scop::realignParams ( )

Align the parameters in the statement to the scop context.

Definition at line 1507 of file ScopInfo.cpp.

References addParameterBounds(), isl::set::align_params(), isl::schedule::align_params(), AssumedContext, Context, getContext(), getFullParamSpace(), isl::schedule::gist_domain_params(), InvalidContext, PollyIgnoreParamBounds(), polly::ScopStmt::realignParams(), and Schedule.

◆ removeAccessData()

void Scop::removeAccessData ( MemoryAccess * Access )

Remove the metadata stored for Access.

Definition at line 2421 of file ScopInfo.cpp.

References polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getAccessValue(), polly::MemoryAccess::getScopArrayInfo(), polly::MemoryAccess::isOriginalAnyPHIKind(), polly::MemoryAccess::isOriginalPHIKind(), polly::MemoryAccess::isOriginalValueKind(), polly::MemoryAccess::isRead(), polly::MemoryAccess::isWrite(), polly::PHI, PHIIncomingAccs, PHIReadAccs, ValueDefAccs, and ValueUseAccs.

Referenced by polly::ScopStmt::removeMemoryAccess(), and polly::ScopStmt::removeSingleMemoryAccess().

◆ removeFromStmtMap()

void Scop::removeFromStmtMap ( ScopStmt & Stmt )

private

Removes Stmt from the StmtMap.

Definition at line 1634 of file ScopInfo.cpp.

References polly::ScopStmt::getBasicBlock(), polly::ScopStmt::getEntryBlock(), polly::ScopStmt::getInstructions(), polly::ScopStmt::getRegion(), InstStmtMap, polly::ScopStmt::isRegionStmt(), and StmtMap.

Referenced by removeStmts().

◆ removeStmtNotInDomainMap()

void Scop::removeStmtNotInDomainMap ( )

private

Removes all statements where the entry block of the statement does not have a corresponding domain in the domain map (or it is empty).

Definition at line 1677 of file ScopInfo.cpp.

References Domain, DomainMap, polly::ScopStmt::getEntryBlock(), if(), and removeStmts().

◆ removeStmts()

void Scop::removeStmts	(	function_ref< bool(ScopStmt &)>	ShouldDelete,
		bool	AfterHoisting = `true`
	)

Remove statements from the list of scop statements.

Parameters

ShouldDelete	A function that returns true if the statement passed to it should be deleted.
AfterHoisting	If true, also remove from data access lists. These lists are filled during ScopBuilder::buildAccessRelations. Therefore, if this method is called before buildAccessRelations, false must be passed.

Definition at line 1657 of file ScopInfo.cpp.

References removeFromStmtMap(), and Stmts.

Referenced by removeStmtNotInDomainMap(), and simplifySCoP().

◆ rend() [1/2]

reverse_iterator polly::Scop::rend ( )

inline

Definition at line 2359 of file ScopInfo.h.

References Stmts.

◆ rend() [2/2]

const_reverse_iterator polly::Scop::rend ( ) const

inline

Definition at line 2361 of file ScopInfo.h.

References Stmts.

◆ restrictDomains()

bool Scop::restrictDomains ( isl::union_set Domain )

Intersects the domains of all statements in the SCoP.

Returns: true if a change was made

Definition at line 2273 of file ScopInfo.cpp.

References isl::union_set::coalesce(), Domain, isl::set::empty(), polly::ScopStmt::getDomain(), polly::ScopStmt::getDomainSpace(), isl::union_set::intersect(), isl::union_set::is_empty(), isl::union_set::is_subset(), and polly::ScopStmt::restrictDomain().

◆ setContext()

void Scop::setContext ( isl::set NewContext )

Set new isl context.

Scop class implement.

Definition at line 1356 of file ScopInfo.cpp.

References isl::set::align_params(), Context, and isl::set::get_space().

◆ setDomain()

void polly::Scop::setDomain	(	BasicBlock *	BB,
		isl::set &	Domain
	)

inline

Set domain for BB.

Definition at line 2524 of file ScopInfo.h.

References Domain, and DomainMap.

◆ setSchedule()

void Scop::setSchedule ( isl::union_map NewSchedule )

Update the current schedule.

NewSchedule The new schedule (given as a flat union-map).

Definition at line 2261 of file ScopInfo.cpp.

References isl::schedule::from_domain(), isl::multi_union_pw_aff::from_union_map(), getDomains(), Schedule, and ScheduleModified.

◆ setScheduleTree()

void Scop::setScheduleTree ( isl::schedule NewSchedule )

Update the current schedule.

NewSchedule The new schedule (given as schedule tree).

Definition at line 2268 of file ScopInfo.cpp.

References Schedule, and ScheduleModified.

◆ simplifyContexts()

void Scop::simplifyContexts ( )

private

Simplify the assumed and invalid context.

Definition at line 1549 of file ScopInfo.cpp.

References isl::set::align_params(), AssumedContext, DefinedBehaviorContext, getParamSpace(), InvalidContext, simplify, and simplifyAssumptionContext().

◆ simplifySCoP()

void Scop::simplifySCoP ( bool AfterHoisting )

Simplify the SCoP representation.

Parameters

AfterHoisting Whether it is called after invariant load hoisting. When true, also removes statements without side-effects.

Definition at line 1686 of file ScopInfo.cpp.

References polly::hasDebugCall(), polly::ScopStmt::isEmpty(), and removeStmts().

◆ trackAssumption()

bool Scop::trackAssumption	(	AssumptionKind	Kind,
		isl::set	Set,
		DebugLoc	Loc,
		AssumptionSign	Sign,
		BasicBlock *	BB
	)

Track and report an assumption.

Use 'clang -Rpass-analysis=polly-scops' or 'opt -pass-remarks-analysis=polly-scops' to output the assumptions.

Parameters

Kind	The assumption kind describing the underlying cause.
Set	The relations between parameters that are assumed to hold.
Loc	The location in the source that caused this assumption.
Sign	Enum to indicate if the assumptions in `Set` are positive (needed/assumptions) or negative (invalid/restrictions).
BB	The block in which this assumption was taken. Used to calculate hotness when emitting remark.

Returns: True if the assumption is not trivial.

Definition at line 1943 of file ScopInfo.cpp.

References polly::ALIASING, polly::AS_ASSUMPTION, polly::AS_RESTRICTION, polly::COMPLEXITY, DEBUG_TYPE, polly::DELINEARIZATION, polly::ERRORBLOCK, isl::set::get_space(), polly::INBOUNDS, polly::INFINITELOOP, polly::INVARIANTLOAD, isl::set::is_empty(), isl::set::is_equal(), isEffectiveAssumption(), ORE, PollyRemarksMinimal(), polly::PROFITABLE, R, toString(), isl::set::universe(), polly::UNSIGNED, and polly::WRAPPING.

Referenced by addAssumption().

◆ updateMaxLoopDepth()

void polly::Scop::updateMaxLoopDepth ( unsigned Depth )

inline

Update maximal loop depth.

If Depth is smaller than current value, then maximal loop depth is not updated.

Definition at line 2436 of file ScopInfo.h.

References MaxLoopDepth.

Friends And Related Function Documentation

◆ ScopBuilder

friend class ScopBuilder

friend

Definition at line 1645 of file ScopInfo.h.

Member Data Documentation

◆ AccessFunctions

AccFuncVector polly::Scop::AccessFunctions

private

Definition at line 1670 of file ScopInfo.h.

Referenced by access_functions(), and addAccessFunction().

◆ Affinator

SCEVAffinator polly::Scop::Affinator

private

The affinator used to translate SCEVs to isl expressions.

Definition at line 1718 of file ScopInfo.h.

Referenced by getLI(), getPwAff(), and hasNSWAddRecForLoop().

◆ ArrayIdx

long polly::Scop::ArrayIdx = 0

private

The smallest array index not yet assigned.

Definition at line 1842 of file ScopInfo.h.

Referenced by getNextArrayIdx().

◆ AssumedContext

isl::set polly::Scop::AssumedContext

private

The assumptions under which this scop was built.

When constructing a scop sometimes the exact representation of a statement or condition would be very complex, but there is a common case which is a lot simpler, but which is only valid under certain assumptions. The assumed context records the assumptions taken during the construction of this scop and that need to be code generated as a run-time test.

Definition at line 1750 of file ScopInfo.h.

Referenced by addAssumption(), buildContext(), getAssumedContext(), getAssumedContextStr(), getBestKnownDefinedBehaviorContext(), isEffectiveAssumption(), printContext(), realignParams(), and simplifyContexts().

◆ Context

isl::set polly::Scop::Context

private

Constraints on parameters.

Definition at line 1715 of file ScopInfo.h.

Referenced by addParameterBounds(), buildContext(), getBestKnownDefinedBehaviorContext(), getContext(), hasFeasibleRuntimeContext(), isEffectiveAssumption(), printContext(), realignParams(), and setContext().

◆ CopyStmtsNum

unsigned polly::Scop::CopyStmtsNum = 0

private

Number of copy statements.

Definition at line 1685 of file ScopInfo.h.

Referenced by addScopStmt(), and getCopyStmtsNum().

◆ DC

ScopDetection::DetectionContext& polly::Scop::DC

private

The context of the SCoP created during SCoP detection.

Definition at line 1699 of file ScopInfo.h.

Referenced by addRequiredInvariantLoad(), getBoxedLoops(), getInsnToMemAccMap(), getRequiredInvariantLoads(), and isNonAffineSubRegion().

◆ DefinedBehaviorContext

isl::set polly::Scop::DefinedBehaviorContext

private

The context under which the SCoP must have defined behavior.

Optimizer and code generator can assume that the SCoP will only be executed with parameter values within this context. This might be either because we can prove that other values are impossible or explicitly have undefined behavior, such as due to no-wrap flags. If this becomes too complex, can also be nullptr.

In contrast to Scop::AssumedContext and Scop::InvalidContext, these do not need to be checked at runtime.

Scop::Context on the other side is an overapproximation and does not include all requirements, but is always defined. However, there is still no guarantee that there is no undefined behavior in DefinedBehaviorContext.

Definition at line 1774 of file ScopInfo.h.

Referenced by buildContext(), getBestKnownDefinedBehaviorContext(), getDefinedBehaviorContext(), intersectDefinedBehavior(), printContext(), and simplifyContexts().

◆ DomainMap

DenseMap<BasicBlock *, isl::set> polly::Scop::DomainMap

private

A map from basic blocks to their domains.

Definition at line 1712 of file ScopInfo.h.

Referenced by getDomainConditions(), getOrInitEmptyDomain(), isDomainDefined(), removeStmtNotInDomainMap(), and setDomain().

◆ DT

DominatorTree* polly::Scop::DT

private

Definition at line 1659 of file ScopInfo.h.

Referenced by getDT(), and isDominatedBy().

◆ HasDisableHeuristicsHint

bool polly::Scop::HasDisableHeuristicsHint = false

private

Is this Scop marked as not to be transformed by an optimization heuristic?

Definition at line 1813 of file ScopInfo.h.

Referenced by hasDisableHeuristicsHint(), and markDisableHeuristics().

◆ HasErrorBlock

bool polly::Scop::HasErrorBlock = false

private

Flag to remember if the SCoP contained an error block or not.

Definition at line 1679 of file ScopInfo.h.

Referenced by hasErrorBlock(), and notifyErrorBlock().

◆ HasSingleExitEdge

bool polly::Scop::HasSingleExitEdge

private

True if the underlying region has a single exiting block.

Definition at line 1676 of file ScopInfo.h.

Referenced by hasSingleExitEdge().

◆ ID

const int polly::Scop::ID

private

A number that uniquely represents a Scop within its function.

Definition at line 1848 of file ScopInfo.h.

Referenced by getID().

◆ InstStmtMap

DenseMap<Instruction *, ScopStmt *> polly::Scop::InstStmtMap

private

A map from instructions to SCoP statements.

Definition at line 1709 of file ScopInfo.h.

Referenced by addScopStmt(), getStmtFor(), and removeFromStmtMap().

◆ InvalidContext

isl::set polly::Scop::InvalidContext

private

The restrictions under which this SCoP was built.

The invalid context is similar to the assumed context as it contains constraints over the parameters. However, while we need the constraints in the assumed context to be "true" the constraints in the invalid context need to be "false". Otherwise they behave the same.

Definition at line 1758 of file ScopInfo.h.

Referenced by addAssumption(), buildContext(), getBestKnownDefinedBehaviorContext(), getInvalidContext(), getInvalidContextStr(), hasTrivialInvalidContext(), isEffectiveAssumption(), printContext(), realignParams(), and simplifyContexts().

◆ InvariantEquivClasses

InvariantEquivClassesTy polly::Scop::InvariantEquivClasses

private

List of invariant accesses.

Definition at line 1839 of file ScopInfo.h.

Referenced by addInvariantEquivClass(), getInvariantAccesses(), hasInvariantAccesses(), invariantEquivClasses(), lookupInvariantEquivClass(), and print().

◆ InvEquivClassVMap

ValueToValueMap polly::Scop::InvEquivClassVMap

private

Mapping from invariant loads to the representing invariant load of their equivalence class.

Definition at line 1836 of file ScopInfo.h.

Referenced by addInvariantLoadMapping(), getRepresentingInvariantLoadSCEV(), and lookupInvariantEquivClass().

◆ IslCtx

std::shared_ptr<isl_ctx> polly::Scop::IslCtx

private

Isl context.

We need a shared_ptr with reference counter to delete the context when all isl objects are deleted. We will distribute the shared_ptr to all objects that use the context to create isl objects, and increase the reference counter. By doing this, we guarantee that the context is deleted when we delete the last object that creates isl objects with the context. This declaration needs to be the first in class to gracefully destroy all isl objects before the context.

Definition at line 1656 of file ScopInfo.h.

Referenced by getIslCtx(), getSharedIslCtx(), and Scop().

◆ IsOptimized

bool polly::Scop::IsOptimized = false

private

Flag to indicate that the scheduler actually optimized the SCoP.

Definition at line 1673 of file ScopInfo.h.

Referenced by isOptimized(), and markAsOptimized().

◆ MaxLoopDepth

unsigned polly::Scop::MaxLoopDepth = 0

private

Max loop depth.

Definition at line 1682 of file ScopInfo.h.

Referenced by getMaxLoopDepth(), and updateMaxLoopDepth().

◆ MinMaxAliasGroups

MinMaxVectorPairVectorTy polly::Scop::MinMaxAliasGroups

private

The set of minimal/maximal accesses for each alias group.

When building runtime alias checks we look at all memory instructions and build so called alias groups. Each group contains a set of accesses to different base arrays which might alias with each other. However, between alias groups there is no aliasing possible.

In a program with int and float pointers annotated with tbaa information we would probably generate two alias groups, one for the int pointers and one for the float pointers.

During code generation we will create a runtime alias check for each alias group to ensure the SCoP is executed in an alias free environment.

Definition at line 1832 of file ScopInfo.h.

Referenced by addAliasGroup(), getAliasGroups(), and printAliasAssumptions().

◆ name

std::optional<std::string> polly::Scop::name

private

The name of the SCoP (identical to the regions name)

Definition at line 1665 of file ScopInfo.h.

Referenced by getName().

◆ ORE

OptimizationRemarkEmitter& polly::Scop::ORE

private

OptimizationRemarkEmitter object for displaying diagnostic remarks.

Definition at line 1702 of file ScopInfo.h.

Referenced by trackAssumption().

◆ ParameterIds

DenseMap<const SCEV *, isl::id> polly::Scop::ParameterIds

private

Mapping from parameters to their ids.

Definition at line 1696 of file ScopInfo.h.

Referenced by createParameterId(), getFullParamSpace(), and getIdForParam().

◆ Parameters

ParameterSetTy polly::Scop::Parameters

private

Parameters of this Scop.

Definition at line 1693 of file ScopInfo.h.

Referenced by addParameterBounds(), addParams(), createParameterId(), getFullParamSpace(), getNumParams(), isParam(), parameters(), and printContext().

◆ PHIIncomingAccs

DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4> > polly::Scop::PHIIncomingAccs

private

List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or MemoryKind::ExitPHI scalar.

Definition at line 1865 of file ScopInfo.h.

Referenced by addAccessData(), getPHIIncomings(), and removeAccessData().

◆ PHIReadAccs

DenseMap<PHINode *, MemoryAccess *> polly::Scop::PHIReadAccs

private

Map of values to the MemoryAccess that reads a PHI.

Definition at line 1856 of file ScopInfo.h.

Referenced by addAccessFunction(), getPHIRead(), and removeAccessData().

◆ R

Region& polly::Scop::R

private

The underlying Region.

Definition at line 1662 of file ScopInfo.h.

Referenced by addScopStmt(), blocks(), contains(), getDomainConditions(), getEnteringBlock(), getEntry(), getEntryExitStr(), getExit(), getExitingBlock(), getFunction(), getName(), getRegion(), getRelativeLoopDepth(), getStatistics(), getStmtListFor(), isNonAffineSubRegion(), and trackAssumption().

◆ Schedule

isl::schedule polly::Scop::Schedule

private

The schedule of the SCoP.

The schedule of the SCoP describes the execution order of the statements in the scop by assigning each statement instance a possibly multi-dimensional execution time. The schedule is stored as a tree of schedule nodes.

The most common nodes in a schedule tree are so-called band nodes. Band nodes map statement instances into a multi dimensional schedule space. This space can be seen as a multi-dimensional clock.

Example:

<S,(5,4)> may be mapped to (5,4) by this schedule:

s0 = i (Year of execution) s1 = j (Day of execution)

or to (9, 20) by this schedule:

s0 = i + j (Year of execution) s1 = 20 (Day of execution)

The order statement instances are executed is defined by the schedule vectors they are mapped to. A statement instance <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if the schedule vector of A is lexicographic smaller than the schedule vector of B.

Besides band nodes, schedule trees contain additional nodes that specify a textual ordering between two subtrees or filter nodes that filter the set of statement instances that will be scheduled in a subtree. There are also several other nodes. A full description of the different nodes in a schedule tree is given in the isl manual.

Definition at line 1810 of file ScopInfo.h.

Referenced by getScheduleTree(), realignParams(), setSchedule(), and setScheduleTree().

◆ ScheduleModified

bool polly::Scop::ScheduleModified = false

private

Whether the schedule has been modified after derived from the CFG by ScopBuilder.

Definition at line 1817 of file ScopInfo.h.

Referenced by isOriginalSchedule(), setSchedule(), and setScheduleTree().

◆ ScopArrayInfoMap

ArrayInfoMapTy polly::Scop::ScopArrayInfoMap

private

A map to remember ScopArrayInfo objects for all base pointers.

As PHI nodes may have two array info objects associated, we add a flag that distinguishes between the PHI node specific ArrayInfo object and the normal one.

Definition at line 1733 of file ScopInfo.h.

Referenced by getOrCreateScopArrayInfo(), getScopArrayInfoOrNull(), and invalidateScopArrayInfo().

◆ ScopArrayInfoSet

ArrayInfoSetTy polly::Scop::ScopArrayInfoSet

private

A set to remember ScopArrayInfo objects.

See also: Scop::ScopArrayInfoMap

Definition at line 1741 of file ScopInfo.h.

Referenced by array_begin(), array_end(), getOrCreateScopArrayInfo(), and invalidateScopArrayInfo().

◆ ScopArrayNameMap

ArrayNameMapTy polly::Scop::ScopArrayNameMap

private

A map to remember ScopArrayInfo objects for all names of memory references.

Definition at line 1737 of file ScopInfo.h.

Referenced by getOrCreateScopArrayInfo().

◆ SE

ScalarEvolution* polly::Scop::SE

private

Definition at line 1658 of file ScopInfo.h.

Referenced by addParameterBounds(), addParams(), getPwAff(), getRepresentingInvariantLoadSCEV(), getSE(), getStatistics(), and lookupInvariantEquivClass().

◆ StmtIdx

long polly::Scop::StmtIdx = 0

private

The smallest statement index not yet assigned.

Definition at line 1845 of file ScopInfo.h.

Referenced by getNextStmtIdx().

◆ StmtMap

DenseMap<BasicBlock *, std::vector<ScopStmt *> > polly::Scop::StmtMap

private

A map from basic blocks to vector of SCoP statements.

Currently this vector comprises only of a single statement.

Definition at line 1706 of file ScopInfo.h.

Referenced by addScopStmt(), getStmtListFor(), and removeFromStmtMap().

◆ Stmts

StmtSet polly::Scop::Stmts

private

The statements in this Scop.

Definition at line 1690 of file ScopInfo.h.

Referenced by addScopStmt(), begin(), end(), getSize(), hasFeasibleRuntimeContext(), isEmpty(), rbegin(), removeStmts(), and rend().

◆ ValueDefAccs

DenseMap<Value *, MemoryAccess *> polly::Scop::ValueDefAccs

private

Map of values to the MemoryAccess that writes its definition.

There must be at most one definition per llvm::Instruction in a SCoP.

Definition at line 1853 of file ScopInfo.h.

Referenced by addAccessFunction(), getValueDef(), and removeAccessData().

◆ ValueUseAccs

DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4> > polly::Scop::ValueUseAccs

private

List of all uses (i.e.

read MemoryAccesses) for a MemoryKind::Value scalar.

Definition at line 1860 of file ScopInfo.h.

Referenced by addAccessData(), getValueUses(), and removeAccessData().

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

Classes

Public Types

Private Types

Private Member Functions

Private Attributes

Friends

Helper functions for printing the Scop.

Statements Iterators

Detailed Description

Member Typedef Documentation

◆ array_iterator

◆ array_range

◆ ArrayInfoMapTy

◆ ArrayInfoSetTy

◆ ArrayNameMapTy

◆ const_array_iterator

◆ const_array_range

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ MinMaxAccessTy

◆ MinMaxVectorPairTy

◆ MinMaxVectorPairVectorTy

◆ MinMaxVectorTy

◆ reverse_iterator

◆ StmtSet

Constructor & Destructor Documentation

◆ Scop() [1/2]

◆ Scop() [2/2]

◆ ~Scop()

Member Function Documentation

◆ access_functions()

◆ addAccessData()

◆ addAccessFunction()

◆ addAliasGroup()

◆ addAssumption()

◆ addInvariantEquivClass()

◆ addInvariantLoadMapping()

◆ addParameterBounds()

◆ addParams()

◆ addRequiredInvariantLoad()

◆ addScopStmt() [1/3]

◆ addScopStmt() [2/3]

◆ addScopStmt() [3/3]

◆ array_begin() [1/2]

◆ array_begin() [2/2]

◆ array_end() [1/2]

◆ array_end() [2/2]

◆ arrays() [1/2]

◆ arrays() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ blocks()

◆ buildContext()

◆ contains() [1/3]

◆ contains() [2/3]

◆ contains() [3/3]

◆ createParameterId()

◆ createScopArrayInfo()

◆ dump()

◆ end() [1/2]

◆ end() [2/2]

◆ getAccesses() [1/2]

◆ getAccesses() [2/2]

◆ getAccessesOfType()

◆ getAliasGroups()

◆ getArrayInfoByName()

◆ getAssumedContext()

◆ getAssumedContextStr()

◆ getBestKnownDefinedBehaviorContext()

◆ getBoxedLoops()

◆ getContext()

◆ getContextStr()

◆ getCopyStmtsNum()

◆ getDefinedBehaviorContext()

◆ getDomainConditions() [1/2]

◆ getDomainConditions() [2/2]

◆ getDomains()

◆ getDT()

◆ getEnteringBlock()