#include "polly/ScopBuilder.h"
#include "polly/Options.h"
#include "polly/ScopDetection.h"
#include "polly/ScopInfo.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"
#include "polly/Support/VirtualInstruction.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include "polly/Support/PollyDebug.h"

Macros
#define	DEBUG_TYPE "polly-scops"

Enumerations
enum class	GranularityChoice { BasicBlocks , ScalarIndependence , Stores }

Functions
	STATISTIC (ScopFound, "Number of valid Scops")
	STATISTIC (RichScopFound, "Number of Scops containing a loop")
	STATISTIC (InfeasibleScops, "Number of SCoPs with statically infeasible context.")
static cl::opt< bool, true >	XModelReadOnlyScalars ("polly-analyze-read-only-scalars", cl::desc("Model read-only scalar values in the scop description"), cl::location(ModelReadOnlyScalars), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< int >	OptComputeOut ("polly-analysis-computeout", cl::desc("Bound the scop analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(800000), cl::cat(PollyCategory))
static cl::opt< bool >	PollyAllowDereferenceOfAllFunctionParams ("polly-allow-dereference-of-all-function-parameters", cl::desc("Treat all parameters to functions that are pointers as dereferencible." " This is useful for invariant load hoisting, since we can generate" " less runtime checks. This is only valid if all pointers to functions" " are always initialized, so that Polly can choose to hoist" " their loads. "), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
static cl::opt< bool >	PollyIgnoreInbounds ("polly-ignore-inbounds", cl::desc("Do not take inbounds assumptions at all"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
static cl::opt< unsigned >	RunTimeChecksMaxArraysPerGroup ("polly-rtc-max-arrays-per-group", cl::desc("The maximal number of arrays to compare in each alias group."), cl::Hidden, cl::init(20), cl::cat(PollyCategory))
static cl::opt< unsigned >	RunTimeChecksMaxAccessDisjuncts ("polly-rtc-max-array-disjuncts", cl::desc("The maximal number of disjunts allowed in memory accesses to " "to build RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory))
static cl::opt< unsigned >	RunTimeChecksMaxParameters ("polly-rtc-max-parameters", cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory))
static cl::opt< bool >	UnprofitableScalarAccs ("polly-unprofitable-scalar-accs", cl::desc("Count statements with scalar accesses as not optimizable"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
static cl::opt< std::string >	UserContextStr ("polly-context", cl::value_desc("isl parameter set"), cl::desc("Provide additional constraints on the context parameters"), cl::init(""), cl::cat(PollyCategory))
static cl::opt< bool >	DetectReductions ("polly-detect-reductions", cl::desc("Detect and exploit reductions"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< bool >	DisableMultiplicativeReductions ("polly-disable-multiplicative-reductions", cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< GranularityChoice >	StmtGranularity ("polly-stmt-granularity", cl::desc("Algorithm to use for splitting basic blocks into multiple statements"), cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb", "One statement per basic block"), clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep", "Scalar independence heuristic"), clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity")), cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory))
static BasicBlock *	getRegionNodeBasicBlock (RegionNode *RN)
	Helper to treat non-affine regions and basic blocks the same.
static BasicBlock *	getRegionNodeSuccessor (RegionNode RN, Instruction TI, unsigned idx)
	Return the `idx'th` block that is executed after `RN`.
static bool	containsErrorBlock (RegionNode RN, const Region &R, ScopDetection SD)
static isl::map	createNextIterationMap (isl::space SetSpace, unsigned Dim)
	}
static isl::set	collectBoundedParts (isl::set S)
	Add `BSet` to set `BoundedParts` if `BSet` is bounded.
static std::pair< isl::set, isl::set >	partitionSetParts (isl::set S, unsigned Dim)
	Compute the (un)bounded parts of `S` wrt.
static isl::set	buildConditionSet (ICmpInst::Predicate Pred, isl::pw_aff L, isl::pw_aff R)
	Create the conditions under which `L` `Pred` `R` is true.
static isl::schedule	combineInSequence (isl::schedule Prev, isl::schedule Succ)
static isl::multi_union_pw_aff	mapToDimension (isl::union_set USet, unsigned N)
static std::string	makeStmtName (BasicBlock *BB, long BBIdx, int Count, bool IsMain, bool IsLast=false)
	Generate a name for a statement.
static std::string	makeStmtName (Region *R, long RIdx)
	Generate a name for a statement that represents a non-affine subregion.
static bool	isOrderedInstruction (Instruction *Inst)
	Is `Inst` an ordered instruction?
static void	joinOperandTree (EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
	Join instructions to the same statement if one uses the scalar result of the other.
static void	joinOrderedInstructions (EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
	Ensure that the order of ordered instructions does not change.
static void	joinOrderedPHIs (EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
	If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for the incoming values from this block are executed after the PHI READ.
static bool	isDivisible (const SCEV *Expr, unsigned Size, ScalarEvolution &SE)
	Check if `Expr` is divisible by `Size`.
static MemoryAccess::ReductionType	getReductionType (const BinaryOperator *BinOp)
	Return the reduction type for a given binary operator.
static MemoryAccess::ReductionType	combineReductionType (MemoryAccess::ReductionType RT0, MemoryAccess::ReductionType RT1)
	Combine two reduction types.
bool	hasIntersectingAccesses (isl::set AllAccs, MemoryAccess LoadMA, MemoryAccess StoreMA, isl::set Domain, SmallVector< MemoryAccess *, 8 > &MemAccs)
	True if `AllAccs` intersects with `MemAccs` except `LoadMA` and `StoreMA`.
bool	checkCandidatePairAccesses (MemoryAccess LoadMA, MemoryAccess StoreMA, isl::set Domain, SmallVector< MemoryAccess *, 8 > &MemAccs)
	Test if the accesses of `LoadMA` and `StoreMA` can form a reduction.
static bool	isAccessRangeTooComplex (isl::set AccessRange)
	Check if an access range is too complex.
static bool	isAParameter (llvm::Value *maybeParam, const Function &F)
static const ScopArrayInfo *	findCanonicalArray (Scop &S, MemoryAccessList &Accesses)
	Find the canonical scop array info object for a set of invariant load hoisted loads.
static bool	isUsedForIndirectHoistedLoad (Scop &S, const ScopArrayInfo *Array)
	Check if `Array` severs as base array in an invariant load.
static void	replaceBasePtrArrays (Scop &S, const ScopArrayInfo Old, const ScopArrayInfo New)
	Replace the base pointer arrays in all memory accesses referencing `Old`, with a reference to `New`.
static bool	buildMinMaxAccess (isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S)
	Add the minimal/maximal access in `Set` to `User`.
static isl::set	getAccessDomain (MemoryAccess *MA)
static void	verifyUse (Scop *S, Use &Op, LoopInfo &LI)
static void	verifyUses (Scop *S, LoopInfo &LI, DominatorTree &DT)
	Check the consistency of every statement's MemoryAccesses.

Variables
static unsigned const	MaxDimensionsInAccessRange = 9

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "polly-scops"

Definition at line 64 of file ScopBuilder.cpp.

Enumeration Type Documentation

◆ GranularityChoice

enum class GranularityChoice

strong

Enumerator
BasicBlocks
ScalarIndependence
Stores

Definition at line 145 of file ScopBuilder.cpp.

Function Documentation

◆ buildConditionSet()

isl::set buildConditionSet	(	ICmpInst::Predicate	Pred,
		isl::pw_aff	L,
		isl::pw_aff	R )

static

Create the conditions under which L Pred R is true.

Definition at line 266 of file ScopBuilder.cpp.

References isl::pw_aff::eq_set(), isl::pw_aff::ge_set(), isl::pw_aff::gt_set(), isl::pw_aff::le_set(), isl::pw_aff::lt_set(), and isl::pw_aff::ne_set().

Referenced by polly::ScopBuilder::buildConditionSets(), and polly::ScopBuilder::buildConditionSets().

◆ buildMinMaxAccess()

bool buildMinMaxAccess	(	isl::set	Set,
		Scop::MinMaxVectorTy &	MinMaxAccesses,
		Scop &	S )

static

Add the minimal/maximal access in Set to User.

Returns: True if more accesses should be added, false if we reached the maximal number of run-time checks to be generated.

Definition at line 3246 of file ScopBuilder.cpp.

References isl::pw_aff::add(), isl::aff::add_constant_si(), assert, isl::pw_multi_aff::at(), isl::pw_multi_aff::coalesce(), isl::pw_multi_aff::dim(), isl::set::get(), isl::pw_aff::get_domain_space(), isl::set::involves_dims(), isl::pw_multi_aff::is_null(), isl_set_n_param(), isl::set::lexmax_pw_multi_aff(), isl::set::lexmin_pw_multi_aff(), isl::set::n_basic_set(), isl::out, isl::param, isl::set::remove_divs(), RunTimeChecksMaxAccessDisjuncts(), RunTimeChecksMaxParameters(), S, isl::pw_multi_aff::set_pw_aff(), isl::set::simple_hull(), polly::simplify(), and unsignedFromIslSize().

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

◆ checkCandidatePairAccesses()

bool checkCandidatePairAccesses	(	MemoryAccess *	LoadMA,
		MemoryAccess *	StoreMA,
		isl::set	Domain,
		SmallVector< MemoryAccess *, 8 > &	MemAccs )

Test if the accesses of LoadMA and StoreMA can form a reduction.

Definition at line 2551 of file ScopBuilder.cpp.

References isl::map::copy(), isl::set::copy(), Domain, polly::MemoryAccess::dump(), polly::MemoryAccess::getAccessRelation(), isl::map::has_equal_space(), hasIntersectingAccesses(), isl::map::intersect_domain(), isl::set::is_empty(), isl::manage(), POLLY_DEBUG, isl::map::range(), and isl::map::unite().

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

◆ collectBoundedParts()

isl::set collectBoundedParts ( isl::set S )

static

Add BSet to set BoundedParts if BSet is bounded.

Definition at line 215 of file ScopBuilder.cpp.

References isl::set::empty(), S, and isl::set::unite().

Referenced by partitionSetParts().

◆ combineInSequence()

isl::schedule combineInSequence	(	isl::schedule	Prev,
		isl::schedule	Succ )

static

Definition at line 1135 of file ScopBuilder.cpp.

References isl::schedule::is_null(), and isl::schedule::sequence().

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

◆ combineReductionType()

MemoryAccess::ReductionType combineReductionType	(	MemoryAccess::ReductionType	RT0,
		MemoryAccess::ReductionType	RT1 )

static

Combine two reduction types.

Definition at line 2515 of file ScopBuilder.cpp.

References polly::MemoryAccess::RT_BOTTOM, and polly::MemoryAccess::RT_NONE.

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

◆ containsErrorBlock()

bool containsErrorBlock	(	RegionNode *	RN,
		const Region &	R,
		ScopDetection *	SD )

static

Definition at line 179 of file ScopBuilder.cpp.

References polly::ScopDetection::isErrorBlock().

Referenced by polly::ScopBuilder::buildDomains(), polly::ScopBuilder::buildDomainsWithBranchConstraints(), and polly::ScopBuilder::propagateInvalidStmtDomains().

◆ createNextIterationMap()

isl::map createNextIterationMap	(	isl::space	SetSpace,
		unsigned	Dim )

static

}

Create a map to map from a given iteration to a subsequent iteration.

This map maps from SetSpace -> SetSpace where the dimensions Dim is incremented by one and all other dimensions are equal, e.g., [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]

if Dim is 2 and SetSpace has 4 dimensions.

Definition at line 198 of file ScopBuilder.cpp.

References isl::map::add_constraint(), isl::constraint::alloc_equality(), C, isl::map::domain_tuple_dim(), isl::map::equate(), isl::in, isl::space::map_from_set(), isl::out, polly::rangeIslSize(), and isl::map::universe().

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

◆ DetectReductions()

cl::opt< bool > DetectReductions	(	"polly-detect-reductions"	,
		cl::desc("Detect and exploit reductions")	,
		cl::Hidden	,
		cl::init(true)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ DisableMultiplicativeReductions()

cl::opt< bool > DisableMultiplicativeReductions	(	"polly-disable-multiplicative-reductions"	,
		cl::desc("Disable multiplicative reductions")	,
		cl::Hidden	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

Referenced by getReductionType().

◆ findCanonicalArray()

const ScopArrayInfo * findCanonicalArray	(	Scop &	S,
		MemoryAccessList &	Accesses )

static

Find the canonical scop array info object for a set of invariant load hoisted loads.

The canonical array is the one that corresponds to the first load in the list of accesses which is used as base pointer of a scop array.

Definition at line 3137 of file ScopBuilder.cpp.

References polly::Array, and S.

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

◆ getAccessDomain()

isl::set getAccessDomain ( MemoryAccess * MA )

static

Definition at line 3340 of file ScopBuilder.cpp.

References Domain, polly::ScopStmt::getDomain(), polly::MemoryAccess::getStatement(), isl::set, and unsignedFromIslSize().

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

◆ getReductionType()

MemoryAccess::ReductionType getReductionType ( const BinaryOperator * BinOp )

static

Return the reduction type for a given binary operator.

Definition at line 2484 of file ScopBuilder.cpp.

References DisableMultiplicativeReductions(), polly::MemoryAccess::RT_ADD, polly::MemoryAccess::RT_BAND, polly::MemoryAccess::RT_BOR, polly::MemoryAccess::RT_BXOR, polly::MemoryAccess::RT_MUL, and polly::MemoryAccess::RT_NONE.

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

◆ getRegionNodeBasicBlock()

BasicBlock * getRegionNodeBasicBlock ( RegionNode * RN )

inlinestatic

Helper to treat non-affine regions and basic blocks the same.

{ Return the block that is the representing block for RN.

Definition at line 164 of file ScopBuilder.cpp.

Referenced by polly::ScopBuilder::buildDomainsWithBranchConstraints(), polly::ScopBuilder::buildScop(), polly::ScopBuilder::propagateDomainConstraints(), and polly::ScopBuilder::propagateInvalidStmtDomains().

◆ getRegionNodeSuccessor()

BasicBlock * getRegionNodeSuccessor	(	RegionNode *	RN,
		Instruction *	TI,
		unsigned	idx )

inlinestatic

Return the idx'th block that is executed after RN.

Definition at line 171 of file ScopBuilder.cpp.

References assert.

Referenced by polly::ScopBuilder::buildDomainsWithBranchConstraints(), and polly::ScopBuilder::propagateInvalidStmtDomains().

◆ hasIntersectingAccesses()

bool hasIntersectingAccesses	(	isl::set	AllAccs,
		MemoryAccess *	LoadMA,
		MemoryAccess *	StoreMA,
		isl::set	Domain,
		SmallVector< MemoryAccess *, 8 > &	MemAccs )

True if AllAccs intersects with MemAccs except LoadMA and StoreMA.

Definition at line 2526 of file ScopBuilder.cpp.

References Domain, and isl::set::project_out_all_params().

Referenced by checkCandidatePairAccesses().

◆ isAccessRangeTooComplex()

bool isAccessRangeTooComplex ( isl::set AccessRange )

static

Check if an access range is too complex.

An access range is too complex, if it contains either many disjuncts or very complex expressions. As a simple heuristic, we assume if a set to be too complex if the sum of existentially quantified dimensions and set dimensions is larger than a threshold. This reliably detects both sets with many disjuncts as well as sets with many divisions as they arise in h264.

Parameters

AccessRange The range to check for complexity.

Returns: True if the access range is too complex.

Definition at line 2830 of file ScopBuilder.cpp.

References isl::div, isl::set::get_basic_set_list(), MaxDimensionsInAccessRange, isl::set, and unsignedFromIslSize().

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

◆ isAParameter()

bool isAParameter	(	llvm::Value *	maybeParam,
		const Function &	F )

static

Definition at line 2969 of file ScopBuilder.cpp.

References Function.

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

◆ isDivisible()

bool isDivisible	(	const SCEV *	Expr,
		unsigned	Size,
		ScalarEvolution &	SE )

static

Check if Expr is divisible by Size.

Definition at line 2164 of file ScopBuilder.cpp.

References assert, and isDivisible().

Referenced by isDivisible(), and polly::ScopBuilder::updateAccessDimensionality().

◆ isOrderedInstruction()

bool isOrderedInstruction ( Instruction * Inst )

static

Is Inst an ordered instruction?

An unordered instruction is an instruction, such that a sequence of unordered instructions can be permuted without changing semantics. Any instruction for which this is not always the case is ordered.

Definition at line 1841 of file ScopBuilder.cpp.

Referenced by polly::ScopBuilder::buildEqivClassBlockStmts(), and joinOrderedInstructions().

◆ isUsedForIndirectHoistedLoad()

bool isUsedForIndirectHoistedLoad	(	Scop &	S,
		const ScopArrayInfo *	Array )

static

Check if Array severs as base array in an invariant load.

Definition at line 3149 of file ScopBuilder.cpp.

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

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

◆ joinOperandTree()

void joinOperandTree	(	EquivalenceClasses< Instruction * > &	UnionFind,
		ArrayRef< Instruction * >	ModeledInsts )

static

Join instructions to the same statement if one uses the scalar result of the other.

Definition at line 1847 of file ScopBuilder.cpp.

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

◆ joinOrderedInstructions()

void joinOrderedInstructions	(	EquivalenceClasses< Instruction * > &	UnionFind,
		ArrayRef< Instruction * >	ModeledInsts )

static

Ensure that the order of ordered instructions does not change.

If we encounter an ordered instruction enclosed in instructions belonging to a different statement (which might as well contain ordered instructions, but this is not tested here), join them.

Definition at line 1873 of file ScopBuilder.cpp.

References isOrderedInstruction().

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

◆ joinOrderedPHIs()

void joinOrderedPHIs	(	EquivalenceClasses< Instruction * > &	UnionFind,
		ArrayRef< Instruction * >	ModeledInsts )

static

If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for the incoming values from this block are executed after the PHI READ.

Otherwise it could overwrite the incoming value from before the BB with the value for the next execution. This can happen if the PHI WRITE is added to the statement with the instruction that defines the incoming value (instead of the last statement of the same BB). To ensure that the PHI READ and WRITE are in order, we put both into the statement. PHI WRITEs are always executed after PHI READs when they are in the same statement.

TODO: This is an overpessimization. We only have to ensure that the PHI WRITE is not put into a statement containing the PHI itself. That could also be done by

having all (strongly connected) PHIs in a single statement,
unite only the PHIs in the operand tree of the PHI WRITE (because it only has a chance of being lifted before a PHI by being in a statement with a PHI that comes before in the basic block), or
when uniting statements, ensure that no (relevant) PHIs are overtaken.

Definition at line 1924 of file ScopBuilder.cpp.

References polly::PHI.

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

◆ makeStmtName() [1/2]

std::string makeStmtName	(	BasicBlock *	BB,
		long	BBIdx,
		int	Count,
		bool	IsMain,
		bool	IsLast = false )

static

Generate a name for a statement.

Parameters

BB	The basic block the statement will represent.
BBIdx	The index of the `BB` relative to other BBs/regions.
Count	The index of the created statement in `BB`.
IsMain	Whether this is the main of all statement for `BB`. If true, no suffix will be added.
IsLast	Uses a special indicator for the last statement of a BB.

Definition at line 1789 of file ScopBuilder.cpp.

References polly::getIslCompatibleName(), and polly::UseInstructionNames.

Referenced by polly::ScopBuilder::buildEqivClassBlockStmts(), polly::ScopBuilder::buildSequentialBlockStmts(), and polly::ScopBuilder::buildStmts().

◆ makeStmtName() [2/2]

std::string makeStmtName	(	Region *	R,
		long	RIdx )

static

Generate a name for a statement that represents a non-affine subregion.

Parameters

R	The region the statement will represent.
RIdx	The index of the `R` relative to other BBs/regions.

Definition at line 1809 of file ScopBuilder.cpp.

References polly::getIslCompatibleName(), and polly::UseInstructionNames.

◆ mapToDimension()

isl::multi_union_pw_aff mapToDimension	(	isl::union_set	USet,
		unsigned	N )

static

Definition at line 1158 of file ScopBuilder.cpp.

References assert, isl::union_pw_multi_aff::empty(), isl::union_set::get_set_list(), isl::union_set::get_space(), isl::union_set::is_empty(), isl::union_set::is_null(), N(), isl::out, isl::pw_multi_aff::project_out_map(), S, isl::set, and unsignedFromIslSize().

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

◆ OptComputeOut()

cl::opt< int > OptComputeOut	(	"polly-analysis-computeout"	,
		cl::desc("Bound the scop analysis by a maximal amount of " "computational steps (0 means no bound)")	,
		cl::Hidden	,
		cl::init(800000)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

◆ partitionSetParts()

std::pair< isl::set, isl::set > partitionSetParts	(	isl::set	S,
		unsigned	Dim )

static

Compute the (un)bounded parts of S wrt.

to dimension Dim.

Returns: A separation of S into first an unbounded then a bounded subset, both with regards to the dimension Dim.

Definition at line 227 of file ScopBuilder.cpp.

References isl::set::add_constraint(), isl::constraint::alloc_inequality(), assert, C, collectBoundedParts(), isl::set::get_space(), isl::set::insert_dims(), isl::param, isl::set::project_out(), polly::rangeIslSize(), isl::set::remove_dims(), S, isl::set, and unsignedFromIslSize().

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

◆ PollyAllowDereferenceOfAllFunctionParams()

cl::opt< bool > PollyAllowDereferenceOfAllFunctionParams	(	"polly-allow-dereference-of-all-function-parameters"	,
		cl::desc("Treat all parameters to functions that are pointers as dereferencible." " This is useful for invariant load hoisting, since we can generate" " less runtime checks. This is only valid if all pointers to functions" " are always initialized, so that Polly can choose to hoist" " their loads. ")	,
		cl::Hidden	,
		cl::init(false)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ PollyIgnoreInbounds()

cl::opt< bool > PollyIgnoreInbounds	(	"polly-ignore-inbounds"	,
		cl::desc("Do not take inbounds assumptions at all")	,
		cl::Hidden	,
		cl::init(false)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ replaceBasePtrArrays()

void replaceBasePtrArrays	(	Scop &	S,
		const ScopArrayInfo *	Old,
		const ScopArrayInfo *	New )

static

Replace the base pointer arrays in all memory accesses referencing Old, with a reference to New.

Definition at line 3159 of file ScopBuilder.cpp.

References polly::ScopArrayInfo::getBasePtrId(), isl::out, S, and isl::map::set_tuple_id().

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

◆ RunTimeChecksMaxAccessDisjuncts()

cl::opt< unsigned > RunTimeChecksMaxAccessDisjuncts	(	"polly-rtc-max-array-disjuncts"	,
		cl::desc("The maximal number of disjunts allowed in memory accesses to " "to build RTCs.")	,
		cl::Hidden	,
		cl::init(8)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

Referenced by buildMinMaxAccess().

◆ RunTimeChecksMaxArraysPerGroup()

cl::opt< unsigned > RunTimeChecksMaxArraysPerGroup	(	"polly-rtc-max-arrays-per-group"	,
		cl::desc("The maximal number of arrays to compare in each alias group.")	,
		cl::Hidden	,
		cl::init(20)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ RunTimeChecksMaxParameters()

cl::opt< unsigned > RunTimeChecksMaxParameters	(	"polly-rtc-max-parameters"	,
		cl::desc("The maximal number of parameters allowed in RTCs.")	,
		cl::Hidden	,
		cl::init(8)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

Referenced by buildMinMaxAccess().

◆ STATISTIC() [1/3]

STATISTIC	(	InfeasibleScops	,
		"Number of SCoPs with statically infeasible context."	)

◆ STATISTIC() [2/3]

STATISTIC	(	RichScopFound	,
		"Number of Scops containing a loop"	)

◆ STATISTIC() [3/3]

STATISTIC	(	ScopFound	,
		"Number of valid Scops"	)

◆ StmtGranularity()

cl::opt< GranularityChoice > StmtGranularity	(	"polly-stmt-granularity"	,
		cl::desc("Algorithm to use for splitting basic blocks into multiple statements")	,
		cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb", "One statement per basic block"), clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep", "Scalar independence heuristic"), clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity"))	,
		cl::init(GranularityChoice::ScalarIndependence)	,
		cl::cat(PollyCategory)	)

static

References BasicBlocks, PollyCategory, ScalarIndependence, and Stores.

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

◆ UnprofitableScalarAccs()

cl::opt< bool > UnprofitableScalarAccs	(	"polly-unprofitable-scalar-accs"	,
		cl::desc("Count statements with scalar accesses as not optimizable")	,
		cl::Hidden	,
		cl::init(false)	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ UserContextStr()

cl::opt< std::string > UserContextStr	(	"polly-context"	,
		cl::value_desc("isl parameter set")	,
		cl::desc("Provide additional constraints on the context parameters")	,
		cl::init("")	,
		cl::cat(PollyCategory)	)

static

References PollyCategory.

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

◆ verifyUse()

void verifyUse	(	Scop *	S,
		Use &	Op,
		LoopInfo &	LI )

static

Definition at line 3548 of file ScopBuilder.cpp.

References assert, polly::VirtualUse::create(), and S.

Referenced by verifyUses().

◆ verifyUses()

void verifyUses	(	Scop *	S,
		LoopInfo &	LI,
		DominatorTree &	DT )

static

Check the consistency of every statement's MemoryAccesses.

The check is carried out by expecting the "physical" kind of use (derived from the BasicBlocks instructions resides in) to be same as the "virtual" kind of use (derived from a statement's MemoryAccess).

The "physical" uses are taken by ensureValueRead to determine whether to create MemoryAccesses. When done, the kind of scalar access should be the same no matter which way it was derived.

The MemoryAccesses might be changed by later SCoP-modifying passes and hence can intentionally influence on the kind of uses (not corresponding to the "physical" anymore, hence called "virtual"). The CodeGenerator therefore has to pick up the virtual uses. But here in the code generator, this has not happened yet, such that virtual and physical uses are equivalent.

Definition at line 3569 of file ScopBuilder.cpp.

References assert, polly::VirtualUse::create(), polly::VirtualUse::Hoisted, polly::VirtualUse::Intra, polly::isIgnoredIntrinsic(), S, polly::VirtualUse::Synthesizable, and verifyUse().

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

◆ XModelReadOnlyScalars()

cl::opt< bool, true > XModelReadOnlyScalars	(	"polly-analyze-read-only-scalars"	,
		cl::desc("Model read-only scalar values in the scop description")	,
		cl::location(ModelReadOnlyScalars)	,
		cl::Hidden	,
		cl::init(true)	,
		cl::cat(PollyCategory)	)

static

References polly::ModelReadOnlyScalars, and PollyCategory.

Variable Documentation

◆ MaxDimensionsInAccessRange

unsigned const MaxDimensionsInAccessRange = 9

static

Definition at line 77 of file ScopBuilder.cpp.

Referenced by isAccessRangeTooComplex().

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ GranularityChoice

Function Documentation

◆ buildConditionSet()

◆ buildMinMaxAccess()

◆ checkCandidatePairAccesses()

◆ collectBoundedParts()

◆ combineInSequence()

◆ combineReductionType()

◆ containsErrorBlock()

◆ createNextIterationMap()

◆ DetectReductions()

◆ DisableMultiplicativeReductions()

◆ findCanonicalArray()

◆ getAccessDomain()

◆ getReductionType()

◆ getRegionNodeBasicBlock()

◆ getRegionNodeSuccessor()

◆ hasIntersectingAccesses()

◆ isAccessRangeTooComplex()

◆ isAParameter()

◆ isDivisible()

◆ isOrderedInstruction()

◆ isUsedForIndirectHoistedLoad()

◆ joinOperandTree()

◆ joinOrderedInstructions()

◆ joinOrderedPHIs()

◆ makeStmtName() [1/2]

◆ makeStmtName() [2/2]

◆ mapToDimension()

◆ OptComputeOut()

◆ partitionSetParts()

◆ PollyAllowDereferenceOfAllFunctionParams()

◆ PollyIgnoreInbounds()

◆ replaceBasePtrArrays()

◆ RunTimeChecksMaxAccessDisjuncts()

◆ RunTimeChecksMaxArraysPerGroup()

◆ RunTimeChecksMaxParameters()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

◆ StmtGranularity()

◆ UnprofitableScalarAccs()

◆ UserContextStr()

◆ verifyUse()

◆ verifyUses()

◆ XModelReadOnlyScalars()

Variable Documentation

◆ MaxDimensionsInAccessRange