/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp

Bug Summary

File:	polly/lib/Analysis/ScopInfo.cpp
Location:	line 1191, column 5
Description:	Value stored to 'Ty' is never read

Annotated Source Code

1	//===--------- ScopInfo.cpp - Create Scops from LLVM IR ------------------===//
2	//
3	// The LLVM Compiler Infrastructure
4	//
5	// This file is distributed under the University of Illinois Open Source
6	// License. See LICENSE.TXT for details.
7	//
8	//===----------------------------------------------------------------------===//
9	//
10	// Create a polyhedral description for a static control flow region.
11	//
12	// The pass creates a polyhedral description of the Scops detected by the Scop
13	// detection derived from their LLVM-IR code.
14	//
15	// This representation is shared among several tools in the polyhedral
16	// community, which are e.g. Cloog, Pluto, Loopo, Graphite.
17	//
18	//===----------------------------------------------------------------------===//
19
20	#include "polly/ScopInfo.h"
21	#include "polly/LinkAllPasses.h"
22	#include "polly/Options.h"
23	#include "polly/Support/GICHelper.h"
24	#include "polly/Support/SCEVValidator.h"
25	#include "polly/Support/ScopHelper.h"
26	#include "llvm/ADT/DepthFirstIterator.h"
27	#include "llvm/ADT/MapVector.h"
28	#include "llvm/ADT/PostOrderIterator.h"
29	#include "llvm/ADT/STLExtras.h"
30	#include "llvm/ADT/SetVector.h"
31	#include "llvm/ADT/Statistic.h"
32	#include "llvm/ADT/StringExtras.h"
33	#include "llvm/Analysis/AliasAnalysis.h"
34	#include "llvm/Analysis/AssumptionCache.h"
35	#include "llvm/Analysis/LoopInfo.h"
36	#include "llvm/Analysis/LoopIterator.h"
37	#include "llvm/Analysis/RegionIterator.h"
38	#include "llvm/Analysis/ScalarEvolutionExpressions.h"
39	#include "llvm/IR/DiagnosticInfo.h"
40	#include "llvm/Support/Debug.h"
41	#include "isl/aff.h"
42	#include "isl/constraint.h"
43	#include "isl/local_space.h"
44	#include "isl/map.h"
45	#include "isl/options.h"
46	#include "isl/printer.h"
47	#include "isl/schedule.h"
48	#include "isl/schedule_node.h"
49	#include "isl/set.h"
50	#include "isl/union_map.h"
51	#include "isl/union_set.h"
52	#include "isl/val.h"
53	#include <sstream>
54	#include <string>
55	#include <vector>
56
57	using namespace llvm;
58	using namespace polly;
59
60	#define DEBUG_TYPE"polly-scops" "polly-scops"
61
62	STATISTIC(ScopFound, "Number of valid Scops")static llvm::Statistic ScopFound = { "polly-scops", "Number of valid Scops" , 0, 0 };
63	STATISTIC(RichScopFound, "Number of Scops containing a loop")static llvm::Statistic RichScopFound = { "polly-scops", "Number of Scops containing a loop" , 0, 0 };
64
65	// The maximal number of basic sets we allow during domain construction to
66	// be created. More complex scops will result in very high compile time and
67	// are also unlikely to result in good code
68	static int const MaxConjunctsInDomain = 20;
69
70	static cl::opt<bool> ModelReadOnlyScalars(
71	"polly-analyze-read-only-scalars",
72	cl::desc("Model read-only scalar values in the scop description"),
73	cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
74
75	// Multiplicative reductions can be disabled separately as these kind of
76	// operations can overflow easily. Additive reductions and bit operations
77	// are in contrast pretty stable.
78	static cl::opt<bool> DisableMultiplicativeReductions(
79	"polly-disable-multiplicative-reductions",
80	cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
81	cl::init(false), cl::cat(PollyCategory));
82
83	static cl::opt<unsigned> RunTimeChecksMaxParameters(
84	"polly-rtc-max-parameters",
85	cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
86	cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
87
88	static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
89	"polly-rtc-max-arrays-per-group",
90	cl::desc("The maximal number of arrays to compare in each alias group."),
91	cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
92	static cl::opt<std::string> UserContextStr(
93	"polly-context", cl::value_desc("isl parameter set"),
94	cl::desc("Provide additional constraints on the context parameters"),
95	cl::init(""), cl::cat(PollyCategory));
96
97	static cl::opt<bool> DetectReductions("polly-detect-reductions",
98	cl::desc("Detect and exploit reductions"),
99	cl::Hidden, cl::ZeroOrMore,
100	cl::init(true), cl::cat(PollyCategory));
101
102	static cl::opt<int> MaxDisjunctsAssumed(
103	"polly-max-disjuncts-assumed",
104	cl::desc("The maximal number of disjuncts we allow in the assumption "
105	"context (this bounds compile time)"),
106	cl::Hidden, cl::ZeroOrMore, cl::init(150), cl::cat(PollyCategory));
107
108	static cl::opt<bool> IgnoreIntegerWrapping(
109	"polly-ignore-integer-wrapping",
110	cl::desc("Do not build run-time checks to proof absence of integer "
111	"wrapping"),
112	cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
113
114	//===----------------------------------------------------------------------===//
115
116	// Create a sequence of two schedules. Either argument may be null and is
117	// interpreted as the empty schedule. Can also return null if both schedules are
118	// empty.
119	static __isl_give isl_schedule *
120	combineInSequence(__isl_take isl_schedule *Prev,
121	__isl_take isl_schedule *Succ) {
122	if (!Prev)
123	return Succ;
124	if (!Succ)
125	return Prev;
126
127	return isl_schedule_sequence(Prev, Succ);
128	}
129
130	static __isl_give isl_set addRangeBoundsToSet(__isl_take isl_set S,
131	const ConstantRange &Range,
132	int dim,
133	enum isl_dim_type type) {
134	isl_val *V;
135	isl_ctx *ctx = isl_set_get_ctx(S);
136
137	bool useLowerUpperBound = Range.isSignWrappedSet() && !Range.isFullSet();
138	const auto LB = useLowerUpperBound ? Range.getLower() : Range.getSignedMin();
139	V = isl_valFromAPInt(ctx, LB, true);
140	isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V);
141
142	const auto UB = useLowerUpperBound ? Range.getUpper() : Range.getSignedMax();
143	V = isl_valFromAPInt(ctx, UB, true);
144	if (useLowerUpperBound)
145	V = isl_val_sub_ui(V, 1);
146	isl_set *SUB = isl_set_upper_bound_val(S, type, dim, V);
147
148	if (useLowerUpperBound)
149	return isl_set_union(SLB, SUB);
150	else
151	return isl_set_intersect(SLB, SUB);
152	}
153
154	static const ScopArrayInfo identifyBasePtrOriginSAI(Scop S, Value *BasePtr) {
155	LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
156	if (!BasePtrLI)
157	return nullptr;
158
159	if (!S->getRegion().contains(BasePtrLI))
160	return nullptr;
161
162	ScalarEvolution &SE = *S->getSE();
163
164	auto *OriginBaseSCEV =
165	SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
166	if (!OriginBaseSCEV)
167	return nullptr;
168
169	auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
170	if (!OriginBaseSCEVUnknown)
171	return nullptr;
172
173	return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
174	ScopArrayInfo::MK_Array);
175	}
176
177	ScopArrayInfo::ScopArrayInfo(Value BasePtr, Type ElementType, isl_ctx *Ctx,
178	ArrayRef<const SCEV *> Sizes, enum MemoryKind Kind,
179	const DataLayout &DL, Scop *S)
180	: BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
181	std::string BasePtrName =
182	getIslCompatibleName("MemRef_", BasePtr, Kind == MK_PHI ? "__phi" : "");
183	Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
184
185	updateSizes(Sizes);
186	BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
187	if (BasePtrOriginSAI)
188	const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
189	}
190
191	__isl_give isl_space *ScopArrayInfo::getSpace() const {
192	auto Space =
193	isl_space_set_alloc(isl_id_get_ctx(Id), 0, getNumberOfDimensions());
194	Space = isl_space_set_tuple_id(Space, isl_dim_set, isl_id_copy(Id));
195	return Space;
196	}
197
198	bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) {
199	int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
200	int ExtraDimsNew = NewSizes.size() - SharedDims;
201	int ExtraDimsOld = DimensionSizes.size() - SharedDims;
202	for (int i = 0; i < SharedDims; i++)
203	if (NewSizes[i + ExtraDimsNew] != DimensionSizes[i + ExtraDimsOld])
204	return false;
205
206	if (DimensionSizes.size() >= NewSizes.size())
207	return true;
208
209	DimensionSizes.clear();
210	DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
211	NewSizes.end());
212	for (isl_pw_aff *Size : DimensionSizesPw)
213	isl_pw_aff_free(Size);
214	DimensionSizesPw.clear();
215	for (const SCEV *Expr : DimensionSizes) {
216	isl_pw_aff *Size = S.getPwAff(Expr);
217	DimensionSizesPw.push_back(Size);
218	}
219	return true;
220	}
221
222	ScopArrayInfo::~ScopArrayInfo() {
223	isl_id_free(Id);
224	for (isl_pw_aff *Size : DimensionSizesPw)
225	isl_pw_aff_free(Size);
226	}
227
228	std::string ScopArrayInfo::getName() const { return isl_id_get_name(Id); }
229
230	int ScopArrayInfo::getElemSizeInBytes() const {
231	return DL.getTypeAllocSize(ElementType);
232	}
233
234	isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); }
235
236	void ScopArrayInfo::dump() const { print(errs()); }
237
238	void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
239	OS.indent(8) << *getElementType() << " " << getName();
240	if (getNumberOfDimensions() > 0)
241	OS << "[*]";
242	for (unsigned u = 1; u < getNumberOfDimensions(); u++) {
243	OS << "[";
244
245	if (SizeAsPwAff) {
246	auto Size = getDimensionSizePw(u);
247	OS << " " << Size << " ";
248	isl_pw_aff_free(Size);
249	} else {
250	OS << *getDimensionSize(u);
251	}
252
253	OS << "]";
254	}
255
256	OS << ";";
257
258	if (BasePtrOriginSAI)
259	OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
260
261	OS << " // Element size " << getElemSizeInBytes() << "\n";
262	}
263
264	const ScopArrayInfo *
265	ScopArrayInfo::getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA) {
266	isl_id *Id = isl_pw_multi_aff_get_tuple_id(PMA, isl_dim_out);
267	assert(Id && "Output dimension didn't have an ID")((Id && "Output dimension didn't have an ID") ? static_cast <void> (0) : __assert_fail ("Id && \"Output dimension didn't have an ID\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 267, __PRETTY_FUNCTION__));
268	return getFromId(Id);
269	}
270
271	const ScopArrayInfo ScopArrayInfo::getFromId(isl_id Id) {
272	void *User = isl_id_get_user(Id);
273	const ScopArrayInfo SAI = static_cast<ScopArrayInfo >(User);
274	isl_id_free(Id);
275	return SAI;
276	}
277
278	void MemoryAccess::updateDimensionality() {
279	auto ArraySpace = getScopArrayInfo()->getSpace();
280	auto AccessSpace = isl_space_range(isl_map_get_space(AccessRelation));
281
282	auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set);
283	auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
284	auto DimsMissing = DimsArray - DimsAccess;
285
286	auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace),
287	isl_set_universe(ArraySpace));
288
289	for (unsigned i = 0; i < DimsMissing; i++)
290	Map = isl_map_fix_si(Map, isl_dim_out, i, 0);
291
292	for (unsigned i = DimsMissing; i < DimsArray; i++)
293	Map = isl_map_equate(Map, isl_dim_in, i - DimsMissing, isl_dim_out, i);
294
295	AccessRelation = isl_map_apply_range(AccessRelation, Map);
296
297	assumeNoOutOfBound();
298	}
299
300	const std::string
301	MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
302	switch (RT) {
303	case MemoryAccess::RT_NONE:
304	llvm_unreachable("Requested a reduction operator string for a memory "::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory " "access which isn't a reduction", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 305)
305	"access which isn't a reduction")::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory " "access which isn't a reduction", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 305);
306	case MemoryAccess::RT_ADD:
307	return "+";
308	case MemoryAccess::RT_MUL:
309	return "*";
310	case MemoryAccess::RT_BOR:
311	return "\|";
312	case MemoryAccess::RT_BXOR:
313	return "^";
314	case MemoryAccess::RT_BAND:
315	return "&";
316	}
317	llvm_unreachable("Unknown reduction type")::llvm::llvm_unreachable_internal("Unknown reduction type", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 317);
318	return "";
319	}
320
321	/// @brief Return the reduction type for a given binary operator
322	static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
323	const Instruction *Load) {
324	if (!BinOp)
325	return MemoryAccess::RT_NONE;
326	switch (BinOp->getOpcode()) {
327	case Instruction::FAdd:
328	if (!BinOp->hasUnsafeAlgebra())
329	return MemoryAccess::RT_NONE;
330	// Fall through
331	case Instruction::Add:
332	return MemoryAccess::RT_ADD;
333	case Instruction::Or:
334	return MemoryAccess::RT_BOR;
335	case Instruction::Xor:
336	return MemoryAccess::RT_BXOR;
337	case Instruction::And:
338	return MemoryAccess::RT_BAND;
339	case Instruction::FMul:
340	if (!BinOp->hasUnsafeAlgebra())
341	return MemoryAccess::RT_NONE;
342	// Fall through
343	case Instruction::Mul:
344	if (DisableMultiplicativeReductions)
345	return MemoryAccess::RT_NONE;
346	return MemoryAccess::RT_MUL;
347	default:
348	return MemoryAccess::RT_NONE;
349	}
350	}
351
352	/// @brief Derive the individual index expressions from a GEP instruction
353	///
354	/// This function optimistically assumes the GEP references into a fixed size
355	/// array. If this is actually true, this function returns a list of array
356	/// subscript expressions as SCEV as well as a list of integers describing
357	/// the size of the individual array dimensions. Both lists have either equal
358	/// length of the size list is one element shorter in case there is no known
359	/// size available for the outermost array dimension.
360	///
361	/// @param GEP The GetElementPtr instruction to analyze.
362	///
363	/// @return A tuple with the subscript expressions and the dimension sizes.
364	static std::tuple<std::vector<const SCEV *>, std::vector<int>>
365	getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
366	std::vector<const SCEV *> Subscripts;
367	std::vector<int> Sizes;
368
369	Type *Ty = GEP->getPointerOperandType();
370
371	bool DroppedFirstDim = false;
372
373	for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
374
375	const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
376
377	if (i == 1) {
378	if (auto PtrTy = dyn_cast<PointerType>(Ty)) {
379	Ty = PtrTy->getElementType();
380	} else if (auto ArrayTy = dyn_cast<ArrayType>(Ty)) {
381	Ty = ArrayTy->getElementType();
382	} else {
383	Subscripts.clear();
384	Sizes.clear();
385	break;
386	}
387	if (auto Const = dyn_cast<SCEVConstant>(Expr))
388	if (Const->getValue()->isZero()) {
389	DroppedFirstDim = true;
390	continue;
391	}
392	Subscripts.push_back(Expr);
393	continue;
394	}
395
396	auto ArrayTy = dyn_cast<ArrayType>(Ty);
397	if (!ArrayTy) {
398	Subscripts.clear();
399	Sizes.clear();
400	break;
401	}
402
403	Subscripts.push_back(Expr);
404	if (!(DroppedFirstDim && i == 2))
405	Sizes.push_back(ArrayTy->getNumElements());
406
407	Ty = ArrayTy->getElementType();
408	}
409
410	return std::make_tuple(Subscripts, Sizes);
411	}
412
413	MemoryAccess::~MemoryAccess() {
414	isl_id_free(Id);
415	isl_map_free(AccessRelation);
416	isl_map_free(NewAccessRelation);
417	}
418
419	const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
420	isl_id *ArrayId = getArrayId();
421	void *User = isl_id_get_user(ArrayId);
422	const ScopArrayInfo SAI = static_cast<ScopArrayInfo >(User);
423	isl_id_free(ArrayId);
424	return SAI;
425	}
426
427	__isl_give isl_id *MemoryAccess::getArrayId() const {
428	return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
429	}
430
431	__isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation(
432	__isl_take isl_union_map *USchedule) const {
433	isl_map Schedule, ScheduledAccRel;
434	isl_union_set *UDomain;
435
436	UDomain = isl_union_set_from_set(getStatement()->getDomain());
437	USchedule = isl_union_map_intersect_domain(USchedule, UDomain);
438	Schedule = isl_map_from_union_map(USchedule);
439	ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule);
440	return isl_pw_multi_aff_from_map(ScheduledAccRel);
441	}
442
443	__isl_give isl_map *MemoryAccess::getOriginalAccessRelation() const {
444	return isl_map_copy(AccessRelation);
445	}
446
447	std::string MemoryAccess::getOriginalAccessRelationStr() const {
448	return stringFromIslObj(AccessRelation);
449	}
450
451	__isl_give isl_space *MemoryAccess::getOriginalAccessRelationSpace() const {
452	return isl_map_get_space(AccessRelation);
453	}
454
455	__isl_give isl_map *MemoryAccess::getNewAccessRelation() const {
456	return isl_map_copy(NewAccessRelation);
457	}
458
459	std::string MemoryAccess::getNewAccessRelationStr() const {
460	return stringFromIslObj(NewAccessRelation);
461	}
462
463	__isl_give isl_basic_map *
464	MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
465	isl_space *Space = isl_space_set_alloc(Statement->getIslCtx(), 0, 1);
466	Space = isl_space_align_params(Space, Statement->getDomainSpace());
467
468	return isl_basic_map_from_domain_and_range(
469	isl_basic_set_universe(Statement->getDomainSpace()),
470	isl_basic_set_universe(Space));
471	}
472
473	// Formalize no out-of-bound access assumption
474	//
475	// When delinearizing array accesses we optimistically assume that the
476	// delinearized accesses do not access out of bound locations (the subscript
477	// expression of each array evaluates for each statement instance that is
478	// executed to a value that is larger than zero and strictly smaller than the
479	// size of the corresponding dimension). The only exception is the outermost
480	// dimension for which we do not need to assume any upper bound. At this point
481	// we formalize this assumption to ensure that at code generation time the
482	// relevant run-time checks can be generated.
483	//
484	// To find the set of constraints necessary to avoid out of bound accesses, we
485	// first build the set of data locations that are not within array bounds. We
486	// then apply the reverse access relation to obtain the set of iterations that
487	// may contain invalid accesses and reduce this set of iterations to the ones
488	// that are actually executed by intersecting them with the domain of the
489	// statement. If we now project out all loop dimensions, we obtain a set of
490	// parameters that may cause statement instances to be executed that may
491	// possibly yield out of bound memory accesses. The complement of these
492	// constraints is the set of constraints that needs to be assumed to ensure such
493	// statement instances are never executed.
494	void MemoryAccess::assumeNoOutOfBound() {
495	isl_space *Space = isl_space_range(getOriginalAccessRelationSpace());
496	isl_set *Outside = isl_set_empty(isl_space_copy(Space));
497	for (int i = 1, Size = isl_space_dim(Space, isl_dim_set); i < Size; ++i) {
498	isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
499	isl_pw_aff *Var =
500	isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
501	isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
502
503	isl_set *DimOutside;
504
505	DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero);
506	isl_pw_aff *SizeE = getScopArrayInfo()->getDimensionSizePw(i);
507	SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in,
508	isl_space_dim(Space, isl_dim_set));
509	SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in,
510	isl_space_get_tuple_id(Space, isl_dim_set));
511
512	DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var));
513
514	Outside = isl_set_union(Outside, DimOutside);
515	}
516
517	Outside = isl_set_apply(Outside, isl_map_reverse(getAccessRelation()));
518	Outside = isl_set_intersect(Outside, Statement->getDomain());
519	Outside = isl_set_params(Outside);
520
521	// Remove divs to avoid the construction of overly complicated assumptions.
522	// Doing so increases the set of parameter combinations that are assumed to
523	// not appear. This is always save, but may make the resulting run-time check
524	// bail out more often than strictly necessary.
525	Outside = isl_set_remove_divs(Outside);
526	Outside = isl_set_complement(Outside);
527	Statement->getParent()->addAssumption(INBOUNDS, Outside,
528	getAccessInstruction()->getDebugLoc());
529	isl_space_free(Space);
530	}
531
532	void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
533	ScalarEvolution *SE = Statement->getParent()->getSE();
534
535	Value Ptr = getPointerOperand(getAccessInstruction());
536	if (!Ptr \|\| !SE->isSCEVable(Ptr->getType()))
537	return;
538
539	auto *PtrSCEV = SE->getSCEV(Ptr);
540	if (isa<SCEVCouldNotCompute>(PtrSCEV))
541	return;
542
543	auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
544	if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
545	PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
546
547	const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
548	if (Range.isFullSet())
549	return;
550
551	bool isWrapping = Range.isSignWrappedSet();
552	unsigned BW = Range.getBitWidth();
553	const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
554	const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax();
555
556	auto Min = LB.sdiv(APInt(BW, ElementSize));
557	auto Max = (UB - APInt(BW, 1)).sdiv(APInt(BW, ElementSize));
558
559	isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation));
560	AccessRange =
561	addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set);
562	AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange);
563	}
564
565	__isl_give isl_map MemoryAccess::foldAccess(__isl_take isl_map AccessRelation,
566	ScopStmt *Statement) {
567	int Size = Subscripts.size();
568
569	for (int i = Size - 2; i >= 0; --i) {
570	isl_space *Space;
571	isl_map MapOne, MapTwo;
572	isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]);
573
574	isl_space *SpaceSize = isl_pw_aff_get_space(DimSize);
575	isl_pw_aff_free(DimSize);
576	isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0);
577
578	Space = isl_map_get_space(AccessRelation);
579	Space = isl_space_map_from_set(isl_space_range(Space));
580	Space = isl_space_align_params(Space, SpaceSize);
581
582	int ParamLocation = isl_space_find_dim_by_id(Space, isl_dim_param, ParamId);
583	isl_id_free(ParamId);
584
585	MapOne = isl_map_universe(isl_space_copy(Space));
586	for (int j = 0; j < Size; ++j)
587	MapOne = isl_map_equate(MapOne, isl_dim_in, j, isl_dim_out, j);
588	MapOne = isl_map_lower_bound_si(MapOne, isl_dim_in, i + 1, 0);
589
590	MapTwo = isl_map_universe(isl_space_copy(Space));
591	for (int j = 0; j < Size; ++j)
592	if (j < i \|\| j > i + 1)
593	MapTwo = isl_map_equate(MapTwo, isl_dim_in, j, isl_dim_out, j);
594
595	isl_local_space *LS = isl_local_space_from_space(Space);
596	isl_constraint *C;
597	C = isl_equality_alloc(isl_local_space_copy(LS));
598	C = isl_constraint_set_constant_si(C, -1);
599	C = isl_constraint_set_coefficient_si(C, isl_dim_in, i, 1);
600	C = isl_constraint_set_coefficient_si(C, isl_dim_out, i, -1);
601	MapTwo = isl_map_add_constraint(MapTwo, C);
602	C = isl_equality_alloc(LS);
603	C = isl_constraint_set_coefficient_si(C, isl_dim_in, i + 1, 1);
604	C = isl_constraint_set_coefficient_si(C, isl_dim_out, i + 1, -1);
605	C = isl_constraint_set_coefficient_si(C, isl_dim_param, ParamLocation, 1);
606	MapTwo = isl_map_add_constraint(MapTwo, C);
607	MapTwo = isl_map_upper_bound_si(MapTwo, isl_dim_in, i + 1, -1);
608
609	MapOne = isl_map_union(MapOne, MapTwo);
610	AccessRelation = isl_map_apply_range(AccessRelation, MapOne);
611	}
612	return AccessRelation;
613	}
614
615	/// @brief Check if @p Expr is divisible by @p Size.
616	static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
617
618	// Only one factor needs to be divisible.
619	if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
620	for (auto *FactorExpr : MulExpr->operands())
621	if (isDivisible(FactorExpr, Size, SE))
622	return true;
623	return false;
624	}
625
626	// For other n-ary expressions (Add, AddRec, Max,...) all operands need
627	// to be divisble.
628	if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
629	for (auto *OpExpr : NAryExpr->operands())
630	if (!isDivisible(OpExpr, Size, SE))
631	return false;
632	return true;
633	}
634
635	auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
636	auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
637	auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
638	return MulSCEV == Expr;
639	}
640
641	void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
642	assert(!AccessRelation && "AccessReltation already built")((!AccessRelation && "AccessReltation already built") ? static_cast<void> (0) : __assert_fail ("!AccessRelation && \"AccessReltation already built\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 642, __PRETTY_FUNCTION__));
643
644	isl_ctx *Ctx = isl_id_get_ctx(Id);
645	isl_id *BaseAddrId = SAI->getBasePtrId();
646
647	if (!isAffine()) {
648	// We overapproximate non-affine accesses with a possible access to the
649	// whole array. For read accesses it does not make a difference, if an
650	// access must or may happen. However, for write accesses it is important to
651	// differentiate between writes that must happen and writes that may happen.
652	AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
653	AccessRelation =
654	isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
655
656	computeBoundsOnAccessRelation(getElemSizeInBytes());
657	return;
658	}
659
660	Scop &S = *getStatement()->getParent();
661	isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
662	AccessRelation = isl_map_universe(Space);
663
664	for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
665	isl_pw_aff *Affine = Statement->getPwAff(Subscripts[i]);
666
667	if (Size == 1) {
668	// For the non delinearized arrays, divide the access function of the last
669	// subscript by the size of the elements in the array.
670	//
671	// A stride one array access in C expressed as A[i] is expressed in
672	// LLVM-IR as something like A[i * elementsize]. This hides the fact that
673	// two subsequent values of 'i' index two values that are stored next to
674	// each other in memory. By this division we make this characteristic
675	// obvious again. However, if the index is not divisible by the element
676	// size we will bail out.
677	isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes());
678	Affine = isl_pw_aff_scale_down_val(Affine, v);
679
680	if (!isDivisible(Subscripts[0], getElemSizeInBytes(), *S.getSE()))
681	S.invalidate(ALIGNMENT, AccessInstruction->getDebugLoc());
682	}
683
684	isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
685
686	AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
687	}
688
689	if (Sizes.size() > 1 && !isa<SCEVConstant>(Sizes[0]))
690	AccessRelation = foldAccess(AccessRelation, Statement);
691
692	Space = Statement->getDomainSpace();
693	AccessRelation = isl_map_set_tuple_id(
694	AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
695	AccessRelation =
696	isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
697
698	AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
699	isl_space_free(Space);
700	}
701
702	MemoryAccess::MemoryAccess(ScopStmt Stmt, Instruction AccessInst,
703	AccessType Type, Value *BaseAddress,
704	unsigned ElemBytes, bool Affine,
705	ArrayRef<const SCEV *> Subscripts,
706	ArrayRef<const SCEV > Sizes, Value AccessValue,
707	ScopArrayInfo::MemoryKind Kind, StringRef BaseName)
708	: Kind(Kind), AccType(Type), RedType(RT_NONE), Statement(Stmt),
709	BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
710	Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
711	AccessValue(AccessValue), IsAffine(Affine),
712	Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
713	NewAccessRelation(nullptr) {
714
715	std::string IdName = "__polly_array_ref";
716	Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
717	}
718
719	void MemoryAccess::realignParams() {
720	isl_space *ParamSpace = Statement->getParent()->getParamSpace();
721	AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
722	}
723
724	const std::string MemoryAccess::getReductionOperatorStr() const {
725	return MemoryAccess::getReductionOperatorStr(getReductionType());
726	}
727
728	__isl_give isl_id *MemoryAccess::getId() const { return isl_id_copy(Id); }
729
730	raw_ostream &polly::operator<<(raw_ostream &OS,
731	MemoryAccess::ReductionType RT) {
732	if (RT == MemoryAccess::RT_NONE)
733	OS << "NONE";
734	else
735	OS << MemoryAccess::getReductionOperatorStr(RT);
736	return OS;
737	}
738
739	void MemoryAccess::print(raw_ostream &OS) const {
740	switch (AccType) {
741	case READ:
742	OS.indent(12) << "ReadAccess :=\t";
743	break;
744	case MUST_WRITE:
745	OS.indent(12) << "MustWriteAccess :=\t";
746	break;
747	case MAY_WRITE:
748	OS.indent(12) << "MayWriteAccess :=\t";
749	break;
750	}
751	OS << "[Reduction Type: " << getReductionType() << "] ";
752	OS << "[Scalar: " << isScalarKind() << "]\n";
753	OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
754	if (hasNewAccessRelation())
755	OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
756	}
757
758	void MemoryAccess::dump() const { print(errs()); }
759
760	// Create a map in the size of the provided set domain, that maps from the
761	// one element of the provided set domain to another element of the provided
762	// set domain.
763	// The mapping is limited to all points that are equal in all but the last
764	// dimension and for which the last dimension of the input is strict smaller
765	// than the last dimension of the output.
766	//
767	// getEqualAndLarger(set[i0, i1, ..., iX]):
768	//
769	// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
770	// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
771	//
772	static isl_map getEqualAndLarger(isl_space setDomain) {
773	isl_space *Space = isl_space_map_from_set(setDomain);
774	isl_map *Map = isl_map_universe(Space);
775	unsigned lastDimension = isl_map_dim(Map, isl_dim_in) - 1;
776
777	// Set all but the last dimension to be equal for the input and output
778	//
779	// input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
780	// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
781	for (unsigned i = 0; i < lastDimension; ++i)
782	Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
783
784	// Set the last dimension of the input to be strict smaller than the
785	// last dimension of the output.
786	//
787	// input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
788	Map = isl_map_order_lt(Map, isl_dim_in, lastDimension, isl_dim_out,
789	lastDimension);
790	return Map;
791	}
792
793	__isl_give isl_set *
794	MemoryAccess::getStride(__isl_take const isl_map *Schedule) const {
795	isl_map S = const_cast<isl_map >(Schedule);
796	isl_map *AccessRelation = getAccessRelation();
797	isl_space *Space = isl_space_range(isl_map_get_space(S));
798	isl_map *NextScatt = getEqualAndLarger(Space);
799
800	S = isl_map_reverse(S);
801	NextScatt = isl_map_lexmin(NextScatt);
802
803	NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S));
804	NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation));
805	NextScatt = isl_map_apply_domain(NextScatt, S);
806	NextScatt = isl_map_apply_domain(NextScatt, AccessRelation);
807
808	isl_set *Deltas = isl_map_deltas(NextScatt);
809	return Deltas;
810	}
811
812	bool MemoryAccess::isStrideX(__isl_take const isl_map *Schedule,
813	int StrideWidth) const {
814	isl_set Stride, StrideX;
815	bool IsStrideX;
816
817	Stride = getStride(Schedule);
818	StrideX = isl_set_universe(isl_set_get_space(Stride));
819	for (unsigned i = 0; i < isl_set_dim(StrideX, isl_dim_set) - 1; i++)
820	StrideX = isl_set_fix_si(StrideX, isl_dim_set, i, 0);
821	StrideX = isl_set_fix_si(StrideX, isl_dim_set,
822	isl_set_dim(StrideX, isl_dim_set) - 1, StrideWidth);
823	IsStrideX = isl_set_is_subset(Stride, StrideX);
824
825	isl_set_free(StrideX);
826	isl_set_free(Stride);
827
828	return IsStrideX;
829	}
830
831	bool MemoryAccess::isStrideZero(const isl_map *Schedule) const {
832	return isStrideX(Schedule, 0);
833	}
834
835	bool MemoryAccess::isStrideOne(const isl_map *Schedule) const {
836	return isStrideX(Schedule, 1);
837	}
838
839	void MemoryAccess::setNewAccessRelation(isl_map *NewAccess) {
840	isl_map_free(NewAccessRelation);
841	NewAccessRelation = NewAccess;
842	}
843
844	//===----------------------------------------------------------------------===//
845
846	isl_map *ScopStmt::getSchedule() const {
847	isl_set *Domain = getDomain();
848	if (isl_set_is_empty(Domain)) {
849	isl_set_free(Domain);
850	return isl_map_from_aff(
851	isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
852	}
853	auto *Schedule = getParent()->getSchedule();
854	Schedule = isl_union_map_intersect_domain(
855	Schedule, isl_union_set_from_set(isl_set_copy(Domain)));
856	if (isl_union_map_is_empty(Schedule)) {
857	isl_set_free(Domain);
858	isl_union_map_free(Schedule);
859	return isl_map_from_aff(
860	isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));
861	}
862	auto *M = isl_map_from_union_map(Schedule);
863	M = isl_map_coalesce(M);
864	M = isl_map_gist_domain(M, Domain);
865	M = isl_map_coalesce(M);
866	return M;
867	}
868
869	__isl_give isl_pw_aff ScopStmt::getPwAff(const SCEV E) {
870	return getParent()->getPwAff(E, isBlockStmt() ? getBasicBlock()
871	: getRegion()->getEntry());
872	}
873
874	void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
875	assert(isl_set_is_subset(NewDomain, Domain) &&((isl_set_is_subset(NewDomain, Domain) && "New domain is not a subset of old domain!" ) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(NewDomain, Domain) && \"New domain is not a subset of old domain!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 876, __PRETTY_FUNCTION__))
876	"New domain is not a subset of old domain!")((isl_set_is_subset(NewDomain, Domain) && "New domain is not a subset of old domain!" ) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(NewDomain, Domain) && \"New domain is not a subset of old domain!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 876, __PRETTY_FUNCTION__));
877	isl_set_free(Domain);
878	Domain = NewDomain;
879	}
880
881	void ScopStmt::buildAccessRelations() {
882	for (MemoryAccess *Access : MemAccs) {
883	Type *ElementType = Access->getAccessValue()->getType();
884
885	ScopArrayInfo::MemoryKind Ty;
886	if (Access->isPHIKind())
887	Ty = ScopArrayInfo::MK_PHI;
888	else if (Access->isExitPHIKind())
889	Ty = ScopArrayInfo::MK_ExitPHI;
890	else if (Access->isValueKind())
891	Ty = ScopArrayInfo::MK_Value;
892	else
893	Ty = ScopArrayInfo::MK_Array;
894
895	const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
896	Access->getBaseAddr(), ElementType, Access->Sizes, Ty);
897
898	Access->buildAccessRelation(SAI);
899	}
900	}
901
902	void ScopStmt::addAccess(MemoryAccess *Access) {
903	Instruction *AccessInst = Access->getAccessInstruction();
904
905	if (Access->isArrayKind()) {
906	MemoryAccessList &MAL = InstructionToAccess[AccessInst];
907	MAL.emplace_front(Access);
908	}
909
910	MemAccs.push_back(Access);
911	}
912
913	void ScopStmt::realignParams() {
914	for (MemoryAccess MA : this)
915	MA->realignParams();
916
917	Domain = isl_set_align_params(Domain, Parent.getParamSpace());
918	}
919
920	/// @brief Add @p BSet to the set @p User if @p BSet is bounded.
921	static isl_stat collectBoundedParts(__isl_take isl_basic_set *BSet,
922	void *User) {
923	isl_set BoundedParts = static_cast<isl_set >(User);
924	if (isl_basic_set_is_bounded(BSet))
925	BoundedParts = isl_set_union(BoundedParts, isl_set_from_basic_set(BSet));
926	else
927	isl_basic_set_free(BSet);
928	return isl_stat_ok;
929	}
930
931	/// @brief Return the bounded parts of @p S.
932	static __isl_give isl_set collectBoundedParts(__isl_take isl_set S) {
933	isl_set *BoundedParts = isl_set_empty(isl_set_get_space(S));
934	isl_set_foreach_basic_set(S, collectBoundedParts, &BoundedParts);
935	isl_set_free(S);
936	return BoundedParts;
937	}
938
939	/// @brief Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
940	///
941	/// @returns A separation of @p S into first an unbounded then a bounded subset,
942	/// both with regards to the dimension @p Dim.
943	static std::pair<__isl_give isl_set , __isl_give isl_set >
944	partitionSetParts(__isl_take isl_set *S, unsigned Dim) {
945
946	for (unsigned u = 0, e = isl_set_n_dim(S); u < e; u++)
947	S = isl_set_lower_bound_si(S, isl_dim_set, u, 0);
948
949	unsigned NumDimsS = isl_set_n_dim(S);
950	isl_set *OnlyDimS = isl_set_copy(S);
951
952	// Remove dimensions that are greater than Dim as they are not interesting.
953	assert(NumDimsS >= Dim + 1)((NumDimsS >= Dim + 1) ? static_cast<void> (0) : __assert_fail ("NumDimsS >= Dim + 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 953, __PRETTY_FUNCTION__));
954	OnlyDimS =
955	isl_set_project_out(OnlyDimS, isl_dim_set, Dim + 1, NumDimsS - Dim - 1);
956
957	// Create artificial parametric upper bounds for dimensions smaller than Dim
958	// as we are not interested in them.
959	OnlyDimS = isl_set_insert_dims(OnlyDimS, isl_dim_param, 0, Dim);
960	for (unsigned u = 0; u < Dim; u++) {
961	isl_constraint *C = isl_inequality_alloc(
962	isl_local_space_from_space(isl_set_get_space(OnlyDimS)));
963	C = isl_constraint_set_coefficient_si(C, isl_dim_param, u, 1);
964	C = isl_constraint_set_coefficient_si(C, isl_dim_set, u, -1);
965	OnlyDimS = isl_set_add_constraint(OnlyDimS, C);
966	}
967
968	// Collect all bounded parts of OnlyDimS.
969	isl_set *BoundedParts = collectBoundedParts(OnlyDimS);
970
971	// Create the dimensions greater than Dim again.
972	BoundedParts = isl_set_insert_dims(BoundedParts, isl_dim_set, Dim + 1,
973	NumDimsS - Dim - 1);
974
975	// Remove the artificial upper bound parameters again.
976	BoundedParts = isl_set_remove_dims(BoundedParts, isl_dim_param, 0, Dim);
977
978	isl_set *UnboundedParts = isl_set_subtract(S, isl_set_copy(BoundedParts));
979	return std::make_pair(UnboundedParts, BoundedParts);
980	}
981
982	/// @brief Set the dimension Ids from @p From in @p To.
983	static __isl_give isl_set setDimensionIds(__isl_keep isl_set From,
984	__isl_take isl_set *To) {
985	for (unsigned u = 0, e = isl_set_n_dim(From); u < e; u++) {
986	isl_id *DimId = isl_set_get_dim_id(From, isl_dim_set, u);
987	To = isl_set_set_dim_id(To, isl_dim_set, u, DimId);
988	}
989	return To;
990	}
991
992	/// @brief Create the conditions under which @p L @p Pred @p R is true.
993	static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
994	__isl_take isl_pw_aff *L,
995	__isl_take isl_pw_aff *R) {
996	switch (Pred) {
997	case ICmpInst::ICMP_EQ:
998	return isl_pw_aff_eq_set(L, R);
999	case ICmpInst::ICMP_NE:
1000	return isl_pw_aff_ne_set(L, R);
1001	case ICmpInst::ICMP_SLT:
1002	return isl_pw_aff_lt_set(L, R);
1003	case ICmpInst::ICMP_SLE:
1004	return isl_pw_aff_le_set(L, R);
1005	case ICmpInst::ICMP_SGT:
1006	return isl_pw_aff_gt_set(L, R);
1007	case ICmpInst::ICMP_SGE:
1008	return isl_pw_aff_ge_set(L, R);
1009	case ICmpInst::ICMP_ULT:
1010	return isl_pw_aff_lt_set(L, R);
1011	case ICmpInst::ICMP_UGT:
1012	return isl_pw_aff_gt_set(L, R);
1013	case ICmpInst::ICMP_ULE:
1014	return isl_pw_aff_le_set(L, R);
1015	case ICmpInst::ICMP_UGE:
1016	return isl_pw_aff_ge_set(L, R);
1017	default:
1018	llvm_unreachable("Non integer predicate not supported")::llvm::llvm_unreachable_internal("Non integer predicate not supported" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1018);
1019	}
1020	}
1021
1022	/// @brief Create the conditions under which @p L @p Pred @p R is true.
1023	///
1024	/// Helper function that will make sure the dimensions of the result have the
1025	/// same isl_id's as the @p Domain.
1026	static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
1027	__isl_take isl_pw_aff *L,
1028	__isl_take isl_pw_aff *R,
1029	__isl_keep isl_set *Domain) {
1030	isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R);
1031	return setDimensionIds(Domain, ConsequenceCondSet);
1032	}
1033
1034	/// @brief Build the conditions sets for the switch @p SI in the @p Domain.
1035	///
1036	/// This will fill @p ConditionSets with the conditions under which control
1037	/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
1038	/// have as many elements as @p SI has successors.
1039	static void
1040	buildConditionSets(Scop &S, SwitchInst SI, Loop L, __isl_keep isl_set *Domain,
1041	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1042
1043	Value *Condition = getConditionFromTerminator(SI);
1044	assert(Condition && "No condition for switch")((Condition && "No condition for switch") ? static_cast <void> (0) : __assert_fail ("Condition && \"No condition for switch\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1044, __PRETTY_FUNCTION__));
1045
1046	ScalarEvolution &SE = *S.getSE();
1047	BasicBlock *BB = SI->getParent();
1048	isl_pw_aff LHS, RHS;
1049	LHS = S.getPwAff(SE.getSCEVAtScope(Condition, L), BB);
1050
1051	unsigned NumSuccessors = SI->getNumSuccessors();
1052	ConditionSets.resize(NumSuccessors);
1053	for (auto &Case : SI->cases()) {
1054	unsigned Idx = Case.getSuccessorIndex();
1055	ConstantInt *CaseValue = Case.getCaseValue();
1056
1057	RHS = S.getPwAff(SE.getSCEV(CaseValue), BB);
1058	isl_set *CaseConditionSet =
1059	buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain);
1060	ConditionSets[Idx] = isl_set_coalesce(
1061	isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
1062	}
1063
1064	assert(ConditionSets[0] == nullptr && "Default condition set was set")((ConditionSets[0] == nullptr && "Default condition set was set" ) ? static_cast<void> (0) : __assert_fail ("ConditionSets[0] == nullptr && \"Default condition set was set\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1064, __PRETTY_FUNCTION__));
1065	isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
1066	for (unsigned u = 2; u < NumSuccessors; u++)
1067	ConditionSetUnion =
1068	isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
1069	ConditionSets[0] = setDimensionIds(
1070	Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
1071
1072	S.markAsOptimized();
1073	isl_pw_aff_free(LHS);
1074	}
1075
1076	/// @brief Build the conditions sets for the branch condition @p Condition in
1077	/// the @p Domain.
1078	///
1079	/// This will fill @p ConditionSets with the conditions under which control
1080	/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1081	/// have as many elements as @p TI has successors. If @p TI is nullptr the
1082	/// context under which @p Condition is true/false will be returned as the
1083	/// new elements of @p ConditionSets.
1084	static void
1085	buildConditionSets(Scop &S, Value Condition, TerminatorInst TI, Loop *L,
1086	__isl_keep isl_set *Domain,
1087	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1088
1089	isl_set *ConsequenceCondSet = nullptr;
1090	if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
1091	if (CCond->isZero())
1092	ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1093	else
1094	ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1095	} else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
1096	auto Opcode = BinOp->getOpcode();
1097	assert(Opcode == Instruction::And \|\| Opcode == Instruction::Or)((Opcode == Instruction::And \|\| Opcode == Instruction::Or) ? static_cast <void> (0) : __assert_fail ("Opcode == Instruction::And \|\| Opcode == Instruction::Or" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1097, __PRETTY_FUNCTION__));
1098
1099	buildConditionSets(S, BinOp->getOperand(0), TI, L, Domain, ConditionSets);
1100	buildConditionSets(S, BinOp->getOperand(1), TI, L, Domain, ConditionSets);
1101
1102	isl_set_free(ConditionSets.pop_back_val());
1103	isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
1104	isl_set_free(ConditionSets.pop_back_val());
1105	isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
1106
1107	if (Opcode == Instruction::And)
1108	ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
1109	else
1110	ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
1111	} else {
1112	auto *ICond = dyn_cast<ICmpInst>(Condition);
1113	assert(ICond &&((ICond && "Condition of exiting branch was neither constant nor ICmp!" ) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1114, __PRETTY_FUNCTION__))
1114	"Condition of exiting branch was neither constant nor ICmp!")((ICond && "Condition of exiting branch was neither constant nor ICmp!" ) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1114, __PRETTY_FUNCTION__));
1115
1116	ScalarEvolution &SE = *S.getSE();
1117	BasicBlock *BB = TI ? TI->getParent() : nullptr;
1118	isl_pw_aff LHS, RHS;
1119	LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB);
1120	RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB);
1121	ConsequenceCondSet =
1122	buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
1123	}
1124
1125	// If no terminator was given we are only looking for parameter constraints
1126	// under which @p Condition is true/false.
1127	if (!TI)
1128	ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
1129
1130	assert(ConsequenceCondSet)((ConsequenceCondSet) ? static_cast<void> (0) : __assert_fail ("ConsequenceCondSet", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1130, __PRETTY_FUNCTION__));
1131	isl_set *AlternativeCondSet =
1132	isl_set_complement(isl_set_copy(ConsequenceCondSet));
1133
1134	ConditionSets.push_back(isl_set_coalesce(
1135	isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));
1136	ConditionSets.push_back(isl_set_coalesce(
1137	isl_set_intersect(AlternativeCondSet, isl_set_copy(Domain))));
1138	}
1139
1140	/// @brief Build the conditions sets for the terminator @p TI in the @p Domain.
1141	///
1142	/// This will fill @p ConditionSets with the conditions under which control
1143	/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1144	/// have as many elements as @p TI has successors.
1145	static void
1146	buildConditionSets(Scop &S, TerminatorInst TI, Loop L,
1147	__isl_keep isl_set *Domain,
1148	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1149
1150	if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
1151	return buildConditionSets(S, SI, L, Domain, ConditionSets);
1152
1153	assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.")((isa<BranchInst>(TI) && "Terminator was neither branch nor switch." ) ? static_cast<void> (0) : __assert_fail ("isa<BranchInst>(TI) && \"Terminator was neither branch nor switch.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1153, __PRETTY_FUNCTION__));
1154
1155	if (TI->getNumSuccessors() == 1) {
1156	ConditionSets.push_back(isl_set_copy(Domain));
1157	return;
1158	}
1159
1160	Value *Condition = getConditionFromTerminator(TI);
1161	assert(Condition && "No condition for Terminator")((Condition && "No condition for Terminator") ? static_cast <void> (0) : __assert_fail ("Condition && \"No condition for Terminator\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1161, __PRETTY_FUNCTION__));
1162
1163	return buildConditionSets(S, Condition, TI, L, Domain, ConditionSets);
1164	}
1165
1166	void ScopStmt::buildDomain() {
1167	isl_id *Id;
1168
1169	Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
1170
1171	Domain = getParent()->getDomainConditions(this);
1172	Domain = isl_set_set_tuple_id(Domain, Id);
1173	}
1174
1175	void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP) {
1176	isl_ctx *Ctx = Parent.getIslCtx();
1177	isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace());
1178	Type *Ty = GEP->getPointerOperandType();
1179	ScalarEvolution &SE = *Parent.getSE();
1180	ScopDetection &SD = Parent.getSD();
1181
1182	// The set of loads that are required to be invariant.
1183	auto &ScopRIL = *SD.getRequiredInvariantLoads(&Parent.getRegion());
1184
1185	std::vector<const SCEV *> Subscripts;
1186	std::vector<int> Sizes;
1187
1188	std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
1189
1190	if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
1191	Ty = PtrTy->getElementType();
	Value stored to 'Ty' is never read
1192	}
1193
1194	int IndexOffset = Subscripts.size() - Sizes.size();
1195
1196	assert(IndexOffset <= 1 && "Unexpected large index offset")((IndexOffset <= 1 && "Unexpected large index offset" ) ? static_cast<void> (0) : __assert_fail ("IndexOffset <= 1 && \"Unexpected large index offset\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1196, __PRETTY_FUNCTION__));
1197
1198	for (size_t i = 0; i < Sizes.size(); i++) {
1199	auto Expr = Subscripts[i + IndexOffset];
1200	auto Size = Sizes[i];
1201
1202	InvariantLoadsSetTy AccessILS;
1203	if (!isAffineExpr(&Parent.getRegion(), Expr, SE, nullptr, &AccessILS))
1204	continue;
1205
1206	bool NonAffine = false;
1207	for (LoadInst *LInst : AccessILS)
1208	if (!ScopRIL.count(LInst))
1209	NonAffine = true;
1210
1211	if (NonAffine)
1212	continue;
1213
1214	isl_pw_aff *AccessOffset = getPwAff(Expr);
1215	AccessOffset =
1216	isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId());
1217
1218	isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain(
1219	isl_local_space_copy(LSpace), isl_val_int_from_si(Ctx, Size)));
1220
1221	isl_set *OutOfBound = isl_pw_aff_ge_set(AccessOffset, DimSize);
1222	OutOfBound = isl_set_intersect(getDomain(), OutOfBound);
1223	OutOfBound = isl_set_params(OutOfBound);
1224	isl_set *InBound = isl_set_complement(OutOfBound);
1225	isl_set *Executed = isl_set_params(getDomain());
1226
1227	// A => B == !A or B
1228	isl_set *InBoundIfExecuted =
1229	isl_set_union(isl_set_complement(Executed), InBound);
1230
1231	InBoundIfExecuted = isl_set_coalesce(InBoundIfExecuted);
1232	Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc());
1233	}
1234
1235	isl_local_space_free(LSpace);
1236	}
1237
1238	void ScopStmt::deriveAssumptions(BasicBlock *Block) {
1239	for (Instruction &Inst : *Block)
1240	if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
1241	deriveAssumptionsFromGEP(GEP);
1242	}
1243
1244	void ScopStmt::collectSurroundingLoops() {
1245	for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
1246	isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
1247	NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
1248	isl_id_free(DimId);
1249	}
1250	}
1251
1252	ScopStmt::ScopStmt(Scop &parent, Region &R)
1253	: Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) {
1254
1255	BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
1256	}
1257
1258	ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
1259	: Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) {
1260
1261	BaseName = getIslCompatibleName("Stmt_", &bb, "");
1262	}
1263
1264	void ScopStmt::init() {
1265	assert(!Domain && "init must be called only once")((!Domain && "init must be called only once") ? static_cast <void> (0) : __assert_fail ("!Domain && \"init must be called only once\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1265, __PRETTY_FUNCTION__));
1266
1267	buildDomain();
1268	collectSurroundingLoops();
1269	buildAccessRelations();
1270
1271	if (BB) {
1272	deriveAssumptions(BB);
1273	} else {
1274	for (BasicBlock *Block : R->blocks()) {
1275	deriveAssumptions(Block);
1276	}
1277	}
1278
1279	if (DetectReductions)
1280	checkForReductions();
1281	}
1282
1283	/// @brief Collect loads which might form a reduction chain with @p StoreMA
1284	///
1285	/// Check if the stored value for @p StoreMA is a binary operator with one or
1286	/// two loads as operands. If the binary operand is commutative & associative,
1287	/// used only once (by @p StoreMA) and its load operands are also used only
1288	/// once, we have found a possible reduction chain. It starts at an operand
1289	/// load and includes the binary operator and @p StoreMA.
1290	///
1291	/// Note: We allow only one use to ensure the load and binary operator cannot
1292	/// escape this block or into any other store except @p StoreMA.
1293	void ScopStmt::collectCandiateReductionLoads(
1294	MemoryAccess StoreMA, SmallVectorImpl<MemoryAccess > &Loads) {
1295	auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
1296	if (!Store)
1297	return;
1298
1299	// Skip if there is not one binary operator between the load and the store
1300	auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
1301	if (!BinOp)
1302	return;
1303
1304	// Skip if the binary operators has multiple uses
1305	if (BinOp->getNumUses() != 1)
1306	return;
1307
1308	// Skip if the opcode of the binary operator is not commutative/associative
1309	if (!BinOp->isCommutative() \|\| !BinOp->isAssociative())
1310	return;
1311
1312	// Skip if the binary operator is outside the current SCoP
1313	if (BinOp->getParent() != Store->getParent())
1314	return;
1315
1316	// Skip if it is a multiplicative reduction and we disabled them
1317	if (DisableMultiplicativeReductions &&
1318	(BinOp->getOpcode() == Instruction::Mul \|\|
1319	BinOp->getOpcode() == Instruction::FMul))
1320	return;
1321
1322	// Check the binary operator operands for a candidate load
1323	auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
1324	auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
1325	if (!PossibleLoad0 && !PossibleLoad1)
1326	return;
1327
1328	// A load is only a candidate if it cannot escape (thus has only this use)
1329	if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
1330	if (PossibleLoad0->getParent() == Store->getParent())
1331	Loads.push_back(&getArrayAccessFor(PossibleLoad0));
1332	if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
1333	if (PossibleLoad1->getParent() == Store->getParent())
1334	Loads.push_back(&getArrayAccessFor(PossibleLoad1));
1335	}
1336
1337	/// @brief Check for reductions in this ScopStmt
1338	///
1339	/// Iterate over all store memory accesses and check for valid binary reduction
1340	/// like chains. For all candidates we check if they have the same base address
1341	/// and there are no other accesses which overlap with them. The base address
1342	/// check rules out impossible reductions candidates early. The overlap check,
1343	/// together with the "only one user" check in collectCandiateReductionLoads,
1344	/// guarantees that none of the intermediate results will escape during
1345	/// execution of the loop nest. We basically check here that no other memory
1346	/// access can access the same memory as the potential reduction.
1347	void ScopStmt::checkForReductions() {
1348	SmallVector<MemoryAccess *, 2> Loads;
1349	SmallVector<std::pair<MemoryAccess , MemoryAccess >, 4> Candidates;
1350
1351	// First collect candidate load-store reduction chains by iterating over all
1352	// stores and collecting possible reduction loads.
1353	for (MemoryAccess *StoreMA : MemAccs) {
1354	if (StoreMA->isRead())
1355	continue;
1356
1357	Loads.clear();
1358	collectCandiateReductionLoads(StoreMA, Loads);
1359	for (MemoryAccess *LoadMA : Loads)
1360	Candidates.push_back(std::make_pair(LoadMA, StoreMA));
1361	}
1362
1363	// Then check each possible candidate pair.
1364	for (const auto &CandidatePair : Candidates) {
1365	bool Valid = true;
1366	isl_map *LoadAccs = CandidatePair.first->getAccessRelation();
1367	isl_map *StoreAccs = CandidatePair.second->getAccessRelation();
1368
1369	// Skip those with obviously unequal base addresses.
1370	if (!isl_map_has_equal_space(LoadAccs, StoreAccs)) {
1371	isl_map_free(LoadAccs);
1372	isl_map_free(StoreAccs);
1373	continue;
1374	}
1375
1376	// And check if the remaining for overlap with other memory accesses.
1377	isl_map *AllAccsRel = isl_map_union(LoadAccs, StoreAccs);
1378	AllAccsRel = isl_map_intersect_domain(AllAccsRel, getDomain());
1379	isl_set *AllAccs = isl_map_range(AllAccsRel);
1380
1381	for (MemoryAccess *MA : MemAccs) {
1382	if (MA == CandidatePair.first \|\| MA == CandidatePair.second)
1383	continue;
1384
1385	isl_map *AccRel =
1386	isl_map_intersect_domain(MA->getAccessRelation(), getDomain());
1387	isl_set *Accs = isl_map_range(AccRel);
1388
1389	if (isl_set_has_equal_space(AllAccs, Accs) \|\| isl_set_free(Accs)) {
1390	isl_set *OverlapAccs = isl_set_intersect(Accs, isl_set_copy(AllAccs));
1391	Valid = Valid && isl_set_is_empty(OverlapAccs);
1392	isl_set_free(OverlapAccs);
1393	}
1394	}
1395
1396	isl_set_free(AllAccs);
1397	if (!Valid)
1398	continue;
1399
1400	const LoadInst *Load =
1401	dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
1402	MemoryAccess::ReductionType RT =
1403	getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load);
1404
1405	// If no overlapping access was found we mark the load and store as
1406	// reduction like.
1407	CandidatePair.first->markAsReductionLike(RT);
1408	CandidatePair.second->markAsReductionLike(RT);
1409	}
1410	}
1411
1412	std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }
1413
1414	std::string ScopStmt::getScheduleStr() const {
1415	auto *S = getSchedule();
1416	auto Str = stringFromIslObj(S);
1417	isl_map_free(S);
1418	return Str;
1419	}
1420
1421	unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); }
1422
1423	unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
1424
1425	const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1426
1427	const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
1428	return NestLoops[Dimension];
1429	}
1430
1431	isl_ctx *ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
1432
1433	__isl_give isl_set *ScopStmt::getDomain() const { return isl_set_copy(Domain); }
1434
1435	__isl_give isl_space *ScopStmt::getDomainSpace() const {
1436	return isl_set_get_space(Domain);
1437	}
1438
1439	__isl_give isl_id *ScopStmt::getDomainId() const {
1440	return isl_set_get_tuple_id(Domain);
1441	}
1442
1443	ScopStmt::~ScopStmt() { isl_set_free(Domain); }
1444
1445	void ScopStmt::print(raw_ostream &OS) const {
1446	OS << "\t" << getBaseName() << "\n";
1447	OS.indent(12) << "Domain :=\n";
1448
1449	if (Domain) {
1450	OS.indent(16) << getDomainStr() << ";\n";
1451	} else
1452	OS.indent(16) << "n/a\n";
1453
1454	OS.indent(12) << "Schedule :=\n";
1455
1456	if (Domain) {
1457	OS.indent(16) << getScheduleStr() << ";\n";
1458	} else
1459	OS.indent(16) << "n/a\n";
1460
1461	for (MemoryAccess *Access : MemAccs)
1462	Access->print(OS);
1463	}
1464
1465	void ScopStmt::dump() const { print(dbgs()); }
1466
1467	void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) {
1468	// Remove all memory accesses in @p InvMAs from this statement
1469	// together with all scalar accesses that were caused by them.
1470	for (MemoryAccess *MA : InvMAs) {
1471	auto Predicate = [&](MemoryAccess *Acc) {
1472	return Acc->getAccessInstruction() == MA->getAccessInstruction();
1473	};
1474	MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
1475	MemAccs.end());
1476	InstructionToAccess.erase(MA->getAccessInstruction());
1477	}
1478	}
1479
1480	//===----------------------------------------------------------------------===//
1481	/// Scop class implement
1482
1483	void Scop::setContext(__isl_take isl_set *NewContext) {
1484	NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
1485	isl_set_free(Context);
1486	Context = NewContext;
1487	}
1488
1489	/// @brief Remap parameter values but keep AddRecs valid wrt. invariant loads.
1490	struct SCEVSensitiveParameterRewriter
1491	: public SCEVVisitor<SCEVSensitiveParameterRewriter, const SCEV *> {
1492	ValueToValueMap &VMap;
1493	ScalarEvolution &SE;
1494
1495	public:
1496	SCEVSensitiveParameterRewriter(ValueToValueMap &VMap, ScalarEvolution &SE)
1497	: VMap(VMap), SE(SE) {}
1498
1499	static const SCEV rewrite(const SCEV E, ScalarEvolution &SE,
1500	ValueToValueMap &VMap) {
1501	SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1502	return SSPR.visit(E);
1503	}
1504
1505	const SCEV visit(const SCEV E) {
1506	return SCEVVisitor<SCEVSensitiveParameterRewriter, const SCEV *>::visit(E);
1507	}
1508
1509	const SCEV visitConstant(const SCEVConstant E) { return E; }
1510
1511	const SCEV visitTruncateExpr(const SCEVTruncateExpr E) {
1512	return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
1513	}
1514
1515	const SCEV visitZeroExtendExpr(const SCEVZeroExtendExpr E) {
1516	return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
1517	}
1518
1519	const SCEV visitSignExtendExpr(const SCEVSignExtendExpr E) {
1520	return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
1521	}
1522
1523	const SCEV visitAddExpr(const SCEVAddExpr E) {
1524	SmallVector<const SCEV *, 4> Operands;
1525	for (int i = 0, e = E->getNumOperands(); i < e; ++i)
1526	Operands.push_back(visit(E->getOperand(i)));
1527	return SE.getAddExpr(Operands);
1528	}
1529
1530	const SCEV visitMulExpr(const SCEVMulExpr E) {
1531	SmallVector<const SCEV *, 4> Operands;
1532	for (int i = 0, e = E->getNumOperands(); i < e; ++i)
1533	Operands.push_back(visit(E->getOperand(i)));
1534	return SE.getMulExpr(Operands);
1535	}
1536
1537	const SCEV visitSMaxExpr(const SCEVSMaxExpr E) {
1538	SmallVector<const SCEV *, 4> Operands;
1539	for (int i = 0, e = E->getNumOperands(); i < e; ++i)
1540	Operands.push_back(visit(E->getOperand(i)));
1541	return SE.getSMaxExpr(Operands);
1542	}
1543
1544	const SCEV visitUMaxExpr(const SCEVUMaxExpr E) {
1545	SmallVector<const SCEV *, 4> Operands;
1546	for (int i = 0, e = E->getNumOperands(); i < e; ++i)
1547	Operands.push_back(visit(E->getOperand(i)));
1548	return SE.getUMaxExpr(Operands);
1549	}
1550
1551	const SCEV visitUDivExpr(const SCEVUDivExpr E) {
1552	return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS()));
1553	}
1554
1555	const SCEV visitAddRecExpr(const SCEVAddRecExpr E) {
1556	auto *Start = visit(E->getStart());
1557	auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
1558	visit(E->getStepRecurrence(SE)),
1559	E->getLoop(), SCEV::FlagAnyWrap);
1560	return SE.getAddExpr(Start, AddRec);
1561	}
1562
1563	const SCEV visitUnknown(const SCEVUnknown E) {
1564	if (auto *NewValue = VMap.lookup(E->getValue()))
1565	return SE.getUnknown(NewValue);
1566	return E;
1567	}
1568	};
1569
1570	const SCEV Scop::getRepresentingInvariantLoadSCEV(const SCEV S) {
1571	return SCEVSensitiveParameterRewriter::rewrite(S, *SE, InvEquivClassVMap);
1572	}
1573
1574	void Scop::addParams(std::vector<const SCEV *> NewParameters) {
1575	for (const SCEV *Parameter : NewParameters) {
1576	Parameter = extractConstantFactor(Parameter, *SE).second;
1577
1578	// Normalize the SCEV to get the representing element for an invariant load.
1579	Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1580
1581	if (ParameterIds.find(Parameter) != ParameterIds.end())
1582	continue;
1583
1584	int dimension = Parameters.size();
1585
1586	Parameters.push_back(Parameter);
1587	ParameterIds[Parameter] = dimension;
1588	}
1589	}
1590
1591	__isl_give isl_id Scop::getIdForParam(const SCEV Parameter) {
1592	// Normalize the SCEV to get the representing element for an invariant load.
1593	Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1594
1595	ParamIdType::const_iterator IdIter = ParameterIds.find(Parameter);
1596
1597	if (IdIter == ParameterIds.end())
1598	return nullptr;
1599
1600	std::string ParameterName;
1601
1602	ParameterName = "p_" + utostr_32(IdIter->second);
1603
1604	if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1605	Value *Val = ValueParameter->getValue();
1606
1607	// If this parameter references a specific Value and this value has a name
1608	// we use this name as it is likely to be unique and more useful than just
1609	// a number.
1610	if (Val->hasName())
1611	ParameterName = Val->getName();
1612	else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1613	auto LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1614	if (LoadOrigin->hasName()) {
1615	ParameterName += "_loaded_from_";
1616	ParameterName +=
1617	LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1618	}
1619	}
1620	}
1621
1622	return isl_id_alloc(getIslCtx(), ParameterName.c_str(),
1623	const_cast<void >((const void )Parameter));
1624	}
1625
1626	isl_set Scop::addNonEmptyDomainConstraints(isl_set C) const {
1627	isl_set *DomainContext = isl_union_set_params(getDomains());
1628	return isl_set_intersect_params(C, DomainContext);
1629	}
1630
1631	void Scop::buildBoundaryContext() {
1632	if (IgnoreIntegerWrapping) {
1633	BoundaryContext = isl_set_universe(getParamSpace());
1634	return;
1635	}
1636
1637	BoundaryContext = Affinator.getWrappingContext();
1638
1639	// The isl_set_complement operation used to create the boundary context
1640	// can possibly become very expensive. We bound the compile time of
1641	// this operation by setting a compute out.
1642	//
1643	// TODO: We can probably get around using isl_set_complement and directly
1644	// AST generate BoundaryContext.
1645	long MaxOpsOld = isl_ctx_get_max_operations(getIslCtx());
1646	isl_ctx_reset_operations(getIslCtx());
1647	isl_ctx_set_max_operations(getIslCtx(), 300000);
1648	isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_CONTINUE1);
1649
1650	BoundaryContext = isl_set_complement(BoundaryContext);
1651
1652	if (isl_ctx_last_error(getIslCtx()) == isl_error_quota) {
1653	isl_set_free(BoundaryContext);
1654	BoundaryContext = isl_set_empty(getParamSpace());
1655	}
1656
1657	isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT2);
1658	isl_ctx_reset_operations(getIslCtx());
1659	isl_ctx_set_max_operations(getIslCtx(), MaxOpsOld);
1660	BoundaryContext = isl_set_gist_params(BoundaryContext, getContext());
1661	trackAssumption(WRAPPING, BoundaryContext, DebugLoc());
1662	}
1663
1664	void Scop::addUserAssumptions(AssumptionCache &AC) {
1665	auto *R = &getRegion();
1666	auto &F = *R->getEntry()->getParent();
1667	for (auto &Assumption : AC.assumptions()) {
1668	auto *CI = dyn_cast_or_null<CallInst>(Assumption);
1669	if (!CI \|\| CI->getNumArgOperands() != 1)
1670	continue;
1671	if (!DT.dominates(CI->getParent(), R->getEntry()))
1672	continue;
1673
1674	auto *Val = CI->getArgOperand(0);
1675	std::vector<const SCEV *> Params;
1676	if (!isAffineParamConstraint(Val, R, *SE, Params)) {
1677	emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE"polly-scops", F,
1678	CI->getDebugLoc(),
1679	"Non-affine user assumption ignored.");
1680	continue;
1681	}
1682
1683	addParams(Params);
1684
1685	auto *L = LI.getLoopFor(CI->getParent());
1686	SmallVector<isl_set *, 2> ConditionSets;
1687	buildConditionSets(*this, Val, nullptr, L, Context, ConditionSets);
1688	assert(ConditionSets.size() == 2)((ConditionSets.size() == 2) ? static_cast<void> (0) : __assert_fail ("ConditionSets.size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1688, __PRETTY_FUNCTION__));
1689	isl_set_free(ConditionSets[1]);
1690
1691	auto *AssumptionCtx = ConditionSets[0];
1692	emitOptimizationRemarkAnalysis(
1693	F.getContext(), DEBUG_TYPE"polly-scops", F, CI->getDebugLoc(),
1694	"Use user assumption: " + stringFromIslObj(AssumptionCtx));
1695	Context = isl_set_intersect(Context, AssumptionCtx);
1696	}
1697	}
1698
1699	void Scop::addUserContext() {
1700	if (UserContextStr.empty())
1701	return;
1702
1703	isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str());
1704	isl_space *Space = getParamSpace();
1705	if (isl_space_dim(Space, isl_dim_param) !=
1706	isl_set_dim(UserContext, isl_dim_param)) {
1707	auto SpaceStr = isl_space_to_str(Space);
1708	errs() << "Error: the context provided in -polly-context has not the same "
1709	<< "number of dimensions than the computed context. Due to this "
1710	<< "mismatch, the -polly-context option is ignored. Please provide "
1711	<< "the context in the parameter space: " << SpaceStr << ".\n";
1712	free(SpaceStr);
1713	isl_set_free(UserContext);
1714	isl_space_free(Space);
1715	return;
1716	}
1717
1718	for (unsigned i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {
1719	auto NameContext = isl_set_get_dim_name(Context, isl_dim_param, i);
1720	auto NameUserContext = isl_set_get_dim_name(UserContext, isl_dim_param, i);
1721
1722	if (strcmp(NameContext, NameUserContext) != 0) {
1723	auto SpaceStr = isl_space_to_str(Space);
1724	errs() << "Error: the name of dimension " << i
1725	<< " provided in -polly-context "
1726	<< "is '" << NameUserContext << "', but the name in the computed "
1727	<< "context is '" << NameContext
1728	<< "'. Due to this name mismatch, "
1729	<< "the -polly-context option is ignored. Please provide "
1730	<< "the context in the parameter space: " << SpaceStr << ".\n";
1731	free(SpaceStr);
1732	isl_set_free(UserContext);
1733	isl_space_free(Space);
1734	return;
1735	}
1736
1737	UserContext =
1738	isl_set_set_dim_id(UserContext, isl_dim_param, i,
1739	isl_space_get_dim_id(Space, isl_dim_param, i));
1740	}
1741
1742	Context = isl_set_intersect(Context, UserContext);
1743	isl_space_free(Space);
1744	}
1745
1746	void Scop::buildInvariantEquivalenceClasses() {
1747	DenseMap<const SCEV , LoadInst > EquivClasses;
1748
1749	const InvariantLoadsSetTy &RIL = *SD.getRequiredInvariantLoads(&getRegion());
1750	for (LoadInst *LInst : RIL) {
1751	const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
1752
1753	LoadInst *&ClassRep = EquivClasses[PointerSCEV];
1754	if (ClassRep) {
1755	InvEquivClassVMap[LInst] = ClassRep;
1756	continue;
1757	}
1758
1759	ClassRep = LInst;
1760	InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList(),
1761	nullptr);
1762	}
1763	}
1764
1765	void Scop::buildContext() {
1766	isl_space *Space = isl_space_params_alloc(IslCtx, 0);
1767	Context = isl_set_universe(isl_space_copy(Space));
1768	AssumedContext = isl_set_universe(Space);
1769	}
1770
1771	void Scop::addParameterBounds() {
1772	for (const auto &ParamID : ParameterIds) {
1773	int dim = ParamID.second;
1774
1775	ConstantRange SRange = SE->getSignedRange(ParamID.first);
1776
1777	Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);
1778	}
1779	}
1780
1781	void Scop::realignParams() {
1782	// Add all parameters into a common model.
1783	isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size());
1784
1785	for (const auto &ParamID : ParameterIds) {
1786	const SCEV *Parameter = ParamID.first;
1787	isl_id *id = getIdForParam(Parameter);
1788	Space = isl_space_set_dim_id(Space, isl_dim_param, ParamID.second, id);
1789	}
1790
1791	// Align the parameters of all data structures to the model.
1792	Context = isl_set_align_params(Context, Space);
1793
1794	for (ScopStmt &Stmt : *this)
1795	Stmt.realignParams();
1796	}
1797
1798	static __isl_give isl_set *
1799	simplifyAssumptionContext(__isl_take isl_set *AssumptionContext,
1800	const Scop &S) {
1801	// If we modelt all blocks in the SCoP that have side effects we can simplify
1802	// the context with the constraints that are needed for anything to be
1803	// executed at all. However, if we have error blocks in the SCoP we already
1804	// assumed some parameter combinations cannot occure and removed them from the
1805	// domains, thus we cannot use the remaining domain to simplify the
1806	// assumptions.
1807	if (!S.hasErrorBlock()) {
1808	isl_set *DomainParameters = isl_union_set_params(S.getDomains());
1809	AssumptionContext =
1810	isl_set_gist_params(AssumptionContext, DomainParameters);
1811	}
1812
1813	AssumptionContext = isl_set_gist_params(AssumptionContext, S.getContext());
1814	return AssumptionContext;
1815	}
1816
1817	void Scop::simplifyContexts() {
1818	// The parameter constraints of the iteration domains give us a set of
1819	// constraints that need to hold for all cases where at least a single
1820	// statement iteration is executed in the whole scop. We now simplify the
1821	// assumed context under the assumption that such constraints hold and at
1822	// least a single statement iteration is executed. For cases where no
1823	// statement instances are executed, the assumptions we have taken about
1824	// the executed code do not matter and can be changed.
1825	//
1826	// WARNING: This only holds if the assumptions we have taken do not reduce
1827	// the set of statement instances that are executed. Otherwise we
1828	// may run into a case where the iteration domains suggest that
1829	// for a certain set of parameter constraints no code is executed,
1830	// but in the original program some computation would have been
1831	// performed. In such a case, modifying the run-time conditions and
1832	// possibly influencing the run-time check may cause certain scops
1833	// to not be executed.
1834	//
1835	// Example:
1836	//
1837	// When delinearizing the following code:
1838	//
1839	// for (long i = 0; i < 100; i++)
1840	// for (long j = 0; j < m; j++)
1841	// A[i+p][j] = 1.0;
1842	//
1843	// we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
1844	// otherwise we would access out of bound data. Now, knowing that code is
1845	// only executed for the case m >= 0, it is sufficient to assume p >= 0.
1846	AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
1847	BoundaryContext = simplifyAssumptionContext(BoundaryContext, *this);
1848	}
1849
1850	/// @brief Add the minimal/maximal access in @p Set to @p User.
1851	static isl_stat buildMinMaxAccess(__isl_take isl_set Set, void User) {
1852	Scop::MinMaxVectorTy MinMaxAccesses = (Scop::MinMaxVectorTy )User;
1853	isl_pw_multi_aff MinPMA, MaxPMA;
1854	isl_pw_aff *LastDimAff;
1855	isl_aff *OneAff;
1856	unsigned Pos;
1857
1858	// Restrict the number of parameters involved in the access as the lexmin/
1859	// lexmax computation will take too long if this number is high.
1860	//
1861	// Experiments with a simple test case using an i7 4800MQ:
1862	//
1863	// #Parameters involved \| Time (in sec)
1864	// 6 \| 0.01
1865	// 7 \| 0.04
1866	// 8 \| 0.12
1867	// 9 \| 0.40
1868	// 10 \| 1.54
1869	// 11 \| 6.78
1870	// 12 \| 30.38
1871	//
1872	if (isl_set_n_param(Set) > RunTimeChecksMaxParameters) {
1873	unsigned InvolvedParams = 0;
1874	for (unsigned u = 0, e = isl_set_n_param(Set); u < e; u++)
1875	if (isl_set_involves_dims(Set, isl_dim_param, u, 1))
1876	InvolvedParams++;
1877
1878	if (InvolvedParams > RunTimeChecksMaxParameters) {
1879	isl_set_free(Set);
1880	return isl_stat_error;
1881	}
1882	}
1883
1884	Set = isl_set_remove_divs(Set);
1885
1886	MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
1887	MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
1888
1889	MinPMA = isl_pw_multi_aff_coalesce(MinPMA);
1890	MaxPMA = isl_pw_multi_aff_coalesce(MaxPMA);
1891
1892	// Adjust the last dimension of the maximal access by one as we want to
1893	// enclose the accessed memory region by MinPMA and MaxPMA. The pointer
1894	// we test during code generation might now point after the end of the
1895	// allocated array but we will never dereference it anyway.
1896	assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&((isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && "Assumed at least one output dimension" ) ? static_cast<void> (0) : __assert_fail ("isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && \"Assumed at least one output dimension\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1897, __PRETTY_FUNCTION__))
1897	"Assumed at least one output dimension")((isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && "Assumed at least one output dimension" ) ? static_cast<void> (0) : __assert_fail ("isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && \"Assumed at least one output dimension\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1897, __PRETTY_FUNCTION__));
1898	Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;
1899	LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos);
1900	OneAff = isl_aff_zero_on_domain(
1901	isl_local_space_from_space(isl_pw_aff_get_domain_space(LastDimAff)));
1902	OneAff = isl_aff_add_constant_si(OneAff, 1);
1903	LastDimAff = isl_pw_aff_add(LastDimAff, isl_pw_aff_from_aff(OneAff));
1904	MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff);
1905
1906	MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA));
1907
1908	isl_set_free(Set);
1909	return isl_stat_ok;
1910	}
1911
1912	static __isl_give isl_set getAccessDomain(MemoryAccess MA) {
1913	isl_set *Domain = MA->getStatement()->getDomain();
1914	Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
1915	return isl_set_reset_tuple_id(Domain);
1916	}
1917
1918	/// @brief Wrapper function to calculate minimal/maximal accesses to each array.
1919	static bool calculateMinMaxAccess(__isl_take isl_union_map *Accesses,
1920	__isl_take isl_union_set *Domains,
1921	Scop::MinMaxVectorTy &MinMaxAccesses) {
1922
1923	Accesses = isl_union_map_intersect_domain(Accesses, Domains);
1924	isl_union_set *Locations = isl_union_map_range(Accesses);
1925	Locations = isl_union_set_coalesce(Locations);
1926	Locations = isl_union_set_detect_equalities(Locations);
1927	bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess,
1928	&MinMaxAccesses));
1929	isl_union_set_free(Locations);
1930	return Valid;
1931	}
1932
1933	/// @brief Helper to treat non-affine regions and basic blocks the same.
1934	///
1935	///{
1936
1937	/// @brief Return the block that is the representing block for @p RN.
1938	static inline BasicBlock getRegionNodeBasicBlock(RegionNode RN) {
1939	return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
1940	: RN->getNodeAs<BasicBlock>();
1941	}
1942
1943	/// @brief Return the @p idx'th block that is executed after @p RN.
1944	static inline BasicBlock *
1945	getRegionNodeSuccessor(RegionNode RN, TerminatorInst TI, unsigned idx) {
1946	if (RN->isSubRegion()) {
1947	assert(idx == 0)((idx == 0) ? static_cast<void> (0) : __assert_fail ("idx == 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1947, __PRETTY_FUNCTION__));
1948	return RN->getNodeAs<Region>()->getExit();
1949	}
1950	return TI->getSuccessor(idx);
1951	}
1952
1953	/// @brief Return the smallest loop surrounding @p RN.
1954	static inline Loop getRegionNodeLoop(RegionNode RN, LoopInfo &LI) {
1955	if (!RN->isSubRegion())
1956	return LI.getLoopFor(RN->getNodeAs<BasicBlock>());
1957
1958	Region *NonAffineSubRegion = RN->getNodeAs<Region>();
1959	Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
1960	while (L && NonAffineSubRegion->contains(L))
1961	L = L->getParentLoop();
1962	return L;
1963	}
1964
1965	static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
1966	if (!RN->isSubRegion())
1967	return 1;
1968
1969	unsigned NumBlocks = 0;
1970	Region *R = RN->getNodeAs<Region>();
1971	for (auto BB : R->blocks()) {
1972	(void)BB;
1973	NumBlocks++;
1974	}
1975	return NumBlocks;
1976	}
1977
1978	static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
1979	const DominatorTree &DT) {
1980	if (!RN->isSubRegion())
1981	return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
1982	for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
1983	if (isErrorBlock(*BB, R, LI, DT))
1984	return true;
1985	return false;
1986	}
1987
1988	///}
1989
1990	static inline __isl_give isl_set addDomainDimId(__isl_take isl_set Domain,
1991	unsigned Dim, Loop *L) {
1992	Domain = isl_set_lower_bound_si(Domain, isl_dim_set, Dim, -1);
1993	isl_id *DimId =
1994	isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast<void *>(L));
1995	return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId);
1996	}
1997
1998	isl_set Scop::getDomainConditions(ScopStmt Stmt) {
1999	BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock()
2000	: Stmt->getRegion()->getEntry();
2001	return getDomainConditions(BB);
2002	}
2003
2004	isl_set Scop::getDomainConditions(BasicBlock BB) {
2005	assert(DomainMap.count(BB) && "Requested BB did not have a domain")((DomainMap.count(BB) && "Requested BB did not have a domain" ) ? static_cast<void> (0) : __assert_fail ("DomainMap.count(BB) && \"Requested BB did not have a domain\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2005, __PRETTY_FUNCTION__));
2006	return isl_set_copy(DomainMap[BB]);
2007	}
2008
2009	void Scop::removeErrorBlockDomains() {
2010	auto removeDomains = [this](BasicBlock *Start) {
2011	auto BBNode = DT.getNode(Start);
2012	for (auto ErrorChild : depth_first(BBNode)) {
2013	auto ErrorChildBlock = ErrorChild->getBlock();
2014	auto CurrentDomain = DomainMap[ErrorChildBlock];
2015	auto Empty = isl_set_empty(isl_set_get_space(CurrentDomain));
2016	DomainMap[ErrorChildBlock] = Empty;
2017	isl_set_free(CurrentDomain);
2018	}
2019	};
2020
2021	SmallVector<Region *, 4> Todo = {&R};
2022
2023	while (!Todo.empty()) {
2024	auto SubRegion = Todo.back();
2025	Todo.pop_back();
2026
2027	if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
2028	for (auto &Child : *SubRegion)
2029	Todo.push_back(Child.get());
2030	continue;
2031	}
2032	if (containsErrorBlock(SubRegion->getNode(), getRegion(), LI, DT))
2033	removeDomains(SubRegion->getEntry());
2034	}
2035
2036	for (auto BB : R.blocks())
2037	if (isErrorBlock(*BB, R, LI, DT))
2038	removeDomains(BB);
2039	}
2040
2041	void Scop::buildDomains(Region *R) {
2042
2043	auto *EntryBB = R->getEntry();
2044	int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB));
2045	auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
2046
2047	Loop *L = LI.getLoopFor(EntryBB);
2048	while (LD-- >= 0) {
2049	S = addDomainDimId(S, LD + 1, L);
2050	L = L->getParentLoop();
2051	}
2052
2053	DomainMap[EntryBB] = S;
2054
2055	if (SD.isNonAffineSubRegion(R, R))
2056	return;
2057
2058	buildDomainsWithBranchConstraints(R);
2059	propagateDomainConstraints(R);
2060
2061	// Error blocks and blocks dominated by them have been assumed to never be
2062	// executed. Representing them in the Scop does not add any value. In fact,
2063	// it is likely to cause issues during construction of the ScopStmts. The
2064	// contents of error blocks have not been verfied to be expressible and
2065	// will cause problems when building up a ScopStmt for them.
2066	// Furthermore, basic blocks dominated by error blocks may reference
2067	// instructions in the error block which, if the error block is not modeled,
2068	// can themselves not be constructed properly.
2069	removeErrorBlockDomains();
2070	}
2071
2072	void Scop::buildDomainsWithBranchConstraints(Region *R) {
2073	RegionInfo &RI = *R->getRegionInfo();
2074
2075	// To create the domain for each block in R we iterate over all blocks and
2076	// subregions in R and propagate the conditions under which the current region
2077	// element is executed. To this end we iterate in reverse post order over R as
2078	// it ensures that we first visit all predecessors of a region node (either a
2079	// basic block or a subregion) before we visit the region node itself.
2080	// Initially, only the domain for the SCoP region entry block is set and from
2081	// there we propagate the current domain to all successors, however we add the
2082	// condition that the successor is actually executed next.
2083	// As we are only interested in non-loop carried constraints here we can
2084	// simply skip loop back edges.
2085
2086	ReversePostOrderTraversal<Region *> RTraversal(R);
2087	for (auto *RN : RTraversal) {
2088
2089	// Recurse for affine subregions but go on for basic blocks and non-affine
2090	// subregions.
2091	if (RN->isSubRegion()) {
2092	Region *SubRegion = RN->getNodeAs<Region>();
2093	if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
2094	buildDomainsWithBranchConstraints(SubRegion);
2095	continue;
2096	}
2097	}
2098
2099	if (containsErrorBlock(RN, getRegion(), LI, DT))
2100	HasErrorBlock = true;
2101
2102	BasicBlock *BB = getRegionNodeBasicBlock(RN);
2103	TerminatorInst *TI = BB->getTerminator();
2104
2105	if (isa<UnreachableInst>(TI))
2106	continue;
2107
2108	isl_set *Domain = DomainMap.lookup(BB);
2109	if (!Domain) {
2110	DEBUG(dbgs() << "\tSkip: " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0)
2111	<< ", it is only reachable from error blocks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0);
2112	continue;
2113	}
2114
2115	DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tVisit: " << BB-> getName() << " : " << Domain << "\n"; } } while (0);
2116
2117	Loop *BBLoop = getRegionNodeLoop(RN, LI);
2118	int BBLoopDepth = getRelativeLoopDepth(BBLoop);
2119
2120	// Build the condition sets for the successor nodes of the current region
2121	// node. If it is a non-affine subregion we will always execute the single
2122	// exit node, hence the single entry node domain is the condition set. For
2123	// basic blocks we use the helper function buildConditionSets.
2124	SmallVector<isl_set *, 8> ConditionSets;
2125	if (RN->isSubRegion())
2126	ConditionSets.push_back(isl_set_copy(Domain));
2127	else
2128	buildConditionSets(*this, TI, BBLoop, Domain, ConditionSets);
2129
2130	// Now iterate over the successors and set their initial domain based on
2131	// their condition set. We skip back edges here and have to be careful when
2132	// we leave a loop not to keep constraints over a dimension that doesn't
2133	// exist anymore.
2134	assert(RN->isSubRegion() \|\| TI->getNumSuccessors() == ConditionSets.size())((RN->isSubRegion() \|\| TI->getNumSuccessors() == ConditionSets .size()) ? static_cast<void> (0) : __assert_fail ("RN->isSubRegion() \|\| TI->getNumSuccessors() == ConditionSets.size()" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2134, __PRETTY_FUNCTION__));
2135	for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
2136	isl_set *CondSet = ConditionSets[u];
2137	BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
2138
2139	// Skip back edges.
2140	if (DT.dominates(SuccBB, BB)) {
2141	isl_set_free(CondSet);
2142	continue;
2143	}
2144
2145	// Do not adjust the number of dimensions if we enter a boxed loop or are
2146	// in a non-affine subregion or if the surrounding loop stays the same.
2147	Loop *SuccBBLoop = LI.getLoopFor(SuccBB);
2148	Region *SuccRegion = RI.getRegionFor(SuccBB);
2149	if (SD.isNonAffineSubRegion(SuccRegion, &getRegion()))
2150	while (SuccBBLoop && SuccRegion->contains(SuccBBLoop))
2151	SuccBBLoop = SuccBBLoop->getParentLoop();
2152
2153	if (BBLoop != SuccBBLoop) {
2154
2155	// Check if the edge to SuccBB is a loop entry or exit edge. If so
2156	// adjust the dimensionality accordingly. Lastly, if we leave a loop
2157	// and enter a new one we need to drop the old constraints.
2158	int SuccBBLoopDepth = getRelativeLoopDepth(SuccBBLoop);
2159	unsigned LoopDepthDiff = std::abs(BBLoopDepth - SuccBBLoopDepth);
2160	if (BBLoopDepth > SuccBBLoopDepth) {
2161	CondSet = isl_set_project_out(CondSet, isl_dim_set,
2162	isl_set_n_dim(CondSet) - LoopDepthDiff,
2163	LoopDepthDiff);
2164	} else if (SuccBBLoopDepth > BBLoopDepth) {
2165	assert(LoopDepthDiff == 1)((LoopDepthDiff == 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2165, __PRETTY_FUNCTION__));
2166	CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
2167	CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
2168	} else if (BBLoopDepth >= 0) {
2169	assert(LoopDepthDiff <= 1)((LoopDepthDiff <= 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff <= 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2169, __PRETTY_FUNCTION__));
2170	CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1);
2171	CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
2172	CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
2173	}
2174	}
2175
2176	// Set the domain for the successor or merge it with an existing domain in
2177	// case there are multiple paths (without loop back edges) to the
2178	// successor block.
2179	isl_set *&SuccDomain = DomainMap[SuccBB];
2180	if (!SuccDomain)
2181	SuccDomain = CondSet;
2182	else
2183	SuccDomain = isl_set_union(SuccDomain, CondSet);
2184
2185	SuccDomain = isl_set_coalesce(SuccDomain);
2186	if (isl_set_n_basic_set(SuccDomain) > MaxConjunctsInDomain) {
2187	auto *Empty = isl_set_empty(isl_set_get_space(SuccDomain));
2188	isl_set_free(SuccDomain);
2189	SuccDomain = Empty;
2190	invalidate(ERROR_DOMAINCONJUNCTS, DebugLoc());
2191	}
2192	DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSet SuccBB: " << SuccBB ->getName() << " : " << SuccDomain << "\n" ; } } while (0)
2193	<< SuccDomain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSet SuccBB: " << SuccBB ->getName() << " : " << SuccDomain << "\n" ; } } while (0);
2194	}
2195	}
2196	}
2197
2198	/// @brief Return the domain for @p BB wrt @p DomainMap.
2199	///
2200	/// This helper function will lookup @p BB in @p DomainMap but also handle the
2201	/// case where @p BB is contained in a non-affine subregion using the region
2202	/// tree obtained by @p RI.
2203	static __isl_give isl_set *
2204	getDomainForBlock(BasicBlock BB, DenseMap<BasicBlock , isl_set *> &DomainMap,
2205	RegionInfo &RI) {
2206	auto DIt = DomainMap.find(BB);
2207	if (DIt != DomainMap.end())
2208	return isl_set_copy(DIt->getSecond());
2209
2210	Region *R = RI.getRegionFor(BB);
2211	while (R->getEntry() == BB)
2212	R = R->getParent();
2213	return getDomainForBlock(R->getEntry(), DomainMap, RI);
2214	}
2215
2216	void Scop::propagateDomainConstraints(Region *R) {
2217	// Iterate over the region R and propagate the domain constrains from the
2218	// predecessors to the current node. In contrast to the
2219	// buildDomainsWithBranchConstraints function, this one will pull the domain
2220	// information from the predecessors instead of pushing it to the successors.
2221	// Additionally, we assume the domains to be already present in the domain
2222	// map here. However, we iterate again in reverse post order so we know all
2223	// predecessors have been visited before a block or non-affine subregion is
2224	// visited.
2225
2226	// The set of boxed loops (loops in non-affine subregions) for this SCoP.
2227	auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
2228
2229	ReversePostOrderTraversal<Region *> RTraversal(R);
2230	for (auto *RN : RTraversal) {
2231
2232	// Recurse for affine subregions but go on for basic blocks and non-affine
2233	// subregions.
2234	if (RN->isSubRegion()) {
2235	Region *SubRegion = RN->getNodeAs<Region>();
2236	if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
2237	propagateDomainConstraints(SubRegion);
2238	continue;
2239	}
2240	}
2241
2242	// Get the domain for the current block and check if it was initialized or
2243	// not. The only way it was not is if this block is only reachable via error
2244	// blocks, thus will not be executed under the assumptions we make. Such
2245	// blocks have to be skipped as their predecessors might not have domains
2246	// either. It would not benefit us to compute the domain anyway, only the
2247	// domains of the error blocks that are reachable from non-error blocks
2248	// are needed to generate assumptions.
2249	BasicBlock *BB = getRegionNodeBasicBlock(RN);
2250	isl_set *&Domain = DomainMap[BB];
2251	if (!Domain) {
2252	DEBUG(dbgs() << "\tSkip: " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0)
2253	<< ", it is only reachable from error blocks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0);
2254	DomainMap.erase(BB);
2255	continue;
2256	}
2257	DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tVisit: " << BB-> getName() << " : " << Domain << "\n"; } } while (0);
2258
2259	Loop *BBLoop = getRegionNodeLoop(RN, LI);
2260	int BBLoopDepth = getRelativeLoopDepth(BBLoop);
2261
2262	isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain));
2263	for (auto *PredBB : predecessors(BB)) {
2264
2265	// Skip backedges
2266	if (DT.dominates(BB, PredBB))
2267	continue;
2268
2269	isl_set *PredBBDom = nullptr;
2270
2271	// Handle the SCoP entry block with its outside predecessors.
2272	if (!getRegion().contains(PredBB))
2273	PredBBDom = isl_set_universe(isl_set_get_space(PredDom));
2274
2275	if (!PredBBDom) {
2276	// Determine the loop depth of the predecessor and adjust its domain to
2277	// the domain of the current block. This can mean we have to:
2278	// o) Drop a dimension if this block is the exit of a loop, not the
2279	// header of a new loop and the predecessor was part of the loop.
2280	// o) Add an unconstrainted new dimension if this block is the header
2281	// of a loop and the predecessor is not part of it.
2282	// o) Drop the information about the innermost loop dimension when the
2283	// predecessor and the current block are surrounded by different
2284	// loops in the same depth.
2285	PredBBDom = getDomainForBlock(PredBB, DomainMap, *R->getRegionInfo());
2286	Loop *PredBBLoop = LI.getLoopFor(PredBB);
2287	while (BoxedLoops.count(PredBBLoop))
2288	PredBBLoop = PredBBLoop->getParentLoop();
2289
2290	int PredBBLoopDepth = getRelativeLoopDepth(PredBBLoop);
2291	unsigned LoopDepthDiff = std::abs(BBLoopDepth - PredBBLoopDepth);
2292	if (BBLoopDepth < PredBBLoopDepth)
2293	PredBBDom = isl_set_project_out(
2294	PredBBDom, isl_dim_set, isl_set_n_dim(PredBBDom) - LoopDepthDiff,
2295	LoopDepthDiff);
2296	else if (PredBBLoopDepth < BBLoopDepth) {
2297	assert(LoopDepthDiff == 1)((LoopDepthDiff == 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2297, __PRETTY_FUNCTION__));
2298	PredBBDom = isl_set_add_dims(PredBBDom, isl_dim_set, 1);
2299	} else if (BBLoop != PredBBLoop && BBLoopDepth >= 0) {
2300	assert(LoopDepthDiff <= 1)((LoopDepthDiff <= 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff <= 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2300, __PRETTY_FUNCTION__));
2301	PredBBDom = isl_set_drop_constraints_involving_dims(
2302	PredBBDom, isl_dim_set, BBLoopDepth, 1);
2303	}
2304	}
2305
2306	PredDom = isl_set_union(PredDom, PredBBDom);
2307	}
2308
2309	// Under the union of all predecessor conditions we can reach this block.
2310	Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom));
2311
2312	if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop))
2313	addLoopBoundsToHeaderDomain(BBLoop);
2314
2315	// Add assumptions for error blocks.
2316	if (containsErrorBlock(RN, getRegion(), LI, DT)) {
2317	IsOptimized = true;
2318	isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
2319	addAssumption(ERRORBLOCK, isl_set_complement(DomPar),
2320	BB->getTerminator()->getDebugLoc());
2321	}
2322	}
2323	}
2324
2325	/// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim
2326	/// is incremented by one and all other dimensions are equal, e.g.,
2327	/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
2328	/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
2329	static __isl_give isl_map *
2330	createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) {
2331	auto *MapSpace = isl_space_map_from_set(SetSpace);
2332	auto *NextIterationMap = isl_map_universe(isl_space_copy(MapSpace));
2333	for (unsigned u = 0; u < isl_map_n_in(NextIterationMap); u++)
2334	if (u != Dim)
2335	NextIterationMap =
2336	isl_map_equate(NextIterationMap, isl_dim_in, u, isl_dim_out, u);
2337	auto *C = isl_constraint_alloc_equality(isl_local_space_from_space(MapSpace));
2338	C = isl_constraint_set_constant_si(C, 1);
2339	C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1);
2340	C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1);
2341	NextIterationMap = isl_map_add_constraint(NextIterationMap, C);
2342	return NextIterationMap;
2343	}
2344
2345	void Scop::addLoopBoundsToHeaderDomain(Loop *L) {
2346	int LoopDepth = getRelativeLoopDepth(L);
2347	assert(LoopDepth >= 0 && "Loop in region should have at least depth one")((LoopDepth >= 0 && "Loop in region should have at least depth one" ) ? static_cast<void> (0) : __assert_fail ("LoopDepth >= 0 && \"Loop in region should have at least depth one\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2347, __PRETTY_FUNCTION__));
2348
2349	BasicBlock *HeaderBB = L->getHeader();
2350	assert(DomainMap.count(HeaderBB))((DomainMap.count(HeaderBB)) ? static_cast<void> (0) : __assert_fail ("DomainMap.count(HeaderBB)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2350, __PRETTY_FUNCTION__));
2351	isl_set *&HeaderBBDom = DomainMap[HeaderBB];
2352
2353	isl_map *NextIterationMap =
2354	createNextIterationMap(isl_set_get_space(HeaderBBDom), LoopDepth);
2355
2356	isl_set *UnionBackedgeCondition =
2357	isl_set_empty(isl_set_get_space(HeaderBBDom));
2358
2359	SmallVector<llvm::BasicBlock *, 4> LatchBlocks;
2360	L->getLoopLatches(LatchBlocks);
2361
2362	for (BasicBlock *LatchBB : LatchBlocks) {
2363
2364	// If the latch is only reachable via error statements we skip it.
2365	isl_set *LatchBBDom = DomainMap.lookup(LatchBB);
2366	if (!LatchBBDom)
2367	continue;
2368
2369	isl_set *BackedgeCondition = nullptr;
2370
2371	TerminatorInst *TI = LatchBB->getTerminator();
2372	BranchInst *BI = dyn_cast<BranchInst>(TI);
2373	if (BI && BI->isUnconditional())
2374	BackedgeCondition = isl_set_copy(LatchBBDom);
2375	else {
2376	SmallVector<isl_set *, 8> ConditionSets;
2377	int idx = BI->getSuccessor(0) != HeaderBB;
2378	buildConditionSets(*this, TI, L, LatchBBDom, ConditionSets);
2379
2380	// Free the non back edge condition set as we do not need it.
2381	isl_set_free(ConditionSets[1 - idx]);
2382
2383	BackedgeCondition = ConditionSets[idx];
2384	}
2385
2386	int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
2387	assert(LatchLoopDepth >= LoopDepth)((LatchLoopDepth >= LoopDepth) ? static_cast<void> ( 0) : __assert_fail ("LatchLoopDepth >= LoopDepth", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2387, __PRETTY_FUNCTION__));
2388	BackedgeCondition =
2389	isl_set_project_out(BackedgeCondition, isl_dim_set, LoopDepth + 1,
2390	LatchLoopDepth - LoopDepth);
2391	UnionBackedgeCondition =
2392	isl_set_union(UnionBackedgeCondition, BackedgeCondition);
2393	}
2394
2395	isl_map *ForwardMap = isl_map_lex_le(isl_set_get_space(HeaderBBDom));
2396	for (int i = 0; i < LoopDepth; i++)
2397	ForwardMap = isl_map_equate(ForwardMap, isl_dim_in, i, isl_dim_out, i);
2398
2399	isl_set *UnionBackedgeConditionComplement =
2400	isl_set_complement(UnionBackedgeCondition);
2401	UnionBackedgeConditionComplement = isl_set_lower_bound_si(
2402	UnionBackedgeConditionComplement, isl_dim_set, LoopDepth, 0);
2403	UnionBackedgeConditionComplement =
2404	isl_set_apply(UnionBackedgeConditionComplement, ForwardMap);
2405	HeaderBBDom = isl_set_subtract(HeaderBBDom, UnionBackedgeConditionComplement);
2406	HeaderBBDom = isl_set_apply(HeaderBBDom, NextIterationMap);
2407
2408	auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
2409	HeaderBBDom = Parts.second;
2410
2411	// Check if there is a <nsw> tagged AddRec for this loop and if so do not add
2412	// the bounded assumptions to the context as they are already implied by the
2413	// <nsw> tag.
2414	if (Affinator.hasNSWAddRecForLoop(L)) {
2415	isl_set_free(Parts.first);
2416	return;
2417	}
2418
2419	isl_set *UnboundedCtx = isl_set_params(Parts.first);
2420	isl_set *BoundedCtx = isl_set_complement(UnboundedCtx);
2421	addAssumption(INFINITELOOP, BoundedCtx,
2422	HeaderBB->getTerminator()->getDebugLoc());
2423	}
2424
2425	void Scop::buildAliasChecks(AliasAnalysis &AA) {
2426	if (!PollyUseRuntimeAliasChecks)
2427	return;
2428
2429	if (buildAliasGroups(AA))
2430	return;
2431
2432	// If a problem occurs while building the alias groups we need to delete
2433	// this SCoP and pretend it wasn't valid in the first place. To this end
2434	// we make the assumed context infeasible.
2435	invalidate(ALIASING, DebugLoc());
2436
2437	DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0)
2438	<< " could not be created as the number of parameters involved "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0)
2439	"is too high. The SCoP will be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0)
2440	"dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0)
2441	"the maximal number of parameters but be advised that the "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0)
2442	"compile time might increase exponentially.\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0);
2443	}
2444
2445	bool Scop::buildAliasGroups(AliasAnalysis &AA) {
2446	// To create sound alias checks we perform the following steps:
2447	// o) Use the alias analysis and an alias set tracker to build alias sets
2448	// for all memory accesses inside the SCoP.
2449	// o) For each alias set we then map the aliasing pointers back to the
2450	// memory accesses we know, thus obtain groups of memory accesses which
2451	// might alias.
2452	// o) We divide each group based on the domains of the minimal/maximal
2453	// accesses. That means two minimal/maximal accesses are only in a group
2454	// if their access domains intersect, otherwise they are in different
2455	// ones.
2456	// o) We partition each group into read only and non read only accesses.
2457	// o) For each group with more than one base pointer we then compute minimal
2458	// and maximal accesses to each array of a group in read only and non
2459	// read only partitions separately.
2460	using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
2461
2462	AliasSetTracker AST(AA);
2463
2464	DenseMap<Value , MemoryAccess > PtrToAcc;
2465	DenseSet<Value *> HasWriteAccess;
2466	for (ScopStmt &Stmt : *this) {
2467
2468	// Skip statements with an empty domain as they will never be executed.
2469	isl_set *StmtDomain = Stmt.getDomain();
2470	bool StmtDomainEmpty = isl_set_is_empty(StmtDomain);
2471	isl_set_free(StmtDomain);
2472	if (StmtDomainEmpty)
2473	continue;
2474
2475	for (MemoryAccess *MA : Stmt) {
2476	if (MA->isScalarKind())
2477	continue;
2478	if (!MA->isRead())
2479	HasWriteAccess.insert(MA->getBaseAddr());
2480	Instruction *Acc = MA->getAccessInstruction();
2481	PtrToAcc[getPointerOperand(*Acc)] = MA;
2482	AST.add(Acc);
2483	}
2484	}
2485
2486	SmallVector<AliasGroupTy, 4> AliasGroups;
2487	for (AliasSet &AS : AST) {
2488	if (AS.isMustAlias() \|\| AS.isForwardingAliasSet())
2489	continue;
2490	AliasGroupTy AG;
2491	for (auto PR : AS)
2492	AG.push_back(PtrToAcc[PR.getValue()]);
2493	assert(AG.size() > 1 &&((AG.size() > 1 && "Alias groups should contain at least two accesses" ) ? static_cast<void> (0) : __assert_fail ("AG.size() > 1 && \"Alias groups should contain at least two accesses\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2494, __PRETTY_FUNCTION__))
2494	"Alias groups should contain at least two accesses")((AG.size() > 1 && "Alias groups should contain at least two accesses" ) ? static_cast<void> (0) : __assert_fail ("AG.size() > 1 && \"Alias groups should contain at least two accesses\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2494, __PRETTY_FUNCTION__));
2495	AliasGroups.push_back(std::move(AG));
2496	}
2497
2498	// Split the alias groups based on their domain.
2499	for (unsigned u = 0; u < AliasGroups.size(); u++) {
2500	AliasGroupTy NewAG;
2501	AliasGroupTy &AG = AliasGroups[u];
2502	AliasGroupTy::iterator AGI = AG.begin();
2503	isl_set AGDomain = getAccessDomain(AGI);
2504	while (AGI != AG.end()) {
2505	MemoryAccess MA = AGI;
2506	isl_set *MADomain = getAccessDomain(MA);
2507	if (isl_set_is_disjoint(AGDomain, MADomain)) {
2508	NewAG.push_back(MA);
2509	AGI = AG.erase(AGI);
2510	isl_set_free(MADomain);
2511	} else {
2512	AGDomain = isl_set_union(AGDomain, MADomain);
2513	AGI++;
2514	}
2515	}
2516	if (NewAG.size() > 1)
2517	AliasGroups.push_back(std::move(NewAG));
2518	isl_set_free(AGDomain);
2519	}
2520
2521	auto &F = *getRegion().getEntry()->getParent();
2522	MapVector<const Value , SmallPtrSet<MemoryAccess , 8>> ReadOnlyPairs;
2523	SmallPtrSet<const Value *, 4> NonReadOnlyBaseValues;
2524	for (AliasGroupTy &AG : AliasGroups) {
2525	NonReadOnlyBaseValues.clear();
2526	ReadOnlyPairs.clear();
2527
2528	if (AG.size() < 2) {
2529	AG.clear();
2530	continue;
2531	}
2532
2533	for (auto II = AG.begin(); II != AG.end();) {
2534	emitOptimizationRemarkAnalysis(
2535	F.getContext(), DEBUG_TYPE"polly-scops", F,
2536	(*II)->getAccessInstruction()->getDebugLoc(),
2537	"Possibly aliasing pointer, use restrict keyword.");
2538
2539	Value BaseAddr = (II)->getBaseAddr();
2540	if (HasWriteAccess.count(BaseAddr)) {
2541	NonReadOnlyBaseValues.insert(BaseAddr);
2542	II++;
2543	} else {
2544	ReadOnlyPairs[BaseAddr].insert(*II);
2545	II = AG.erase(II);
2546	}
2547	}
2548
2549	// If we don't have read only pointers check if there are at least two
2550	// non read only pointers, otherwise clear the alias group.
2551	if (ReadOnlyPairs.empty() && NonReadOnlyBaseValues.size() <= 1) {
2552	AG.clear();
2553	continue;
2554	}
2555
2556	// If we don't have non read only pointers clear the alias group.
2557	if (NonReadOnlyBaseValues.empty()) {
2558	AG.clear();
2559	continue;
2560	}
2561
2562	// Calculate minimal and maximal accesses for non read only accesses.
2563	MinMaxAliasGroups.emplace_back();
2564	MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
2565	MinMaxVectorTy &MinMaxAccessesNonReadOnly = pair.first;
2566	MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
2567	MinMaxAccessesNonReadOnly.reserve(AG.size());
2568
2569	isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
2570
2571	// AG contains only non read only accesses.
2572	for (MemoryAccess *MA : AG)
2573	Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
2574
2575	bool Valid = calculateMinMaxAccess(Accesses, getDomains(),
2576	MinMaxAccessesNonReadOnly);
2577
2578	// Bail out if the number of values we need to compare is too large.
2579	// This is important as the number of comparisions grows quadratically with
2580	// the number of values we need to compare.
2581	if (!Valid \|\| (MinMaxAccessesNonReadOnly.size() + !ReadOnlyPairs.empty() >
2582	RunTimeChecksMaxArraysPerGroup))
2583	return false;
2584
2585	// Calculate minimal and maximal accesses for read only accesses.
2586	MinMaxAccessesReadOnly.reserve(ReadOnlyPairs.size());
2587	Accesses = isl_union_map_empty(getParamSpace());
2588
2589	for (const auto &ReadOnlyPair : ReadOnlyPairs)
2590	for (MemoryAccess *MA : ReadOnlyPair.second)
2591	Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
2592
2593	Valid =
2594	calculateMinMaxAccess(Accesses, getDomains(), MinMaxAccessesReadOnly);
2595
2596	if (!Valid)
2597	return false;
2598	}
2599
2600	return true;
2601	}
2602
2603	/// @brief Get the smallest loop that contains @p R but is not in @p R.
2604	static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) {
2605	// Start with the smallest loop containing the entry and expand that
2606	// loop until it contains all blocks in the region. If there is a loop
2607	// containing all blocks in the region check if it is itself contained
2608	// and if so take the parent loop as it will be the smallest containing
2609	// the region but not contained by it.
2610	Loop *L = LI.getLoopFor(R.getEntry());
2611	while (L) {
2612	bool AllContained = true;
2613	for (auto *BB : R.blocks())
2614	AllContained &= L->contains(BB);
2615	if (AllContained)
2616	break;
2617	L = L->getParentLoop();
2618	}
2619
2620	return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr;
2621	}
2622
2623	static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
2624	ScopDetection &SD) {
2625
2626	const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD.getBoxedLoops(&R);
2627
2628	unsigned MinLD = INT_MAX2147483647, MaxLD = 0;
2629	for (BasicBlock *BB : R.blocks()) {
2630	if (Loop *L = LI.getLoopFor(BB)) {
2631	if (!R.contains(L))
2632	continue;
2633	if (BoxedLoops && BoxedLoops->count(L))
2634	continue;
2635	unsigned LD = L->getLoopDepth();
2636	MinLD = std::min(MinLD, LD);
2637	MaxLD = std::max(MaxLD, LD);
2638	}
2639	}
2640
2641	// Handle the case that there is no loop in the SCoP first.
2642	if (MaxLD == 0)
2643	return 1;
2644
2645	assert(MinLD >= 1 && "Minimal loop depth should be at least one")((MinLD >= 1 && "Minimal loop depth should be at least one" ) ? static_cast<void> (0) : __assert_fail ("MinLD >= 1 && \"Minimal loop depth should be at least one\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2645, __PRETTY_FUNCTION__));
2646	assert(MaxLD >= MinLD &&((MaxLD >= MinLD && "Maximal loop depth was smaller than mininaml loop depth?" ) ? static_cast<void> (0) : __assert_fail ("MaxLD >= MinLD && \"Maximal loop depth was smaller than mininaml loop depth?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2647, __PRETTY_FUNCTION__))
2647	"Maximal loop depth was smaller than mininaml loop depth?")((MaxLD >= MinLD && "Maximal loop depth was smaller than mininaml loop depth?" ) ? static_cast<void> (0) : __assert_fail ("MaxLD >= MinLD && \"Maximal loop depth was smaller than mininaml loop depth?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2647, __PRETTY_FUNCTION__));
2648	return MaxLD - MinLD + 1;
2649	}
2650
2651	Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
2652	ScalarEvolution &ScalarEvolution, DominatorTree &DT, LoopInfo &LI,
2653	isl_ctx *Context, unsigned MaxLoopDepth)
2654	: LI(LI), DT(DT), SE(&ScalarEvolution), SD(SD), R(R),
2655	AccFuncMap(AccFuncMap), IsOptimized(false),
2656	HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
2657	MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Context(nullptr),
2658	Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr),
2659	Schedule(nullptr) {}
2660
2661	void Scop::init(AliasAnalysis &AA, AssumptionCache &AC) {
2662	buildContext();
2663	addUserAssumptions(AC);
2664	buildInvariantEquivalenceClasses();
2665
2666	buildDomains(&R);
2667
2668	// Remove empty and ignored statements.
2669	// Exit early in case there are no executable statements left in this scop.
2670	simplifySCoP(true);
2671	if (Stmts.empty())
2672	return;
2673
2674	// The ScopStmts now have enough information to initialize themselves.
2675	for (ScopStmt &Stmt : Stmts)
2676	Stmt.init();
2677
2678	buildSchedule();
2679
2680	if (isl_set_is_empty(AssumedContext))
2681	return;
2682
2683	updateAccessDimensionality();
2684	realignParams();
2685	addParameterBounds();
2686	addUserContext();
2687	buildBoundaryContext();
2688	simplifyContexts();
2689	buildAliasChecks(AA);
2690
2691	hoistInvariantLoads();
2692	simplifySCoP(false);
2693	}
2694
2695	Scop::~Scop() {
2696	isl_set_free(Context);
2697	isl_set_free(AssumedContext);
2698	isl_set_free(BoundaryContext);
2699	isl_schedule_free(Schedule);
2700
2701	for (auto It : DomainMap)
2702	isl_set_free(It.second);
2703
2704	// Free the alias groups
2705	for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
2706	for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
2707	isl_pw_multi_aff_free(MMA.first);
2708	isl_pw_multi_aff_free(MMA.second);
2709	}
2710	for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
2711	isl_pw_multi_aff_free(MMA.first);
2712	isl_pw_multi_aff_free(MMA.second);
2713	}
2714	}
2715
2716	for (const auto &IAClass : InvariantEquivClasses)
2717	isl_set_free(std::get<2>(IAClass));
2718	}
2719
2720	void Scop::updateAccessDimensionality() {
2721	for (auto &Stmt : *this)
2722	for (auto &Access : Stmt)
2723	Access->updateDimensionality();
2724	}
2725
2726	void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
2727	for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
2728	ScopStmt &Stmt = *StmtIt;
2729	RegionNode *RN = Stmt.isRegionStmt()
2730	? Stmt.getRegion()->getNode()
2731	: getRegion().getBBNode(Stmt.getBasicBlock());
2732
2733	bool RemoveStmt = StmtIt->isEmpty();
2734	if (!RemoveStmt)
2735	RemoveStmt = isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]);
2736	if (!RemoveStmt)
2737	RemoveStmt = (RemoveIgnoredStmts && isIgnored(RN));
2738
2739	// Remove read only statements only after invariant loop hoisting.
2740	if (!RemoveStmt && !RemoveIgnoredStmts) {
2741	bool OnlyRead = true;
2742	for (MemoryAccess *MA : Stmt) {
2743	if (MA->isRead())
2744	continue;
2745
2746	OnlyRead = false;
2747	break;
2748	}
2749
2750	RemoveStmt = OnlyRead;
2751	}
2752
2753	if (RemoveStmt) {
2754	// Remove the statement because it is unnecessary.
2755	if (Stmt.isRegionStmt())
2756	for (BasicBlock *BB : Stmt.getRegion()->blocks())
2757	StmtMap.erase(BB);
2758	else
2759	StmtMap.erase(Stmt.getBasicBlock());
2760
2761	StmtIt = Stmts.erase(StmtIt);
2762	continue;
2763	}
2764
2765	StmtIt++;
2766	}
2767	}
2768
2769	const InvariantEquivClassTy Scop::lookupInvariantEquivClass(Value Val) const {
2770	LoadInst *LInst = dyn_cast<LoadInst>(Val);
2771	if (!LInst)
2772	return nullptr;
2773
2774	if (Value *Rep = InvEquivClassVMap.lookup(LInst))
2775	LInst = cast<LoadInst>(Rep);
2776
2777	const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
2778	for (auto &IAClass : InvariantEquivClasses)
2779	if (PointerSCEV == std::get<0>(IAClass))
2780	return &IAClass;
2781
2782	return nullptr;
2783	}
2784
2785	void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
2786
2787	// Get the context under which the statement is executed.
2788	isl_set *DomainCtx = isl_set_params(Stmt.getDomain());
2789	DomainCtx = isl_set_remove_redundancies(DomainCtx);
2790	DomainCtx = isl_set_detect_equalities(DomainCtx);
2791	DomainCtx = isl_set_coalesce(DomainCtx);
2792
2793	// Project out all parameters that relate to loads in the statement. Otherwise
2794	// we could have cyclic dependences on the constraints under which the
2795	// hoisted loads are executed and we could not determine an order in which to
2796	// pre-load them. This happens because not only lower bounds are part of the
2797	// domain but also upper bounds.
2798	for (MemoryAccess *MA : InvMAs) {
2799	Instruction *AccInst = MA->getAccessInstruction();
2800	if (SE->isSCEVable(AccInst->getType())) {
2801	SetVector<Value *> Values;
2802	for (const SCEV *Parameter : Parameters) {
2803	Values.clear();
2804	findValues(Parameter, Values);
2805	if (!Values.count(AccInst))
2806	continue;
2807
2808	if (isl_id *ParamId = getIdForParam(Parameter)) {
2809	int Dim = isl_set_find_dim_by_id(DomainCtx, isl_dim_param, ParamId);
2810	DomainCtx = isl_set_eliminate(DomainCtx, isl_dim_param, Dim, 1);
2811	isl_id_free(ParamId);
2812	}
2813	}
2814	}
2815	}
2816
2817	for (MemoryAccess *MA : InvMAs) {
2818	// Check for another invariant access that accesses the same location as
2819	// MA and if found consolidate them. Otherwise create a new equivalence
2820	// class at the end of InvariantEquivClasses.
2821	LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
2822	const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
2823
2824	bool Consolidated = false;
2825	for (auto &IAClass : InvariantEquivClasses) {
2826	if (PointerSCEV != std::get<0>(IAClass))
2827	continue;
2828
2829	Consolidated = true;
2830
2831	// Add MA to the list of accesses that are in this class.
2832	auto &MAs = std::get<1>(IAClass);
2833	MAs.push_front(MA);
2834
2835	// Unify the execution context of the class and this statement.
2836	isl_set *&IAClassDomainCtx = std::get<2>(IAClass);
2837	if (IAClassDomainCtx)
2838	IAClassDomainCtx = isl_set_coalesce(
2839	isl_set_union(IAClassDomainCtx, isl_set_copy(DomainCtx)));
2840	else
2841	IAClassDomainCtx = isl_set_copy(DomainCtx);
2842	break;
2843	}
2844
2845	if (Consolidated)
2846	continue;
2847
2848	// If we did not consolidate MA, thus did not find an equivalence class
2849	// for it, we create a new one.
2850	InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList{MA},
2851	isl_set_copy(DomainCtx));
2852	}
2853
2854	isl_set_free(DomainCtx);
2855	}
2856
2857	bool Scop::isHoistableAccess(MemoryAccess *Access,
2858	__isl_keep isl_union_map *Writes) {
2859	// TODO: Loads that are not loop carried, hence are in a statement with
2860	// zero iterators, are by construction invariant, though we
2861	// currently "hoist" them anyway. This is necessary because we allow
2862	// them to be treated as parameters (e.g., in conditions) and our code
2863	// generation would otherwise use the old value.
2864
2865	auto &Stmt = *Access->getStatement();
2866	BasicBlock *BB =
2867	Stmt.isBlockStmt() ? Stmt.getBasicBlock() : Stmt.getRegion()->getEntry();
2868
2869	if (Access->isScalarKind() \|\| Access->isWrite() \|\| !Access->isAffine())
2870	return false;
2871
2872	// Skip accesses that have an invariant base pointer which is defined but
2873	// not loaded inside the SCoP. This can happened e.g., if a readnone call
2874	// returns a pointer that is used as a base address. However, as we want
2875	// to hoist indirect pointers, we allow the base pointer to be defined in
2876	// the region if it is also a memory access. Each ScopArrayInfo object
2877	// that has a base pointer origin has a base pointer that is loaded and
2878	// that it is invariant, thus it will be hoisted too. However, if there is
2879	// no base pointer origin we check that the base pointer is defined
2880	// outside the region.
2881	const ScopArrayInfo *SAI = Access->getScopArrayInfo();
2882	while (auto *BasePtrOriginSAI = SAI->getBasePtrOriginSAI())
2883	SAI = BasePtrOriginSAI;
2884
2885	if (auto *BasePtrInst = dyn_cast<Instruction>(SAI->getBasePtr()))
2886	if (R.contains(BasePtrInst))
2887	return false;
2888
2889	// Skip accesses in non-affine subregions as they might not be executed
2890	// under the same condition as the entry of the non-affine subregion.
2891	if (BB != Access->getAccessInstruction()->getParent())
2892	return false;
2893
2894	isl_map *AccessRelation = Access->getAccessRelation();
2895
2896	// Skip accesses that have an empty access relation. These can be caused
2897	// by multiple offsets with a type cast in-between that cause the overall
2898	// byte offset to be not divisible by the new types sizes.
2899	if (isl_map_is_empty(AccessRelation)) {
2900	isl_map_free(AccessRelation);
2901	return false;
2902	}
2903
2904	if (isl_map_involves_dims(AccessRelation, isl_dim_in, 0,
2905	Stmt.getNumIterators())) {
2906	isl_map_free(AccessRelation);
2907	return false;
2908	}
2909
2910	AccessRelation = isl_map_intersect_domain(AccessRelation, Stmt.getDomain());
2911	isl_set *AccessRange = isl_map_range(AccessRelation);
2912
2913	isl_union_map *Written = isl_union_map_intersect_range(
2914	isl_union_map_copy(Writes), isl_union_set_from_set(AccessRange));
2915	bool IsWritten = !isl_union_map_is_empty(Written);
2916	isl_union_map_free(Written);
2917
2918	if (IsWritten)
2919	return false;
2920
2921	return true;
2922	}
2923
2924	void Scop::verifyInvariantLoads() {
2925	auto &RIL = *SD.getRequiredInvariantLoads(&getRegion());
2926	for (LoadInst *LI : RIL) {
2927	assert(LI && getRegion().contains(LI))((LI && getRegion().contains(LI)) ? static_cast<void > (0) : __assert_fail ("LI && getRegion().contains(LI)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2927, __PRETTY_FUNCTION__));
2928	ScopStmt *Stmt = getStmtForBasicBlock(LI->getParent());
2929	if (Stmt && Stmt->getArrayAccessOrNULLFor(LI)) {
2930	invalidate(INVARIANTLOAD, LI->getDebugLoc());
2931	return;
2932	}
2933	}
2934	}
2935
2936	void Scop::hoistInvariantLoads() {
2937	isl_union_map *Writes = getWrites();
2938	for (ScopStmt &Stmt : *this) {
2939
2940	MemoryAccessList InvariantAccesses;
2941
2942	for (MemoryAccess *Access : Stmt)
2943	if (isHoistableAccess(Access, Writes))
2944	InvariantAccesses.push_front(Access);
2945
2946	// We inserted invariant accesses always in the front but need them to be
2947	// sorted in a "natural order". The statements are already sorted in reverse
2948	// post order and that suffices for the accesses too. The reason we require
2949	// an order in the first place is the dependences between invariant loads
2950	// that can be caused by indirect loads.
2951	InvariantAccesses.reverse();
2952
2953	// Transfer the memory access from the statement to the SCoP.
2954	Stmt.removeMemoryAccesses(InvariantAccesses);
2955	addInvariantLoads(Stmt, InvariantAccesses);
2956	}
2957	isl_union_map_free(Writes);
2958
2959	verifyInvariantLoads();
2960	}
2961
2962	const ScopArrayInfo *
2963	Scop::getOrCreateScopArrayInfo(Value BasePtr, Type AccessType,
2964	ArrayRef<const SCEV *> Sizes,
2965	ScopArrayInfo::MemoryKind Kind) {
2966	auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)];
2967	if (!SAI) {
2968	auto &DL = getRegion().getEntry()->getModule()->getDataLayout();
2969	SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, Kind,
2970	DL, this));
2971	} else {
2972	// In case of mismatching array sizes, we bail out by setting the run-time
2973	// context to false.
2974	if (!SAI->updateSizes(Sizes))
2975	invalidate(DELINEARIZATION, DebugLoc());
2976	}
2977	return SAI.get();
2978	}
2979
2980	const ScopArrayInfo Scop::getScopArrayInfo(Value BasePtr,
2981	ScopArrayInfo::MemoryKind Kind) {
2982	auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
2983	assert(SAI && "No ScopArrayInfo available for this base pointer")((SAI && "No ScopArrayInfo available for this base pointer" ) ? static_cast<void> (0) : __assert_fail ("SAI && \"No ScopArrayInfo available for this base pointer\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2983, __PRETTY_FUNCTION__));
2984	return SAI;
2985	}
2986
2987	std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
2988	std::string Scop::getAssumedContextStr() const {
2989	return stringFromIslObj(AssumedContext);
2990	}
2991	std::string Scop::getBoundaryContextStr() const {
2992	return stringFromIslObj(BoundaryContext);
2993	}
2994
2995	std::string Scop::getNameStr() const {
2996	std::string ExitName, EntryName;
2997	raw_string_ostream ExitStr(ExitName);
2998	raw_string_ostream EntryStr(EntryName);
2999
3000	R.getEntry()->printAsOperand(EntryStr, false);
3001	EntryStr.str();
3002
3003	if (R.getExit()) {
3004	R.getExit()->printAsOperand(ExitStr, false);
3005	ExitStr.str();
3006	} else
3007	ExitName = "FunctionExit";
3008
3009	return EntryName + "---" + ExitName;
3010	}
3011
3012	__isl_give isl_set *Scop::getContext() const { return isl_set_copy(Context); }
3013	__isl_give isl_space *Scop::getParamSpace() const {
3014	return isl_set_get_space(Context);
3015	}
3016
3017	__isl_give isl_set *Scop::getAssumedContext() const {
3018	return isl_set_copy(AssumedContext);
3019	}
3020
3021	__isl_give isl_set *Scop::getRuntimeCheckContext() const {
3022	isl_set *RuntimeCheckContext = getAssumedContext();
3023	RuntimeCheckContext =
3024	isl_set_intersect(RuntimeCheckContext, getBoundaryContext());
3025	RuntimeCheckContext = simplifyAssumptionContext(RuntimeCheckContext, *this);
3026	return RuntimeCheckContext;
3027	}
3028
3029	bool Scop::hasFeasibleRuntimeContext() const {
3030	isl_set *RuntimeCheckContext = getRuntimeCheckContext();
3031	RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext);
3032	bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext);
3033	isl_set_free(RuntimeCheckContext);
3034	return IsFeasible;
3035	}
3036
3037	static std::string toString(AssumptionKind Kind) {
3038	switch (Kind) {
3039	case ALIASING:
3040	return "No-aliasing";
3041	case INBOUNDS:
3042	return "Inbounds";
3043	case WRAPPING:
3044	return "No-overflows";
3045	case ALIGNMENT:
3046	return "Alignment";
3047	case ERRORBLOCK:
3048	return "No-error";
3049	case INFINITELOOP:
3050	return "Finite loop";
3051	case INVARIANTLOAD:
3052	return "Invariant load";
3053	case DELINEARIZATION:
3054	return "Delinearization";
3055	case ERROR_DOMAINCONJUNCTS:
3056	return "Low number of domain conjuncts";
3057	}
3058	llvm_unreachable("Unknown AssumptionKind!")::llvm::llvm_unreachable_internal("Unknown AssumptionKind!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3058);
3059	}
3060
3061	void Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set,
3062	DebugLoc Loc) {
3063	if (isl_set_is_subset(Context, Set))
3064	return;
3065
3066	if (isl_set_is_subset(AssumedContext, Set))
3067	return;
3068
3069	auto &F = *getRegion().getEntry()->getParent();
3070	std::string Msg = toString(Kind) + " assumption:\t" + stringFromIslObj(Set);
3071	emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE"polly-scops", F, Loc, Msg);
3072	}
3073
3074	void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
3075	DebugLoc Loc) {
3076	trackAssumption(Kind, Set, Loc);
3077	AssumedContext = isl_set_intersect(AssumedContext, Set);
3078
3079	int NSets = isl_set_n_basic_set(AssumedContext);
3080	if (NSets >= MaxDisjunctsAssumed) {
3081	isl_space *Space = isl_set_get_space(AssumedContext);
3082	isl_set_free(AssumedContext);
3083	AssumedContext = isl_set_empty(Space);
3084	}
3085
3086	AssumedContext = isl_set_coalesce(AssumedContext);
3087	}
3088
3089	void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc) {
3090	addAssumption(Kind, isl_set_empty(getParamSpace()), Loc);
3091	}
3092
3093	__isl_give isl_set *Scop::getBoundaryContext() const {
3094	return isl_set_copy(BoundaryContext);
3095	}
3096
3097	void Scop::printContext(raw_ostream &OS) const {
3098	OS << "Context:\n";
3099
3100	if (!Context) {
3101	OS.indent(4) << "n/a\n\n";
3102	return;
3103	}
3104
3105	OS.indent(4) << getContextStr() << "\n";
3106
3107	OS.indent(4) << "Assumed Context:\n";
3108	if (!AssumedContext) {
3109	OS.indent(4) << "n/a\n\n";
3110	return;
3111	}
3112
3113	OS.indent(4) << getAssumedContextStr() << "\n";
3114
3115	OS.indent(4) << "Boundary Context:\n";
3116	if (!BoundaryContext) {
3117	OS.indent(4) << "n/a\n\n";
3118	return;
3119	}
3120
3121	OS.indent(4) << getBoundaryContextStr() << "\n";
3122
3123	for (const SCEV *Parameter : Parameters) {
3124	int Dim = ParameterIds.find(Parameter)->second;
3125	OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n";
3126	}
3127	}
3128
3129	void Scop::printAliasAssumptions(raw_ostream &OS) const {
3130	int noOfGroups = 0;
3131	for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
3132	if (Pair.second.size() == 0)
3133	noOfGroups += 1;
3134	else
3135	noOfGroups += Pair.second.size();
3136	}
3137
3138	OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";
3139	if (MinMaxAliasGroups.empty()) {
3140	OS.indent(8) << "n/a\n";
3141	return;
3142	}
3143
3144	for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
3145
3146	// If the group has no read only accesses print the write accesses.
3147	if (Pair.second.empty()) {
3148	OS.indent(8) << "[[";
3149	for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
3150	OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
3151	<< ">";
3152	}
3153	OS << " ]]\n";
3154	}
3155
3156	for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
3157	OS.indent(8) << "[[";
3158	OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
3159	for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
3160	OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
3161	<< ">";
3162	}
3163	OS << " ]]\n";
3164	}
3165	}
3166	}
3167
3168	void Scop::printStatements(raw_ostream &OS) const {
3169	OS << "Statements {\n";
3170
3171	for (const ScopStmt &Stmt : *this)
3172	OS.indent(4) << Stmt;
3173
3174	OS.indent(4) << "}\n";
3175	}
3176
3177	void Scop::printArrayInfo(raw_ostream &OS) const {
3178	OS << "Arrays {\n";
3179
3180	for (auto &Array : arrays())
3181	Array.second->print(OS);
3182
3183	OS.indent(4) << "}\n";
3184
3185	OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
3186
3187	for (auto &Array : arrays())
3188	Array.second->print(OS, /* SizeAsPwAff */ true);
3189
3190	OS.indent(4) << "}\n";
3191	}
3192
3193	void Scop::print(raw_ostream &OS) const {
3194	OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName()
3195	<< "\n";
3196	OS.indent(4) << "Region: " << getNameStr() << "\n";
3197	OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
3198	OS.indent(4) << "Invariant Accesses: {\n";
3199	for (const auto &IAClass : InvariantEquivClasses) {
3200	const auto &MAs = std::get<1>(IAClass);
3201	if (MAs.empty()) {
3202	OS.indent(12) << "Class Pointer: " << *std::get<0>(IAClass) << "\n";
3203	} else {
3204	MAs.front()->print(OS);
3205	OS.indent(12) << "Execution Context: " << std::get<2>(IAClass) << "\n";
3206	}
3207	}
3208	OS.indent(4) << "}\n";
3209	printContext(OS.indent(4));
3210	printArrayInfo(OS.indent(4));
3211	printAliasAssumptions(OS);
3212	printStatements(OS.indent(4));
3213	}
3214
3215	void Scop::dump() const { print(dbgs()); }
3216
3217	isl_ctx *Scop::getIslCtx() const { return IslCtx; }
3218
3219	__isl_give isl_pw_aff Scop::getPwAff(const SCEV E, BasicBlock *BB) {
3220	return Affinator.getPwAff(E, BB);
3221	}
3222
3223	__isl_give isl_union_set *Scop::getDomains() const {
3224	isl_union_set *Domain = isl_union_set_empty(getParamSpace());
3225
3226	for (const ScopStmt &Stmt : *this)
3227	Domain = isl_union_set_add_set(Domain, Stmt.getDomain());
3228
3229	return Domain;
3230	}
3231
3232	__isl_give isl_union_map *
3233	Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
3234	isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
3235
3236	for (ScopStmt &Stmt : *this) {
3237	for (MemoryAccess *MA : Stmt) {
3238	if (!Predicate(*MA))
3239	continue;
3240
3241	isl_set *Domain = Stmt.getDomain();
3242	isl_map *AccessDomain = MA->getAccessRelation();
3243	AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
3244	Accesses = isl_union_map_add_map(Accesses, AccessDomain);
3245	}
3246	}
3247	return isl_union_map_coalesce(Accesses);
3248	}
3249
3250	__isl_give isl_union_map *Scop::getMustWrites() {
3251	return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); });
3252	}
3253
3254	__isl_give isl_union_map *Scop::getMayWrites() {
3255	return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); });
3256	}
3257
3258	__isl_give isl_union_map *Scop::getWrites() {
3259	return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); });
3260	}
3261
3262	__isl_give isl_union_map *Scop::getReads() {
3263	return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });
3264	}
3265
3266	__isl_give isl_union_map *Scop::getAccesses() {
3267	return getAccessesOfType([](MemoryAccess &MA) { return true; });
3268	}
3269
3270	__isl_give isl_union_map *Scop::getSchedule() const {
3271	auto Tree = getScheduleTree();
3272	auto S = isl_schedule_get_map(Tree);
3273	isl_schedule_free(Tree);
3274	return S;
3275	}
3276
3277	__isl_give isl_schedule *Scop::getScheduleTree() const {
3278	return isl_schedule_intersect_domain(isl_schedule_copy(Schedule),
3279	getDomains());
3280	}
3281
3282	void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) {
3283	auto *S = isl_schedule_from_domain(getDomains());
3284	S = isl_schedule_insert_partial_schedule(
3285	S, isl_multi_union_pw_aff_from_union_map(NewSchedule));
3286	isl_schedule_free(Schedule);
3287	Schedule = S;
3288	}
3289
3290	void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) {
3291	isl_schedule_free(Schedule);
3292	Schedule = NewSchedule;
3293	}
3294
3295	bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
3296	bool Changed = false;
3297	for (ScopStmt &Stmt : *this) {
3298	isl_union_set *StmtDomain = isl_union_set_from_set(Stmt.getDomain());
3299	isl_union_set *NewStmtDomain = isl_union_set_intersect(
3300	isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));
3301
3302	if (isl_union_set_is_subset(StmtDomain, NewStmtDomain)) {
3303	isl_union_set_free(StmtDomain);
3304	isl_union_set_free(NewStmtDomain);
3305	continue;
3306	}
3307
3308	Changed = true;
3309
3310	isl_union_set_free(StmtDomain);
3311	NewStmtDomain = isl_union_set_coalesce(NewStmtDomain);
3312
3313	if (isl_union_set_is_empty(NewStmtDomain)) {
3314	Stmt.restrictDomain(isl_set_empty(Stmt.getDomainSpace()));
3315	isl_union_set_free(NewStmtDomain);
3316	} else
3317	Stmt.restrictDomain(isl_set_from_union_set(NewStmtDomain));
3318	}
3319	isl_union_set_free(Domain);
3320	return Changed;
3321	}
3322
3323	ScalarEvolution *Scop::getSE() const { return SE; }
3324
3325	bool Scop::isIgnored(RegionNode *RN) {
3326	BasicBlock *BB = getRegionNodeBasicBlock(RN);
3327	ScopStmt *Stmt = getStmtForRegionNode(RN);
3328
3329	// If there is no stmt, then it already has been removed.
3330	if (!Stmt)
3331	return true;
3332
3333	// Check if there are accesses contained.
3334	if (Stmt->isEmpty())
3335	return true;
3336
3337	// Check for reachability via non-error blocks.
3338	if (!DomainMap.count(BB))
3339	return true;
3340
3341	// Check if error blocks are contained.
3342	if (containsErrorBlock(RN, getRegion(), LI, DT))
3343	return true;
3344
3345	return false;
3346	}
3347
3348	struct MapToDimensionDataTy {
3349	int N;
3350	isl_union_pw_multi_aff *Res;
3351	};
3352
3353	// @brief Create a function that maps the elements of 'Set' to its N-th
3354	// dimension and add it to User->Res.
3355	//
3356	// @param Set The input set.
3357	// @param User->N The dimension to map to.
3358	// @param User->Res The isl_union_pw_multi_aff to which to add the result.
3359	//
3360	// @returns isl_stat_ok if no error occured, othewise isl_stat_error.
3361	static isl_stat mapToDimension_AddSet(__isl_take isl_set Set, void User) {
3362	struct MapToDimensionDataTy Data = (struct MapToDimensionDataTy )User;
3363	int Dim;
3364	isl_space *Space;
3365	isl_pw_multi_aff *PMA;
3366
3367	Dim = isl_set_dim(Set, isl_dim_set);
3368	Space = isl_set_get_space(Set);
3369	PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N,
3370	Dim - Data->N);
3371	if (Data->N > 1)
3372	PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1);
3373	Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA);
3374
3375	isl_set_free(Set);
3376
3377	return isl_stat_ok;
3378	}
3379
3380	// @brief Create an isl_multi_union_aff that defines an identity mapping
3381	// from the elements of USet to their N-th dimension.
3382	//
3383	// # Example:
3384	//
3385	// Domain: { A[i,j]; B[i,j,k] }
3386	// N: 1
3387	//
3388	// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
3389	//
3390	// @param USet A union set describing the elements for which to generate a
3391	// mapping.
3392	// @param N The dimension to map to.
3393	// @returns A mapping from USet to its N-th dimension.
3394	static __isl_give isl_multi_union_pw_aff *
3395	mapToDimension(__isl_take isl_union_set *USet, int N) {
3396	assert(N >= 0)((N >= 0) ? static_cast<void> (0) : __assert_fail ("N >= 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3396, __PRETTY_FUNCTION__));
3397	assert(USet)((USet) ? static_cast<void> (0) : __assert_fail ("USet" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3397, __PRETTY_FUNCTION__));
3398	assert(!isl_union_set_is_empty(USet))((!isl_union_set_is_empty(USet)) ? static_cast<void> (0 ) : __assert_fail ("!isl_union_set_is_empty(USet)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3398, __PRETTY_FUNCTION__));
3399
3400	struct MapToDimensionDataTy Data;
3401
3402	auto *Space = isl_union_set_get_space(USet);
3403	auto *PwAff = isl_union_pw_multi_aff_empty(Space);
3404
3405	Data = {N, PwAff};
3406
3407	auto Res = isl_union_set_foreach_set(USet, &mapToDimension_AddSet, &Data);
3408
3409	assert(Res == isl_stat_ok)((Res == isl_stat_ok) ? static_cast<void> (0) : __assert_fail ("Res == isl_stat_ok", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3409, __PRETTY_FUNCTION__));
3410
3411	isl_union_set_free(USet);
3412	return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
3413	}
3414
3415	void Scop::addScopStmt(BasicBlock BB, Region R) {
3416	if (BB) {
3417	Stmts.emplace_back(this, BB);
3418	auto Stmt = &Stmts.back();
3419	StmtMap[BB] = Stmt;
3420	} else {
3421	assert(R && "Either basic block or a region expected.")((R && "Either basic block or a region expected.") ? static_cast <void> (0) : __assert_fail ("R && \"Either basic block or a region expected.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3421, __PRETTY_FUNCTION__));
3422	Stmts.emplace_back(this, R);
3423	auto Stmt = &Stmts.back();
3424	for (BasicBlock *BB : R->blocks())
3425	StmtMap[BB] = Stmt;
3426	}
3427	}
3428
3429	void Scop::buildSchedule() {
3430	DenseMap<Loop , std::pair<isl_schedule , unsigned>> LoopSchedules;
3431	Loop *L = getLoopSurroundingRegion(getRegion(), LI);
3432	LoopSchedules[L];
3433	buildSchedule(getRegion().getNode(), LoopSchedules);
3434	Schedule = LoopSchedules[L].first;
3435	}
3436
3437	void Scop::buildSchedule(
3438	RegionNode *RN,
3439	DenseMap<Loop , std::pair<isl_schedule , unsigned>> &LoopSchedules) {
3440
3441	if (RN->isSubRegion()) {
3442	auto *LocalRegion = RN->getNodeAs<Region>();
3443	if (!SD.isNonAffineSubRegion(LocalRegion, &getRegion())) {
3444	ReversePostOrderTraversal<Region *> RTraversal(LocalRegion);
3445	for (auto *Child : RTraversal)
3446	buildSchedule(Child, LoopSchedules);
3447	return;
3448	}
3449	}
3450
3451	Loop *L = getRegionNodeLoop(RN, LI);
3452	if (!getRegion().contains(L))
3453	L = getLoopSurroundingRegion(getRegion(), LI);
3454
3455	int LD = getRelativeLoopDepth(L);
3456	auto &LSchedulePair = LoopSchedules[L];
3457	LSchedulePair.second += getNumBlocksInRegionNode(RN);
3458
3459	ScopStmt *Stmt = getStmtForRegionNode(RN);
3460	if (Stmt) {
3461	auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
3462	auto *StmtSchedule = isl_schedule_from_domain(UDomain);
3463	LSchedulePair.first = combineInSequence(LSchedulePair.first, StmtSchedule);
3464	}
3465
3466	isl_schedule *LSchedule = LSchedulePair.first;
3467	unsigned NumVisited = LSchedulePair.second;
3468	while (L && NumVisited == L->getNumBlocks()) {
3469	auto *PL = L->getParentLoop();
3470
3471	// Either we have a proper loop and we also build a schedule for the
3472	// parent loop or we have a infinite loop that does not have a proper
3473	// parent loop. In the former case this conditional will be skipped, in
3474	// the latter case however we will break here as we do not build a domain
3475	// nor a schedule for a infinite loop.
3476	assert(LoopSchedules.count(PL) \|\| LSchedule == nullptr)((LoopSchedules.count(PL) \|\| LSchedule == nullptr) ? static_cast <void> (0) : __assert_fail ("LoopSchedules.count(PL) \|\| LSchedule == nullptr" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3476, __PRETTY_FUNCTION__));
3477	if (!LoopSchedules.count(PL))
3478	break;
3479
3480	auto &PSchedulePair = LoopSchedules[PL];
3481
3482	if (LSchedule) {
3483	auto *LDomain = isl_schedule_get_domain(LSchedule);
3484	auto *MUPA = mapToDimension(LDomain, LD + 1);
3485	LSchedule = isl_schedule_insert_partial_schedule(LSchedule, MUPA);
3486	PSchedulePair.first = combineInSequence(PSchedulePair.first, LSchedule);
3487	}
3488
3489	PSchedulePair.second += NumVisited;
3490
3491	L = PL;
3492	LD--;
3493	NumVisited = PSchedulePair.second;
3494	LSchedule = PSchedulePair.first;
3495	}
3496	}
3497
3498	ScopStmt Scop::getStmtForBasicBlock(BasicBlock BB) const {
3499	auto StmtMapIt = StmtMap.find(BB);
3500	if (StmtMapIt == StmtMap.end())
3501	return nullptr;
3502	return StmtMapIt->second;
3503	}
3504
3505	ScopStmt Scop::getStmtForRegionNode(RegionNode RN) const {
3506	return getStmtForBasicBlock(getRegionNodeBasicBlock(RN));
3507	}
3508
3509	int Scop::getRelativeLoopDepth(const Loop *L) const {
3510	Loop *OuterLoop =
3511	L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
3512	if (!OuterLoop)
3513	return -1;
3514	return L->getLoopDepth() - OuterLoop->getLoopDepth();
3515	}
3516
3517	void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
3518	Region *NonAffineSubRegion, bool IsExitBlock) {
3519
3520	// PHI nodes that are in the exit block of the region, hence if IsExitBlock is
3521	// true, are not modeled as ordinary PHI nodes as they are not part of the
3522	// region. However, we model the operands in the predecessor blocks that are
3523	// part of the region as regular scalar accesses.
3524
3525	// If we can synthesize a PHI we can skip it, however only if it is in
3526	// the region. If it is not it can only be in the exit block of the region.
3527	// In this case we model the operands but not the PHI itself.
3528	if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
3529	return;
3530
3531	// PHI nodes are modeled as if they had been demoted prior to the SCoP
3532	// detection. Hence, the PHI is a load of a new memory location in which the
3533	// incoming value was written at the end of the incoming basic block.
3534	bool OnlyNonAffineSubRegionOperands = true;
3535	for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
3536	Value *Op = PHI->getIncomingValue(u);
3537	BasicBlock *OpBB = PHI->getIncomingBlock(u);
3538
3539	// Do not build scalar dependences inside a non-affine subregion.
3540	if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
3541	continue;
3542
3543	OnlyNonAffineSubRegionOperands = false;
3544
3545	if (!R.contains(OpBB))
3546	continue;
3547
3548	Instruction *OpI = dyn_cast<Instruction>(Op);
3549	if (OpI) {
3550	BasicBlock *OpIBB = OpI->getParent();
3551	// As we pretend there is a use (or more precise a write) of OpI in OpBB
3552	// we have to insert a scalar dependence from the definition of OpI to
3553	// OpBB if the definition is not in OpBB.
3554	if (scop->getStmtForBasicBlock(OpIBB) !=
3555	scop->getStmtForBasicBlock(OpBB)) {
3556	addValueReadAccess(OpI, PHI, OpBB);
3557	addValueWriteAccess(OpI);
3558	}
3559	} else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
3560	addValueReadAccess(Op, PHI, OpBB);
3561	}
3562
3563	addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
3564	}
3565
3566	if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
3567	addPHIReadAccess(PHI);
3568	}
3569	}
3570
3571	bool ScopInfo::buildScalarDependences(Instruction Inst, Region R,
3572	Region *NonAffineSubRegion) {
3573	bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
3574	if (isIgnoredIntrinsic(Inst))
3575	return false;
3576
3577	bool AnyCrossStmtUse = false;
3578	BasicBlock *ParentBB = Inst->getParent();
3579
3580	for (User *U : Inst->users()) {
3581	Instruction *UI = dyn_cast<Instruction>(U);
3582
3583	// Ignore the strange user
3584	if (UI == 0)
3585	continue;
3586
3587	BasicBlock *UseParent = UI->getParent();
3588
3589	// Ignore basic block local uses. A value that is defined in a scop, but
3590	// used in a PHI node in the same basic block does not count as basic block
3591	// local, as for such cases a control flow edge is passed between definition
3592	// and use.
3593	if (UseParent == ParentBB && !isa<PHINode>(UI))
3594	continue;
3595
3596	// Uses by PHI nodes in the entry node count as external uses in case the
3597	// use is through an incoming block that is itself not contained in the
3598	// region.
3599	if (R->getEntry() == UseParent) {
3600	if (auto *PHI = dyn_cast<PHINode>(UI)) {
3601	bool ExternalUse = false;
3602	for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
3603	if (PHI->getIncomingValue(i) == Inst &&
3604	!R->contains(PHI->getIncomingBlock(i))) {
3605	ExternalUse = true;
3606	break;
3607	}
3608	}
3609
3610	if (ExternalUse) {
3611	AnyCrossStmtUse = true;
3612	continue;
3613	}
3614	}
3615	}
3616
3617	// Do not build scalar dependences inside a non-affine subregion.
3618	if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
3619	continue;
3620
3621	// Check for PHI nodes in the region exit and skip them, if they will be
3622	// modeled as PHI nodes.
3623	//
3624	// PHI nodes in the region exit that have more than two incoming edges need
3625	// to be modeled as PHI-Nodes to correctly model the fact that depending on
3626	// the control flow a different value will be assigned to the PHI node. In
3627	// case this is the case, there is no need to create an additional normal
3628	// scalar dependence. Hence, bail out before we register an "out-of-region"
3629	// use for this definition.
3630	if (isa<PHINode>(UI) && UI->getParent() == R->getExit() &&
3631	!R->getExitingBlock())
3632	continue;
3633
3634	// Check whether or not the use is in the SCoP.
3635	if (!R->contains(UseParent)) {
3636	AnyCrossStmtUse = true;
3637	continue;
3638	}
3639
3640	// If the instruction can be synthesized and the user is in the region
3641	// we do not need to add scalar dependences.
3642	if (canSynthesizeInst)
3643	continue;
3644
3645	// No need to translate these scalar dependences into polyhedral form,
3646	// because synthesizable scalars can be generated by the code generator.
3647	if (canSynthesize(UI, LI, SE, R))
3648	continue;
3649
3650	// Skip PHI nodes in the region as they handle their operands on their own.
3651	if (isa<PHINode>(UI))
3652	continue;
3653
3654	// Now U is used in another statement.
3655	AnyCrossStmtUse = true;
3656
3657	// Do not build a read access that is not in the current SCoP
3658	// Use the def instruction as base address of the MemoryAccess, so that it
3659	// will become the name of the scalar access in the polyhedral form.
3660	addValueReadAccess(Inst, UI);
3661	}
3662
3663	if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
3664	for (Value *Op : Inst->operands()) {
3665	if (canSynthesize(Op, LI, SE, R))
3666	continue;
3667
3668	if (Instruction *OpInst = dyn_cast<Instruction>(Op))
3669	if (R->contains(OpInst))
3670	continue;
3671
3672	if (isa<Constant>(Op))
3673	continue;
3674
3675	addValueReadAccess(Op, Inst);
3676	}
3677	}
3678
3679	return AnyCrossStmtUse;
3680	}
3681
3682	extern MapInsnToMemAcc InsnToMemAcc;
3683
3684	void ScopInfo::buildMemoryAccess(
3685	Instruction Inst, Loop L, Region *R,
3686	const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
3687	const InvariantLoadsSetTy &ScopRIL) {
3688	unsigned Size;
3689	Type *SizeType;
3690	Value *Val;
3691	enum MemoryAccess::AccessType Type;
3692
3693	if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
3694	SizeType = Load->getType();
3695	Size = TD->getTypeAllocSize(SizeType);
3696	Type = MemoryAccess::READ;
3697	Val = Load;
3698	} else {
3699	StoreInst *Store = cast<StoreInst>(Inst);
3700	SizeType = Store->getValueOperand()->getType();
3701	Size = TD->getTypeAllocSize(SizeType);
3702	Type = MemoryAccess::MUST_WRITE;
3703	Val = Store->getValueOperand();
3704	}
3705
3706	auto Address = getPointerOperand(*Inst);
3707
3708	const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
3709	const SCEVUnknown *BasePointer =
3710	dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
3711
3712	assert(BasePointer && "Could not find base pointer")((BasePointer && "Could not find base pointer") ? static_cast <void> (0) : __assert_fail ("BasePointer && \"Could not find base pointer\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3712, __PRETTY_FUNCTION__));
3713	AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
3714
3715	if (isa<GetElementPtrInst>(Address) \|\| isa<BitCastInst>(Address)) {
3716	auto NewAddress = Address;
3717	if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
3718	auto Src = BitCast->getOperand(0);
3719	auto SrcTy = Src->getType();
3720	auto DstTy = BitCast->getType();
3721	if (SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits())
3722	NewAddress = Src;
3723	}
3724
3725	if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
3726	std::vector<const SCEV *> Subscripts;
3727	std::vector<int> Sizes;
3728	std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE);
3729	auto BasePtr = GEP->getOperand(0);
3730
3731	std::vector<const SCEV *> SizesSCEV;
3732
3733	bool AllAffineSubcripts = true;
3734	for (auto Subscript : Subscripts) {
3735	InvariantLoadsSetTy AccessILS;
3736	AllAffineSubcripts =
3737	isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS);
3738
3739	for (LoadInst *LInst : AccessILS)
3740	if (!ScopRIL.count(LInst))
3741	AllAffineSubcripts = false;
3742
3743	if (!AllAffineSubcripts)
3744	break;
3745	}
3746
3747	if (AllAffineSubcripts && Sizes.size() > 0) {
3748	for (auto V : Sizes)
3749	SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
3750	IntegerType::getInt64Ty(BasePtr->getContext()), V)));
3751	SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
3752	IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
3753
3754	addArrayAccess(Inst, Type, BasePointer->getValue(), Size, true,
3755	Subscripts, SizesSCEV, Val);
3756	return;
3757	}
3758	}
3759	}
3760
3761	auto AccItr = InsnToMemAcc.find(Inst);
3762	if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
3763	addArrayAccess(Inst, Type, BasePointer->getValue(), Size, true,
3764	AccItr->second.DelinearizedSubscripts,
3765	AccItr->second.Shape->DelinearizedSizes, Val);
3766	return;
3767	}
3768
3769	// Check if the access depends on a loop contained in a non-affine subregion.
3770	bool isVariantInNonAffineLoop = false;
3771	if (BoxedLoops) {
3772	SetVector<const Loop *> Loops;
3773	findLoops(AccessFunction, Loops);
3774	for (const Loop *L : Loops)
3775	if (BoxedLoops->count(L))
3776	isVariantInNonAffineLoop = true;
3777	}
3778
3779	InvariantLoadsSetTy AccessILS;
3780	bool IsAffine =
3781	!isVariantInNonAffineLoop &&
3782	isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessILS);
3783
3784	for (LoadInst *LInst : AccessILS)
3785	if (!ScopRIL.count(LInst))
3786	IsAffine = false;
3787
3788	// FIXME: Size of the number of bytes of an array element, not the number of
3789	// elements as probably intended here.
3790	const SCEV *SizeSCEV =
3791	SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size);
3792
3793	if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
3794	Type = MemoryAccess::MAY_WRITE;
3795
3796	addArrayAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine,
3797	ArrayRef<const SCEV *>(AccessFunction),
3798	ArrayRef<const SCEV *>(SizeSCEV), Val);
3799	}
3800
3801	void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
3802
3803	if (SD->isNonAffineSubRegion(&SR, &R)) {
3804	for (BasicBlock *BB : SR.blocks())
3805	buildAccessFunctions(R, *BB, &SR);
3806	return;
3807	}
3808
3809	for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
3810	if (I->isSubRegion())
3811	buildAccessFunctions(R, *I->getNodeAs<Region>());
3812	else
3813	buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
3814	}
3815
3816	void ScopInfo::buildStmts(Region &SR) {
3817	Region *R = getRegion();
3818
3819	if (SD->isNonAffineSubRegion(&SR, R)) {
3820	scop->addScopStmt(nullptr, &SR);
3821	return;
3822	}
3823
3824	for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
3825	if (I->isSubRegion())
3826	buildStmts(*I->getNodeAs<Region>());
3827	else
3828	scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
3829	}
3830
3831	void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
3832	Region *NonAffineSubRegion,
3833	bool IsExitBlock) {
3834	// We do not build access functions for error blocks, as they may contain
3835	// instructions we can not model.
3836	DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3837	if (isErrorBlock(BB, R, *LI, DT) && !IsExitBlock)
3838	return;
3839
3840	Loop *L = LI->getLoopFor(&BB);
3841
3842	// The set of loops contained in non-affine subregions that are part of R.
3843	const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
3844
3845	// The set of loads that are required to be invariant.
3846	auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
3847
3848	for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
3849	Instruction Inst = &I;
3850
3851	PHINode *PHI = dyn_cast<PHINode>(Inst);
3852	if (PHI)
3853	buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
3854
3855	// For the exit block we stop modeling after the last PHI node.
3856	if (!PHI && IsExitBlock)
3857	break;
3858
3859	// TODO: At this point we only know that elements of ScopRIL have to be
3860	// invariant and will be hoisted for the SCoP to be processed. Though,
3861	// there might be other invariant accesses that will be hoisted and
3862	// that would allow to make a non-affine access affine.
3863	if (isa<LoadInst>(Inst) \|\| isa<StoreInst>(Inst))
3864	buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
3865
3866	if (isIgnoredIntrinsic(Inst))
3867	continue;
3868
3869	// Do not build scalar dependences for required invariant loads as we will
3870	// hoist them later on anyway or drop the SCoP if we cannot.
3871	if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
3872	continue;
3873
3874	if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
3875	if (!isa<StoreInst>(Inst))
3876	addValueWriteAccess(Inst);
3877	}
3878	}
3879	}
3880
3881	void ScopInfo::addMemoryAccess(BasicBlock BB, Instruction Inst,
3882	MemoryAccess::AccessType Type,
3883	Value *BaseAddress, unsigned ElemBytes,
3884	bool Affine, Value *AccessValue,
3885	ArrayRef<const SCEV *> Subscripts,
3886	ArrayRef<const SCEV *> Sizes,
3887	ScopArrayInfo::MemoryKind Kind) {
3888	ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
3889
3890	// Do not create a memory access for anything not in the SCoP. It would be
3891	// ignored anyway.
3892	if (!Stmt)
3893	return;
3894
3895	AccFuncSetType &AccList = AccFuncMap[BB];
3896	Value *BaseAddr = BaseAddress;
3897	std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
3898
3899	bool isKnownMustAccess = false;
3900
3901	// Accesses in single-basic block statements are always excuted.
3902	if (Stmt->isBlockStmt())
3903	isKnownMustAccess = true;
3904
3905	if (Stmt->isRegionStmt()) {
3906	// Accesses that dominate the exit block of a non-affine region are always
3907	// executed. In non-affine regions there may exist MK_Values that do not
3908	// dominate the exit. MK_Values will always dominate the exit and MK_PHIs
3909	// only if there is at most one PHI_WRITE in the non-affine region.
3910	if (DT->dominates(BB, Stmt->getRegion()->getExit()))
3911	isKnownMustAccess = true;
3912	}
3913
3914	if (!isKnownMustAccess && Type == MemoryAccess::MUST_WRITE)
3915	Type = MemoryAccess::MAY_WRITE;
3916
3917	AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine,
3918	Subscripts, Sizes, AccessValue, Kind, BaseName);
3919	Stmt->addAccess(&AccList.back());
3920	}
3921
3922	void ScopInfo::addArrayAccess(Instruction *MemAccInst,
3923	MemoryAccess::AccessType Type, Value *BaseAddress,
3924	unsigned ElemBytes, bool IsAffine,
3925	ArrayRef<const SCEV *> Subscripts,
3926	ArrayRef<const SCEV *> Sizes,
3927	Value *AccessValue) {
3928	assert(isa<LoadInst>(MemAccInst) \|\| isa<StoreInst>(MemAccInst))((isa<LoadInst>(MemAccInst) \|\| isa<StoreInst>(MemAccInst )) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(MemAccInst) \|\| isa<StoreInst>(MemAccInst)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3928, __PRETTY_FUNCTION__));
3929	assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ))((isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ )) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3929, __PRETTY_FUNCTION__));
3930	addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
3931	ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
3932	ScopArrayInfo::MK_Array);
3933	}
3934	void ScopInfo::addValueWriteAccess(Instruction *Value) {
3935	addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
3936	true, Value, ArrayRef<const SCEV *>(),
3937	ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
3938	}
3939	void ScopInfo::addValueReadAccess(Value Value, Instruction User) {
3940	assert(!isa<PHINode>(User))((!isa<PHINode>(User)) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(User)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3940, __PRETTY_FUNCTION__));
3941	addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
3942	Value, ArrayRef<const SCEV >(), ArrayRef<const SCEV >(),
3943	ScopArrayInfo::MK_Value);
3944	}
3945	void ScopInfo::addValueReadAccess(Value Value, PHINode User,
3946	BasicBlock *UserBB) {
3947	addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
3948	ArrayRef<const SCEV >(), ArrayRef<const SCEV >(),
3949	ScopArrayInfo::MK_Value);
3950	}
3951	void ScopInfo::addPHIWriteAccess(PHINode PHI, BasicBlock IncomingBlock,
3952	Value *IncomingValue, bool IsExitBlock) {
3953	addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
3954	MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
3955	ArrayRef<const SCEV >(), ArrayRef<const SCEV >(),
3956	IsExitBlock ? ScopArrayInfo::MK_ExitPHI
3957	: ScopArrayInfo::MK_PHI);
3958	}
3959	void ScopInfo::addPHIReadAccess(PHINode *PHI) {
3960	addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
3961	ArrayRef<const SCEV >(), ArrayRef<const SCEV >(),
3962	ScopArrayInfo::MK_PHI);
3963	}
3964
3965	void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
3966	unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, LI, SD);
3967	scop = new Scop(R, AccFuncMap, SD, SE, DT, LI, ctx, MaxLoopDepth);
3968
3969	buildStmts(R);
3970	buildAccessFunctions(R, R);
3971
3972	// In case the region does not have an exiting block we will later (during
3973	// code generation) split the exit block. This will move potential PHI nodes
3974	// from the current exit block into the new region exiting block. Hence, PHI
3975	// nodes that are at this point not part of the region will be.
3976	// To handle these PHI nodes later we will now model their operands as scalar
3977	// accesses. Note that we do not model anything in the exit block if we have
3978	// an exiting block in the region, as there will not be any splitting later.
3979	if (!R.getExitingBlock())
3980	buildAccessFunctions(R, R.getExit(), nullptr, / IsExitBlock */ true);
3981
3982	scop->init(*AA, AC);
3983	}
3984
3985	void ScopInfo::print(raw_ostream &OS, const Module *) const {
3986	if (!scop) {
3987	OS << "Invalid Scop!\n";
3988	return;
3989	}
3990
3991	scop->print(OS);
3992	}
3993
3994	void ScopInfo::clear() {
3995	AccFuncMap.clear();
3996	if (scop) {
3997	delete scop;
3998	scop = 0;
3999	}
4000	}
4001
4002	//===----------------------------------------------------------------------===//
4003	ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
4004	ctx = isl_ctx_alloc();
4005	isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT2);
4006	}
4007
4008	ScopInfo::~ScopInfo() {
4009	clear();
4010	isl_ctx_free(ctx);
4011	}
4012
4013	void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
4014	AU.addRequired<LoopInfoWrapperPass>();
4015	AU.addRequired<RegionInfoPass>();
4016	AU.addRequired<DominatorTreeWrapperPass>();
4017	AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
4018	AU.addRequiredTransitive<ScopDetection>();
4019	AU.addRequired<AAResultsWrapperPass>();
4020	AU.addRequired<AssumptionCacheTracker>();
4021	AU.setPreservesAll();
4022	}
4023
4024	bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
4025	SD = &getAnalysis<ScopDetection>();
4026
4027	if (!SD->isMaxRegionInScop(*R))
4028	return false;
4029
4030	Function *F = R->getEntry()->getParent();
4031	SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
4032	LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
4033	AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4034	TD = &F->getParent()->getDataLayout();
4035	DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4036	auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
4037
4038	DebugLoc Beg, End;
4039	getDebugLocations(R, Beg, End);
4040	std::string Msg = "SCoP begins here.";
4041	emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE"polly-scops", *F, Beg, Msg);
4042
4043	buildScop(*R, AC);
4044
4045	DEBUG(scop->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { scop->print(dbgs()); } } while (0);
4046
4047	if (scop->isEmpty() \|\| !scop->hasFeasibleRuntimeContext()) {
4048	Msg = "SCoP ends here but was dismissed.";
4049	delete scop;
4050	scop = nullptr;
4051	} else {
4052	Msg = "SCoP ends here.";
4053	++ScopFound;
4054	if (scop->getMaxLoopDepth() > 0)
4055	++RichScopFound;
4056	}
4057
4058	emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE"polly-scops", *F, End, Msg);
4059
4060	return false;
4061	}
4062
4063	char ScopInfo::ID = 0;
4064
4065	Pass *polly::createScopInfoPass() { return new ScopInfo(); }
4066
4067	INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",static void* initializeScopInfoPassOnce(PassRegistry &Registry ) {
4068	"Polly - Create polyhedral description of Scops", false,static void* initializeScopInfoPassOnce(PassRegistry &Registry ) {
4069	false)static void* initializeScopInfoPassOnce(PassRegistry &Registry ) {;
4070	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);;
4071	INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);;
4072	INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);;
4073	INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry);;
4074	INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);;
4075	INITIALIZE_PASS_DEPENDENCY(ScopDetection)initializeScopDetectionPass(Registry);;
4076	INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);;
4077	INITIALIZE_PASS_END(ScopInfo, "polly-scops",PassInfo PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
4078	"Polly - Create polyhedral description of Scops", false,PassInfo PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
4079	false)PassInfo PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }