ScopBuilder.cpp File Reference

#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"

Go to the source code of this file.

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()

static 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().

buildMinMaxAccess()

static 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(), 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()

static 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(), and isl::set::unite().

Referenced by partitionSetParts().

combineInSequence()

static 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()

static 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()

static 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()

static 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()

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

static

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

DisableMultiplicativeReductions()

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

static

Referenced by getReductionType().

findCanonicalArray()

static 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.

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

getAccessDomain()

static 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()

static 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()

static 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()

static 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, isl::set::has_equal_space(), and isl::set::project_out_all_params().

Referenced by checkCandidatePairAccesses().

isAccessRangeTooComplex()

static 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()

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

static

Definition at line 2969 of file ScopBuilder.cpp.

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

isDivisible()

static 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()

static 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()

static 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, and polly::MemoryAccess::getScopArrayInfo().

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

joinOperandTree()

static 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()

static 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()

static 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]

static 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]

static 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()

static 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(), isl::set, and unsignedFromIslSize().

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

OptComputeOut()

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

partitionSetParts()

static 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(), isl::set, and unsignedFromIslSize().

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

PollyAllowDereferenceOfAllFunctionParams()

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

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

PollyIgnoreInbounds()

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

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

replaceBasePtrArrays()

static 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, and isl::map::set_tuple_id().

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

RunTimeChecksMaxAccessDisjuncts()

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

Referenced by buildMinMaxAccess().

RunTimeChecksMaxArraysPerGroup()

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

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

RunTimeChecksMaxParameters()

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

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()

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

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

UnprofitableScalarAccs()

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

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

UserContextStr()

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

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

verifyUse()

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

static

Definition at line 3548 of file ScopBuilder.cpp.

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

Referenced by verifyUses().

verifyUses()

static 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(), polly::VirtualUse::Synthesizable, and verifyUse().

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

XModelReadOnlyScalars()

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

Variable Documentation

MaxDimensionsInAccessRange

unsigned const MaxDimensionsInAccessRange = 9

static

Definition at line 77 of file ScopBuilder.cpp.

Referenced by isAccessRangeTooComplex().