1	//===- ScopInfo.cpp -------------------------------------------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// Create a polyhedral description for a static control flow region.
10	//
11	// The pass creates a polyhedral description of the Scops detected by the Scop
12	// detection derived from their LLVM-IR code.
13	//
14	// This representation is shared among several tools in the polyhedral
15	// community, which are e.g. Cloog, Pluto, Loopo, Graphite.
16	//
17	//===----------------------------------------------------------------------===//
18
19	#include "polly/ScopInfo.h"
20	#include "polly/LinkAllPasses.h"
21	#include "polly/Options.h"
22	#include "polly/ScopBuilder.h"
23	#include "polly/ScopDetection.h"
24	#include "polly/Support/GICHelper.h"
25	#include "polly/Support/ISLOStream.h"
26	#include "polly/Support/ISLTools.h"
27	#include "polly/Support/SCEVAffinator.h"
28	#include "polly/Support/SCEVValidator.h"
29	#include "polly/Support/ScopHelper.h"
30	#include "llvm/ADT/APInt.h"
31	#include "llvm/ADT/ArrayRef.h"
32	#include "llvm/ADT/PostOrderIterator.h"
33	#include "llvm/ADT/Sequence.h"
34	#include "llvm/ADT/SmallPtrSet.h"
35	#include "llvm/ADT/SmallSet.h"
36	#include "llvm/ADT/Statistic.h"
37	#include "llvm/ADT/StringExtras.h"
38	#include "llvm/Analysis/AliasAnalysis.h"
39	#include "llvm/Analysis/AssumptionCache.h"
40	#include "llvm/Analysis/Loads.h"
41	#include "llvm/Analysis/LoopInfo.h"
42	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
43	#include "llvm/Analysis/RegionInfo.h"
44	#include "llvm/Analysis/RegionIterator.h"
45	#include "llvm/Analysis/ScalarEvolution.h"
46	#include "llvm/Analysis/ScalarEvolutionExpressions.h"
47	#include "llvm/IR/BasicBlock.h"
48	#include "llvm/IR/ConstantRange.h"
49	#include "llvm/IR/DataLayout.h"
50	#include "llvm/IR/DebugLoc.h"
51	#include "llvm/IR/Dominators.h"
52	#include "llvm/IR/Function.h"
53	#include "llvm/IR/InstrTypes.h"
54	#include "llvm/IR/Instruction.h"
55	#include "llvm/IR/Instructions.h"
56	#include "llvm/IR/Module.h"
57	#include "llvm/IR/PassManager.h"
58	#include "llvm/IR/Type.h"
59	#include "llvm/IR/Value.h"
60	#include "llvm/InitializePasses.h"
61	#include "llvm/Support/Compiler.h"
62	#include "llvm/Support/Debug.h"
63	#include "llvm/Support/ErrorHandling.h"
64	#include "llvm/Support/raw_ostream.h"
65	#include "isl/aff.h"
66	#include "isl/local_space.h"
67	#include "isl/map.h"
68	#include "isl/options.h"
69	#include "isl/set.h"
70	#include <cassert>
71	#include <numeric>
72
73	using namespace llvm;
74	using namespace polly;
75
76	#define DEBUG_TYPE "polly-scops"
77
78	STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.");
79	STATISTIC(AssumptionsInbounds, "Number of inbounds assumptions taken.");
80	STATISTIC(AssumptionsWrapping, "Number of wrapping assumptions taken.");
81	STATISTIC(AssumptionsUnsigned, "Number of unsigned assumptions taken.");
82	STATISTIC(AssumptionsComplexity, "Number of too complex SCoPs.");
83	STATISTIC(AssumptionsUnprofitable, "Number of unprofitable SCoPs.");
84	STATISTIC(AssumptionsErrorBlock, "Number of error block assumptions taken.");
85	STATISTIC(AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.");
86	STATISTIC(AssumptionsInvariantLoad,
87	"Number of invariant loads assumptions taken.");
88	STATISTIC(AssumptionsDelinearization,
89	"Number of delinearization assumptions taken.");
90
91	STATISTIC(NumScops, "Number of feasible SCoPs after ScopInfo");
92	STATISTIC(NumLoopsInScop, "Number of loops in scops");
93	STATISTIC(NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo");
94	STATISTIC(NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo");
95
96	STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");
97	STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
98	STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
99	STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
100	STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
101	STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
102	STATISTIC(NumScopsDepthLarger,
103	"Number of scops with maximal loop depth 6 and larger");
104	STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");
105
106	STATISTIC(NumValueWrites, "Number of scalar value writes after ScopInfo");
107	STATISTIC(
108	NumValueWritesInLoops,
109	"Number of scalar value writes nested in affine loops after ScopInfo");
110	STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo");
111	STATISTIC(NumPHIWritesInLoops,
112	"Number of scalar phi writes nested in affine loops after ScopInfo");
113	STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo");
114	STATISTIC(NumSingletonWritesInLoops,
115	"Number of singleton writes nested in affine loops after ScopInfo");
116
117	unsigned const polly::MaxDisjunctsInDomain = 20;
118
119	// The number of disjunct in the context after which we stop to add more
120	// disjuncts. This parameter is there to avoid exponential growth in the
121	// number of disjunct when adding non-convex sets to the context.
122	static int const MaxDisjunctsInContext = 4;
123
124	// Be a bit more generous for the defined behavior context which is used less
125	// often.
126	static int const MaxDisjunktsInDefinedBehaviourContext = 8;
127
128	static cl::opt<bool> PollyRemarksMinimal(
129	"polly-remarks-minimal",
130	cl::desc("Do not emit remarks about assumptions that are known"),
131	cl::Hidden, cl::cat(PollyCategory));
132
133	static cl::opt<bool>
134	IslOnErrorAbort("polly-on-isl-error-abort",
135	cl::desc("Abort if an isl error is encountered"),
136	cl::init(Val: true), cl::cat(PollyCategory));
137
138	static cl::opt<bool> PollyPreciseInbounds(
139	"polly-precise-inbounds",
140	cl::desc("Take more precise inbounds assumptions (do not scale well)"),
141	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
142
143	static cl::opt<bool> PollyIgnoreParamBounds(
144	"polly-ignore-parameter-bounds",
145	cl::desc(
146	"Do not add parameter bounds and do no gist simplify sets accordingly"),
147	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
148
149	static cl::opt<bool> PollyPreciseFoldAccesses(
150	"polly-precise-fold-accesses",
151	cl::desc("Fold memory accesses to model more possible delinearizations "
152	"(does not scale well)"),
153	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
154
155	bool polly::UseInstructionNames;
156
157	static cl::opt<bool, true> XUseInstructionNames(
158	"polly-use-llvm-names",
159	cl::desc("Use LLVM-IR names when deriving statement names"),
160	cl::location(L&: UseInstructionNames), cl::Hidden, cl::cat(PollyCategory));
161
162	static cl::opt<bool> PollyPrintInstructions(
163	"polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
164	cl::Hidden, cl::Optional, cl::init(Val: false), cl::cat(PollyCategory));
165
166	static cl::list<std::string> IslArgs("polly-isl-arg",
167	cl::value_desc("argument"),
168	cl::desc("Option passed to ISL"),
169	cl::cat(PollyCategory));
170
171	//===----------------------------------------------------------------------===//
172
173	static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,
174	int dim, isl::dim type) {
175	isl::val V;
176	isl::ctx Ctx = S.ctx();
177
178	// The upper and lower bound for a parameter value is derived either from
179	// the data type of the parameter or from the - possibly more restrictive -
180	// range metadata.
181	V = valFromAPInt(Ctx: Ctx.get(), Int: Range.getSignedMin(), IsSigned: true);
182	S = S.lower_bound_val(type, pos: dim, value: V);
183	V = valFromAPInt(Ctx: Ctx.get(), Int: Range.getSignedMax(), IsSigned: true);
184	S = S.upper_bound_val(type, pos: dim, value: V);
185
186	if (Range.isFullSet())
187	return S;
188
189	if (S.n_basic_set().release() > MaxDisjunctsInContext)
190	return S;
191
192	// In case of signed wrapping, we can refine the set of valid values by
193	// excluding the part not covered by the wrapping range.
194	if (Range.isSignWrappedSet()) {
195	V = valFromAPInt(Ctx: Ctx.get(), Int: Range.getLower(), IsSigned: true);
196	isl::set SLB = S.lower_bound_val(type, pos: dim, value: V);
197
198	V = valFromAPInt(Ctx: Ctx.get(), Int: Range.getUpper(), IsSigned: true);
199	V = V.sub(v2: 1);
200	isl::set SUB = S.upper_bound_val(type, pos: dim, value: V);
201	S = SLB.unite(set2: SUB);
202	}
203
204	return S;
205	}
206
207	static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
208	LoadInst *BasePtrLI = dyn_cast<LoadInst>(Val: BasePtr);
209	if (!BasePtrLI)
210	return nullptr;
211
212	if (!S->contains(I: BasePtrLI))
213	return nullptr;
214
215	ScalarEvolution &SE = *S->getSE();
216
217	auto *OriginBaseSCEV =
218	SE.getPointerBase(V: SE.getSCEV(V: BasePtrLI->getPointerOperand()));
219	if (!OriginBaseSCEV)
220	return nullptr;
221
222	auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(Val: OriginBaseSCEV);
223	if (!OriginBaseSCEVUnknown)
224	return nullptr;
225
226	return S->getScopArrayInfo(BasePtr: OriginBaseSCEVUnknown->getValue(),
227	Kind: MemoryKind::Array);
228	}
229
230	ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,
231	ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
232	const DataLayout &DL, Scop *S,
233	const char *BaseName)
234	: BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
235	std::string BasePtrName =
236	BaseName ? BaseName
237	: getIslCompatibleName(Prefix: "MemRef", Val: BasePtr, Number: S->getNextArrayIdx(),
238	Suffix: Kind == MemoryKind::PHI ? "__phi" : "",
239	UseInstructionNames);
240	Id = isl::id::alloc(ctx: Ctx, name: BasePtrName, user: this);
241
242	updateSizes(Sizes);
243
244	if (!BasePtr || Kind != MemoryKind::Array) {
245	BasePtrOriginSAI = nullptr;
246	return;
247	}
248
249	BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
250	if (BasePtrOriginSAI)
251	const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(DerivedSAI: this);
252	}
253
254	ScopArrayInfo::~ScopArrayInfo() = default;
255
256	isl::space ScopArrayInfo::getSpace() const {
257	auto Space = isl::space(Id.ctx(), 0, getNumberOfDimensions());
258	Space = Space.set_tuple_id(type: isl::dim::set, id: Id);
259	return Space;
260	}
261
262	bool ScopArrayInfo::isReadOnly() {
263	isl::union_set WriteSet = S.getWrites().range();
264	isl::space Space = getSpace();
265	WriteSet = WriteSet.extract_set(space: Space);
266
267	return bool(WriteSet.is_empty());
268	}
269
270	bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {
271	if (Array->getElementType() != getElementType())
272	return false;
273
274	if (Array->getNumberOfDimensions() != getNumberOfDimensions())
275	return false;
276
277	for (unsigned i = 0; i < getNumberOfDimensions(); i++)
278	if (Array->getDimensionSize(Dim: i) != getDimensionSize(Dim: i))
279	return false;
280
281	return true;
282	}
283
284	void ScopArrayInfo::updateElementType(Type *NewElementType) {
285	if (NewElementType == ElementType)
286	return;
287
288	auto OldElementSize = DL.getTypeAllocSizeInBits(Ty: ElementType);
289	auto NewElementSize = DL.getTypeAllocSizeInBits(Ty: NewElementType);
290
291	if (NewElementSize == OldElementSize || NewElementSize == 0)
292	return;
293
294	if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
295	ElementType = NewElementType;
296	} else {
297	auto GCD = std::gcd(m: (uint64_t)NewElementSize, n: (uint64_t)OldElementSize);
298	ElementType = IntegerType::get(C&: ElementType->getContext(), NumBits: GCD);
299	}
300	}
301
302	bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
303	bool CheckConsistency) {
304	int SharedDims = std::min(a: NewSizes.size(), b: DimensionSizes.size());
305	int ExtraDimsNew = NewSizes.size() - SharedDims;
306	int ExtraDimsOld = DimensionSizes.size() - SharedDims;
307
308	if (CheckConsistency) {
309	for (int i = 0; i < SharedDims; i++) {
310	auto *NewSize = NewSizes[i + ExtraDimsNew];
311	auto *KnownSize = DimensionSizes[i + ExtraDimsOld];
312	if (NewSize && KnownSize && NewSize != KnownSize)
313	return false;
314	}
315
316	if (DimensionSizes.size() >= NewSizes.size())
317	return true;
318	}
319
320	DimensionSizes.clear();
321	DimensionSizes.insert(I: DimensionSizes.begin(), From: NewSizes.begin(),
322	To: NewSizes.end());
323	DimensionSizesPw.clear();
324	for (const SCEV *Expr : DimensionSizes) {
325	if (!Expr) {
326	DimensionSizesPw.push_back(Elt: isl::pw_aff());
327	continue;
328	}
329	isl::pw_aff Size = S.getPwAffOnly(E: Expr);
330	DimensionSizesPw.push_back(Elt: Size);
331	}
332	return true;
333	}
334
335	std::string ScopArrayInfo::getName() const { return Id.get_name(); }
336
337	int ScopArrayInfo::getElemSizeInBytes() const {
338	return DL.getTypeAllocSize(Ty: ElementType);
339	}
340
341	isl::id ScopArrayInfo::getBasePtrId() const { return Id; }
342
343	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
344	LLVM_DUMP_METHOD void ScopArrayInfo::dump() const { print(OS&: errs()); }
345	#endif
346
347	void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
348	OS.indent(NumSpaces: 8) << *getElementType() << " " << getName();
349	unsigned u = 0;
350
351	if (getNumberOfDimensions() > 0 && !getDimensionSize(Dim: 0)) {
352	OS << "[*]";
353	u++;
354	}
355	for (; u < getNumberOfDimensions(); u++) {
356	OS << "[";
357
358	if (SizeAsPwAff) {
359	isl::pw_aff Size = getDimensionSizePw(Dim: u);
360	OS << " " << Size << " ";
361	} else {
362	OS << *getDimensionSize(Dim: u);
363	}
364
365	OS << "]";
366	}
367
368	OS << ";";
369
370	if (BasePtrOriginSAI)
371	OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
372
373	OS << " // Element size " << getElemSizeInBytes() << "\n";
374	}
375
376	const ScopArrayInfo *
377	ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA) {
378	isl::id Id = PMA.get_tuple_id(type: isl::dim::out);
379	assert(!Id.is_null() && "Output dimension didn't have an ID");
380	return getFromId(Id);
381	}
382
383	const ScopArrayInfo *ScopArrayInfo::getFromId(isl::id Id) {
384	void *User = Id.get_user();
385	const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
386	return SAI;
387	}
388
389	void MemoryAccess::wrapConstantDimensions() {
390	auto *SAI = getScopArrayInfo();
391	isl::space ArraySpace = SAI->getSpace();
392	isl::ctx Ctx = ArraySpace.ctx();
393	unsigned DimsArray = SAI->getNumberOfDimensions();
394
395	isl::multi_aff DivModAff = isl::multi_aff::identity(
396	space: ArraySpace.map_from_domain_and_range(range: ArraySpace));
397	isl::local_space LArraySpace = isl::local_space(ArraySpace);
398
399	// Begin with last dimension, to iteratively carry into higher dimensions.
400	for (int i = DimsArray - 1; i > 0; i--) {
401	auto *DimSize = SAI->getDimensionSize(Dim: i);
402	auto *DimSizeCst = dyn_cast<SCEVConstant>(Val: DimSize);
403
404	// This transformation is not applicable to dimensions with dynamic size.
405	if (!DimSizeCst)
406	continue;
407
408	// This transformation is not applicable to dimensions of size zero.
409	if (DimSize->isZero())
410	continue;
411
412	isl::val DimSizeVal =
413	valFromAPInt(Ctx: Ctx.get(), Int: DimSizeCst->getAPInt(), IsSigned: false);
414	isl::aff Var = isl::aff::var_on_domain(ls: LArraySpace, type: isl::dim::set, pos: i);
415	isl::aff PrevVar =
416	isl::aff::var_on_domain(ls: LArraySpace, type: isl::dim::set, pos: i - 1);
417
418	// Compute: index % size
419	// Modulo must apply in the divide of the previous iteration, if any.
420	isl::aff Modulo = Var.mod(mod: DimSizeVal);
421	Modulo = Modulo.pullback(ma: DivModAff);
422
423	// Compute: floor(index / size)
424	isl::aff Divide = Var.div(aff2: isl::aff(LArraySpace, DimSizeVal));
425	Divide = Divide.floor();
426	Divide = Divide.add(aff2: PrevVar);
427	Divide = Divide.pullback(ma: DivModAff);
428
429	// Apply Modulo and Divide.
430	DivModAff = DivModAff.set_aff(pos: i, el: Modulo);
431	DivModAff = DivModAff.set_aff(pos: i - 1, el: Divide);
432	}
433
434	// Apply all modulo/divides on the accesses.
435	isl::map Relation = AccessRelation;
436	Relation = Relation.apply_range(map2: isl::map::from_multi_aff(maff: DivModAff));
437	Relation = Relation.detect_equalities();
438	AccessRelation = Relation;
439	}
440
441	void MemoryAccess::updateDimensionality() {
442	auto *SAI = getScopArrayInfo();
443	isl::space ArraySpace = SAI->getSpace();
444	isl::space AccessSpace = AccessRelation.get_space().range();
445	isl::ctx Ctx = ArraySpace.ctx();
446
447	unsigned DimsArray = unsignedFromIslSize(Size: ArraySpace.dim(type: isl::dim::set));
448	unsigned DimsAccess = unsignedFromIslSize(Size: AccessSpace.dim(type: isl::dim::set));
449	assert(DimsArray >= DimsAccess);
450	unsigned DimsMissing = DimsArray - DimsAccess;
451
452	auto *BB = getStatement()->getEntryBlock();
453	auto &DL = BB->getModule()->getDataLayout();
454	unsigned ArrayElemSize = SAI->getElemSizeInBytes();
455	unsigned ElemBytes = DL.getTypeAllocSize(Ty: getElementType());
456
457	isl::map Map = isl::map::from_domain_and_range(
458	domain: isl::set::universe(space: AccessSpace), range: isl::set::universe(space: ArraySpace));
459
460	for (auto i : seq<unsigned>(Begin: 0, End: DimsMissing))
461	Map = Map.fix_si(type: isl::dim::out, pos: i, value: 0);
462
463	for (auto i : seq<unsigned>(Begin: DimsMissing, End: DimsArray))
464	Map = Map.equate(type1: isl::dim::in, pos1: i - DimsMissing, type2: isl::dim::out, pos2: i);
465
466	AccessRelation = AccessRelation.apply_range(map2: Map);
467
468	// For the non delinearized arrays, divide the access function of the last
469	// subscript by the size of the elements in the array.
470	//
471	// A stride one array access in C expressed as A[i] is expressed in
472	// LLVM-IR as something like A[i * elementsize]. This hides the fact that
473	// two subsequent values of 'i' index two values that are stored next to
474	// each other in memory. By this division we make this characteristic
475	// obvious again. If the base pointer was accessed with offsets not divisible
476	// by the accesses element size, we will have chosen a smaller ArrayElemSize
477	// that divides the offsets of all accesses to this base pointer.
478	if (DimsAccess == 1) {
479	isl::val V = isl::val(Ctx, ArrayElemSize);
480	AccessRelation = AccessRelation.floordiv_val(d: V);
481	}
482
483	// We currently do this only if we added at least one dimension, which means
484	// some dimension's indices have not been specified, an indicator that some
485	// index values have been added together.
486	// TODO: Investigate general usefulness; Effect on unit tests is to make index
487	// expressions more complicated.
488	if (DimsMissing)
489	wrapConstantDimensions();
490
491	if (!isAffine())
492	computeBoundsOnAccessRelation(ElementSize: ArrayElemSize);
493
494	// Introduce multi-element accesses in case the type loaded by this memory
495	// access is larger than the canonical element type of the array.
496	//
497	// An access ((float *)A)[i] to an array char *A is modeled as
498	// {[i] -> A[o] : 4 i <= o <= 4 i + 3
499	if (ElemBytes > ArrayElemSize) {
500	assert(ElemBytes % ArrayElemSize == 0 &&
501	"Loaded element size should be multiple of canonical element size");
502	assert(DimsArray >= 1);
503	isl::map Map = isl::map::from_domain_and_range(
504	domain: isl::set::universe(space: ArraySpace), range: isl::set::universe(space: ArraySpace));
505	for (auto i : seq<unsigned>(Begin: 0, End: DimsArray - 1))
506	Map = Map.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
507
508	isl::constraint C;
509	isl::local_space LS;
510
511	LS = isl::local_space(Map.get_space());
512	int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();
513
514	C = isl::constraint::alloc_inequality(ls: LS);
515	C = C.set_constant_val(isl::val(Ctx, Num - 1));
516	C = C.set_coefficient_si(type: isl::dim::in, pos: DimsArray - 1, v: 1);
517	C = C.set_coefficient_si(type: isl::dim::out, pos: DimsArray - 1, v: -1);
518	Map = Map.add_constraint(constraint: C);
519
520	C = isl::constraint::alloc_inequality(ls: LS);
521	C = C.set_coefficient_si(type: isl::dim::in, pos: DimsArray - 1, v: -1);
522	C = C.set_coefficient_si(type: isl::dim::out, pos: DimsArray - 1, v: 1);
523	C = C.set_constant_val(isl::val(Ctx, 0));
524	Map = Map.add_constraint(constraint: C);
525	AccessRelation = AccessRelation.apply_range(map2: Map);
526	}
527	}
528
529	const std::string
530	MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
531	switch (RT) {
532	case MemoryAccess::RT_NONE:
533	llvm_unreachable("Requested a reduction operator string for a memory "
534	"access which isn't a reduction");
535	case MemoryAccess::RT_ADD:
536	return "+";
537	case MemoryAccess::RT_MUL:
538	return "*";
539	case MemoryAccess::RT_BOR:
540	return "|";
541	case MemoryAccess::RT_BXOR:
542	return "^";
543	case MemoryAccess::RT_BAND:
544	return "&";
545	}
546	llvm_unreachable("Unknown reduction type");
547	}
548
549	const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const {
550	isl::id ArrayId = getArrayId();
551	void *User = ArrayId.get_user();
552	const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
553	return SAI;
554	}
555
556	const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {
557	isl::id ArrayId = getLatestArrayId();
558	void *User = ArrayId.get_user();
559	const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
560	return SAI;
561	}
562
563	isl::id MemoryAccess::getOriginalArrayId() const {
564	return AccessRelation.get_tuple_id(type: isl::dim::out);
565	}
566
567	isl::id MemoryAccess::getLatestArrayId() const {
568	if (!hasNewAccessRelation())
569	return getOriginalArrayId();
570	return NewAccessRelation.get_tuple_id(type: isl::dim::out);
571	}
572
573	isl::map MemoryAccess::getAddressFunction() const {
574	return getAccessRelation().lexmin();
575	}
576
577	isl::pw_multi_aff
578	MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule) const {
579	isl::map Schedule, ScheduledAccRel;
580	isl::union_set UDomain;
581
582	UDomain = getStatement()->getDomain();
583	USchedule = USchedule.intersect_domain(uset: UDomain);
584	Schedule = isl::map::from_union_map(umap: USchedule);
585	ScheduledAccRel = getAddressFunction().apply_domain(map2: Schedule);
586	return isl::pw_multi_aff::from_map(map: ScheduledAccRel);
587	}
588
589	isl::map MemoryAccess::getOriginalAccessRelation() const {
590	return AccessRelation;
591	}
592
593	std::string MemoryAccess::getOriginalAccessRelationStr() const {
594	return stringFromIslObj(Obj: AccessRelation);
595	}
596
597	isl::space MemoryAccess::getOriginalAccessRelationSpace() const {
598	return AccessRelation.get_space();
599	}
600
601	isl::map MemoryAccess::getNewAccessRelation() const {
602	return NewAccessRelation;
603	}
604
605	std::string MemoryAccess::getNewAccessRelationStr() const {
606	return stringFromIslObj(Obj: NewAccessRelation);
607	}
608
609	std::string MemoryAccess::getAccessRelationStr() const {
610	return stringFromIslObj(Obj: getAccessRelation());
611	}
612
613	isl::basic_map MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
614	isl::space Space = isl::space(Statement->getIslCtx(), 0, 1);
615	Space = Space.align_params(space2: Statement->getDomainSpace());
616
617	return isl::basic_map::from_domain_and_range(
618	domain: isl::basic_set::universe(space: Statement->getDomainSpace()),
619	range: isl::basic_set::universe(space: Space));
620	}
621
622	// Formalize no out-of-bound access assumption
623	//
624	// When delinearizing array accesses we optimistically assume that the
625	// delinearized accesses do not access out of bound locations (the subscript
626	// expression of each array evaluates for each statement instance that is
627	// executed to a value that is larger than zero and strictly smaller than the
628	// size of the corresponding dimension). The only exception is the outermost
629	// dimension for which we do not need to assume any upper bound. At this point
630	// we formalize this assumption to ensure that at code generation time the
631	// relevant run-time checks can be generated.
632	//
633	// To find the set of constraints necessary to avoid out of bound accesses, we
634	// first build the set of data locations that are not within array bounds. We
635	// then apply the reverse access relation to obtain the set of iterations that
636	// may contain invalid accesses and reduce this set of iterations to the ones
637	// that are actually executed by intersecting them with the domain of the
638	// statement. If we now project out all loop dimensions, we obtain a set of
639	// parameters that may cause statement instances to be executed that may
640	// possibly yield out of bound memory accesses. The complement of these
641	// constraints is the set of constraints that needs to be assumed to ensure such
642	// statement instances are never executed.
643	isl::set MemoryAccess::assumeNoOutOfBound() {
644	auto *SAI = getScopArrayInfo();
645	isl::space Space = getOriginalAccessRelationSpace().range();
646	isl::set Outside = isl::set::empty(space: Space);
647	for (int i = 1, Size = Space.dim(type: isl::dim::set).release(); i < Size; ++i) {
648	isl::local_space LS(Space);
649	isl::pw_aff Var = isl::pw_aff::var_on_domain(ls: LS, type: isl::dim::set, pos: i);
650	isl::pw_aff Zero = isl::pw_aff(LS);
651
652	isl::set DimOutside = Var.lt_set(pwaff2: Zero);
653	isl::pw_aff SizeE = SAI->getDimensionSizePw(Dim: i);
654	SizeE = SizeE.add_dims(type: isl::dim::in, n: Space.dim(type: isl::dim::set).release());
655	SizeE = SizeE.set_tuple_id(type: isl::dim::in, id: Space.get_tuple_id(type: isl::dim::set));
656	DimOutside = DimOutside.unite(set2: SizeE.le_set(pwaff2: Var));
657
658	Outside = Outside.unite(set2: DimOutside);
659	}
660
661	Outside = Outside.apply(map: getAccessRelation().reverse());
662	Outside = Outside.intersect(set2: Statement->getDomain());
663	Outside = Outside.params();
664
665	// Remove divs to avoid the construction of overly complicated assumptions.
666	// Doing so increases the set of parameter combinations that are assumed to
667	// not appear. This is always save, but may make the resulting run-time check
668	// bail out more often than strictly necessary.
669	Outside = Outside.remove_divs();
670	Outside = Outside.complement();
671
672	if (!PollyPreciseInbounds)
673	Outside = Outside.gist_params(context: Statement->getDomain().params());
674	return Outside;
675	}
676
677	void MemoryAccess::buildMemIntrinsicAccessRelation() {
678	assert(isMemoryIntrinsic());
679	assert(Subscripts.size() == 2 && Sizes.size() == 1);
680
681	isl::pw_aff SubscriptPWA = getPwAff(E: Subscripts[0]);
682	isl::map SubscriptMap = isl::map::from_pw_aff(pwaff: SubscriptPWA);
683
684	isl::map LengthMap;
685	if (Subscripts[1] == nullptr) {
686	LengthMap = isl::map::universe(space: SubscriptMap.get_space());
687	} else {
688	isl::pw_aff LengthPWA = getPwAff(E: Subscripts[1]);
689	LengthMap = isl::map::from_pw_aff(pwaff: LengthPWA);
690	isl::space RangeSpace = LengthMap.get_space().range();
691	LengthMap = LengthMap.apply_range(map2: isl::map::lex_gt(set_space: RangeSpace));
692	}
693	LengthMap = LengthMap.lower_bound_si(type: isl::dim::out, pos: 0, value: 0);
694	LengthMap = LengthMap.align_params(model: SubscriptMap.get_space());
695	SubscriptMap = SubscriptMap.align_params(model: LengthMap.get_space());
696	LengthMap = LengthMap.sum(map2: SubscriptMap);
697	AccessRelation =
698	LengthMap.set_tuple_id(type: isl::dim::in, id: getStatement()->getDomainId());
699	}
700
701	void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
702	ScalarEvolution *SE = Statement->getParent()->getSE();
703
704	auto MAI = MemAccInst(getAccessInstruction());
705	if (isa<MemIntrinsic>(Val: MAI))
706	return;
707
708	Value *Ptr = MAI.getPointerOperand();
709	if (!Ptr || !SE->isSCEVable(Ty: Ptr->getType()))
710	return;
711
712	auto *PtrSCEV = SE->getSCEV(V: Ptr);
713	if (isa<SCEVCouldNotCompute>(Val: PtrSCEV))
714	return;
715
716	auto *BasePtrSCEV = SE->getPointerBase(V: PtrSCEV);
717	if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(Val: BasePtrSCEV))
718	PtrSCEV = SE->getMinusSCEV(LHS: PtrSCEV, RHS: BasePtrSCEV);
719
720	const ConstantRange &Range = SE->getSignedRange(S: PtrSCEV);
721	if (Range.isFullSet())
722	return;
723
724	if (Range.isUpperWrapped() || Range.isSignWrappedSet())
725	return;
726
727	bool isWrapping = Range.isSignWrappedSet();
728
729	unsigned BW = Range.getBitWidth();
730	const auto One = APInt(BW, 1);
731	const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
732	const auto UB = isWrapping ? (Range.getUpper() - One) : Range.getSignedMax();
733
734	auto Min = LB.sdiv(RHS: APInt(BW, ElementSize));
735	auto Max = UB.sdiv(RHS: APInt(BW, ElementSize)) + One;
736
737	assert(Min.sle(Max) && "Minimum expected to be less or equal than max");
738
739	isl::map Relation = AccessRelation;
740	isl::set AccessRange = Relation.range();
741	AccessRange = addRangeBoundsToSet(S: AccessRange, Range: ConstantRange(Min, Max), dim: 0,
742	type: isl::dim::set);
743	AccessRelation = Relation.intersect_range(set: AccessRange);
744	}
745
746	void MemoryAccess::foldAccessRelation() {
747	if (Sizes.size() < 2 || isa<SCEVConstant>(Val: Sizes[1]))
748	return;
749
750	int Size = Subscripts.size();
751
752	isl::map NewAccessRelation = AccessRelation;
753
754	for (int i = Size - 2; i >= 0; --i) {
755	isl::space Space;
756	isl::map MapOne, MapTwo;
757	isl::pw_aff DimSize = getPwAff(E: Sizes[i + 1]);
758
759	isl::space SpaceSize = DimSize.get_space();
760	isl::id ParamId = SpaceSize.get_dim_id(type: isl::dim::param, pos: 0);
761
762	Space = AccessRelation.get_space();
763	Space = Space.range().map_from_set();
764	Space = Space.align_params(space2: SpaceSize);
765
766	int ParamLocation = Space.find_dim_by_id(type: isl::dim::param, id: ParamId);
767
768	MapOne = isl::map::universe(space: Space);
769	for (int j = 0; j < Size; ++j)
770	MapOne = MapOne.equate(type1: isl::dim::in, pos1: j, type2: isl::dim::out, pos2: j);
771	MapOne = MapOne.lower_bound_si(type: isl::dim::in, pos: i + 1, value: 0);
772
773	MapTwo = isl::map::universe(space: Space);
774	for (int j = 0; j < Size; ++j)
775	if (j < i || j > i + 1)
776	MapTwo = MapTwo.equate(type1: isl::dim::in, pos1: j, type2: isl::dim::out, pos2: j);
777
778	isl::local_space LS(Space);
779	isl::constraint C;
780	C = isl::constraint::alloc_equality(ls: LS);
781	C = C.set_constant_si(-1);
782	C = C.set_coefficient_si(type: isl::dim::in, pos: i, v: 1);
783	C = C.set_coefficient_si(type: isl::dim::out, pos: i, v: -1);
784	MapTwo = MapTwo.add_constraint(constraint: C);
785	C = isl::constraint::alloc_equality(ls: LS);
786	C = C.set_coefficient_si(type: isl::dim::in, pos: i + 1, v: 1);
787	C = C.set_coefficient_si(type: isl::dim::out, pos: i + 1, v: -1);
788	C = C.set_coefficient_si(type: isl::dim::param, pos: ParamLocation, v: 1);
789	MapTwo = MapTwo.add_constraint(constraint: C);
790	MapTwo = MapTwo.upper_bound_si(type: isl::dim::in, pos: i + 1, value: -1);
791
792	MapOne = MapOne.unite(map2: MapTwo);
793	NewAccessRelation = NewAccessRelation.apply_range(map2: MapOne);
794	}
795
796	isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();
797	isl::space Space = Statement->getDomainSpace();
798	NewAccessRelation = NewAccessRelation.set_tuple_id(
799	type: isl::dim::in, id: Space.get_tuple_id(type: isl::dim::set));
800	NewAccessRelation = NewAccessRelation.set_tuple_id(type: isl::dim::out, id: BaseAddrId);
801	NewAccessRelation = NewAccessRelation.gist_domain(context: Statement->getDomain());
802
803	// Access dimension folding might in certain cases increase the number of
804	// disjuncts in the memory access, which can possibly complicate the generated
805	// run-time checks and can lead to costly compilation.
806	if (!PollyPreciseFoldAccesses && NewAccessRelation.n_basic_map().release() >
807	AccessRelation.n_basic_map().release()) {
808	} else {
809	AccessRelation = NewAccessRelation;
810	}
811	}
812
813	void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
814	assert(AccessRelation.is_null() && "AccessRelation already built");
815
816	// Initialize the invalid domain which describes all iterations for which the
817	// access relation is not modeled correctly.
818	isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();
819	InvalidDomain = isl::set::empty(space: StmtInvalidDomain.get_space());
820
821	isl::ctx Ctx = Id.ctx();
822	isl::id BaseAddrId = SAI->getBasePtrId();
823
824	if (getAccessInstruction() && isa<MemIntrinsic>(Val: getAccessInstruction())) {
825	buildMemIntrinsicAccessRelation();
826	AccessRelation = AccessRelation.set_tuple_id(type: isl::dim::out, id: BaseAddrId);
827	return;
828	}
829
830	if (!isAffine()) {
831	// We overapproximate non-affine accesses with a possible access to the
832	// whole array. For read accesses it does not make a difference, if an
833	// access must or may happen. However, for write accesses it is important to
834	// differentiate between writes that must happen and writes that may happen.
835	if (AccessRelation.is_null())
836	AccessRelation = createBasicAccessMap(Statement);
837
838	AccessRelation = AccessRelation.set_tuple_id(type: isl::dim::out, id: BaseAddrId);
839	return;
840	}
841
842	isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);
843	AccessRelation = isl::map::universe(space: Space);
844
845	for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
846	isl::pw_aff Affine = getPwAff(E: Subscripts[i]);
847	isl::map SubscriptMap = isl::map::from_pw_aff(pwaff: Affine);
848	AccessRelation = AccessRelation.flat_range_product(map2: SubscriptMap);
849	}
850
851	Space = Statement->getDomainSpace();
852	AccessRelation = AccessRelation.set_tuple_id(
853	type: isl::dim::in, id: Space.get_tuple_id(type: isl::dim::set));
854	AccessRelation = AccessRelation.set_tuple_id(type: isl::dim::out, id: BaseAddrId);
855
856	AccessRelation = AccessRelation.gist_domain(context: Statement->getDomain());
857	}
858
859	MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
860	AccessType AccType, Value *BaseAddress,
861	Type *ElementType, bool Affine,
862	ArrayRef<const SCEV *> Subscripts,
863	ArrayRef<const SCEV *> Sizes, Value *AccessValue,
864	MemoryKind Kind)
865	: Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(),
866	BaseAddr(BaseAddress), ElementType(ElementType),
867	Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
868	AccessValue(AccessValue), IsAffine(Affine),
869	Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(),
870	NewAccessRelation() {
871	static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
872	const std::string Access = TypeStrings[AccType] + utostr(X: Stmt->size());
873
874	std::string IdName = Stmt->getBaseName() + Access;
875	Id = isl::id::alloc(ctx: Stmt->getParent()->getIslCtx(), name: IdName, user: this);
876	}
877
878	MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
879	: Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
880	InvalidDomain(), AccessRelation(), NewAccessRelation(AccRel) {
881	isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(type: isl::dim::out);
882	auto *SAI = ScopArrayInfo::getFromId(Id: ArrayInfoId);
883	Sizes.push_back(Elt: nullptr);
884	for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
885	Sizes.push_back(Elt: SAI->getDimensionSize(Dim: i));
886	ElementType = SAI->getElementType();
887	BaseAddr = SAI->getBasePtr();
888	static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
889	const std::string Access = TypeStrings[AccType] + utostr(X: Stmt->size());
890
891	std::string IdName = Stmt->getBaseName() + Access;
892	Id = isl::id::alloc(ctx: Stmt->getParent()->getIslCtx(), name: IdName, user: this);
893	}
894
895	MemoryAccess::~MemoryAccess() = default;
896
897	void MemoryAccess::realignParams() {
898	isl::set Ctx = Statement->getParent()->getContext();
899	InvalidDomain = InvalidDomain.gist_params(context: Ctx);
900	AccessRelation = AccessRelation.gist_params(context: Ctx);
901
902	// Predictable parameter order is required for JSON imports. Ensure alignment
903	// by explicitly calling align_params.
904	isl::space CtxSpace = Ctx.get_space();
905	InvalidDomain = InvalidDomain.align_params(model: CtxSpace);
906	AccessRelation = AccessRelation.align_params(model: CtxSpace);
907	}
908
909	const std::string MemoryAccess::getReductionOperatorStr() const {
910	return MemoryAccess::getReductionOperatorStr(RT: getReductionType());
911	}
912
913	isl::id MemoryAccess::getId() const { return Id; }
914
915	raw_ostream &polly::operator<<(raw_ostream &OS,
916	MemoryAccess::ReductionType RT) {
917	if (RT == MemoryAccess::RT_NONE)
918	OS << "NONE";
919	else
920	OS << MemoryAccess::getReductionOperatorStr(RT);
921	return OS;
922	}
923
924	void MemoryAccess::print(raw_ostream &OS) const {
925	switch (AccType) {
926	case READ:
927	OS.indent(NumSpaces: 12) << "ReadAccess :=\t";
928	break;
929	case MUST_WRITE:
930	OS.indent(NumSpaces: 12) << "MustWriteAccess :=\t";
931	break;
932	case MAY_WRITE:
933	OS.indent(NumSpaces: 12) << "MayWriteAccess :=\t";
934	break;
935	}
936
937	OS << "[Reduction Type: " << getReductionType() << "] ";
938
939	OS << "[Scalar: " << isScalarKind() << "]\n";
940	OS.indent(NumSpaces: 16) << getOriginalAccessRelationStr() << ";\n";
941	if (hasNewAccessRelation())
942	OS.indent(NumSpaces: 11) << "new: " << getNewAccessRelationStr() << ";\n";
943	}
944
945	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
946	LLVM_DUMP_METHOD void MemoryAccess::dump() const { print(OS&: errs()); }
947	#endif
948
949	isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {
950	auto *Stmt = getStatement();
951	PWACtx PWAC = Stmt->getParent()->getPwAff(E, BB: Stmt->getEntryBlock());
952	isl::set StmtDom = getStatement()->getDomain();
953	StmtDom = StmtDom.reset_tuple_id();
954	isl::set NewInvalidDom = StmtDom.intersect(set2: PWAC.second);
955	InvalidDomain = InvalidDomain.unite(set2: NewInvalidDom);
956	return PWAC.first;
957	}
958
959	// Create a map in the size of the provided set domain, that maps from the
960	// one element of the provided set domain to another element of the provided
961	// set domain.
962	// The mapping is limited to all points that are equal in all but the last
963	// dimension and for which the last dimension of the input is strict smaller
964	// than the last dimension of the output.
965	//
966	// getEqualAndLarger(set[i0, i1, ..., iX]):
967	//
968	// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
969	// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
970	//
971	static isl::map getEqualAndLarger(isl::space SetDomain) {
972	isl::space Space = SetDomain.map_from_set();
973	isl::map Map = isl::map::universe(space: Space);
974	unsigned lastDimension = Map.domain_tuple_dim().release() - 1;
975
976	// Set all but the last dimension to be equal for the input and output
977	//
978	// input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
979	// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
980	for (unsigned i = 0; i < lastDimension; ++i)
981	Map = Map.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
982
983	// Set the last dimension of the input to be strict smaller than the
984	// last dimension of the output.
985	//
986	// input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
987	Map = Map.order_lt(type1: isl::dim::in, pos1: lastDimension, type2: isl::dim::out, pos2: lastDimension);
988	return Map;
989	}
990
991	isl::set MemoryAccess::getStride(isl::map Schedule) const {
992	isl::map AccessRelation = getAccessRelation();
993	isl::space Space = Schedule.get_space().range();
994	isl::map NextScatt = getEqualAndLarger(SetDomain: Space);
995
996	Schedule = Schedule.reverse();
997	NextScatt = NextScatt.lexmin();
998
999	NextScatt = NextScatt.apply_range(map2: Schedule);
1000	NextScatt = NextScatt.apply_range(map2: AccessRelation);
1001	NextScatt = NextScatt.apply_domain(map2: Schedule);
1002	NextScatt = NextScatt.apply_domain(map2: AccessRelation);
1003
1004	isl::set Deltas = NextScatt.deltas();
1005	return Deltas;
1006	}
1007
1008	bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {
1009	isl::set Stride, StrideX;
1010	bool IsStrideX;
1011
1012	Stride = getStride(Schedule);
1013	StrideX = isl::set::universe(space: Stride.get_space());
1014	int Size = unsignedFromIslSize(Size: StrideX.tuple_dim());
1015	for (auto i : seq<int>(Begin: 0, End: Size - 1))
1016	StrideX = StrideX.fix_si(type: isl::dim::set, pos: i, value: 0);
1017	StrideX = StrideX.fix_si(type: isl::dim::set, pos: Size - 1, value: StrideWidth);
1018	IsStrideX = Stride.is_subset(set2: StrideX);
1019
1020	return IsStrideX;
1021	}
1022
1023	bool MemoryAccess::isStrideZero(isl::map Schedule) const {
1024	return isStrideX(Schedule, StrideWidth: 0);
1025	}
1026
1027	bool MemoryAccess::isStrideOne(isl::map Schedule) const {
1028	return isStrideX(Schedule, StrideWidth: 1);
1029	}
1030
1031	void MemoryAccess::setAccessRelation(isl::map NewAccess) {
1032	AccessRelation = NewAccess;
1033	}
1034
1035	void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {
1036	assert(!NewAccess.is_null());
1037
1038	#ifndef NDEBUG
1039	// Check domain space compatibility.
1040	isl::space NewSpace = NewAccess.get_space();
1041	isl::space NewDomainSpace = NewSpace.domain();
1042	isl::space OriginalDomainSpace = getStatement()->getDomainSpace();
1043	assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace));
1044
1045	// Reads must be executed unconditionally. Writes might be executed in a
1046	// subdomain only.
1047	if (isRead()) {
1048	// Check whether there is an access for every statement instance.
1049	isl::set StmtDomain = getStatement()->getDomain();
1050	isl::set DefinedContext =
1051	getStatement()->getParent()->getBestKnownDefinedBehaviorContext();
1052	StmtDomain = StmtDomain.intersect_params(params: DefinedContext);
1053	isl::set NewDomain = NewAccess.domain();
1054	assert(!StmtDomain.is_subset(NewDomain).is_false() &&
1055	"Partial READ accesses not supported");
1056	}
1057
1058	isl::space NewAccessSpace = NewAccess.get_space();
1059	assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&
1060	"Must specify the array that is accessed");
1061	isl::id NewArrayId = NewAccessSpace.get_tuple_id(type: isl::dim::set);
1062	auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());
1063	assert(SAI && "Must set a ScopArrayInfo");
1064
1065	if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
1066	InvariantEquivClassTy *EqClass =
1067	getStatement()->getParent()->lookupInvariantEquivClass(
1068	Val: SAI->getBasePtr());
1069	assert(EqClass &&
1070	"Access functions to indirect arrays must have an invariant and "
1071	"hoisted base pointer");
1072	}
1073
1074	// Check whether access dimensions correspond to number of dimensions of the
1075	// accesses array.
1076	unsigned Dims = SAI->getNumberOfDimensions();
1077	unsigned SpaceSize = unsignedFromIslSize(Size: NewAccessSpace.dim(type: isl::dim::set));
1078	assert(SpaceSize == Dims && "Access dims must match array dims");
1079	#endif
1080
1081	NewAccess = NewAccess.gist_params(context: getStatement()->getParent()->getContext());
1082	NewAccess = NewAccess.gist_domain(context: getStatement()->getDomain());
1083	NewAccessRelation = NewAccess;
1084	}
1085
1086	bool MemoryAccess::isLatestPartialAccess() const {
1087	isl::set StmtDom = getStatement()->getDomain();
1088	isl::set AccDom = getLatestAccessRelation().domain();
1089
1090	return !StmtDom.is_subset(set2: AccDom);
1091	}
1092
1093	//===----------------------------------------------------------------------===//
1094
1095	isl::map ScopStmt::getSchedule() const {
1096	isl::set Domain = getDomain();
1097	if (Domain.is_empty())
1098	return isl::map::from_aff(aff: isl::aff(isl::local_space(getDomainSpace())));
1099	auto Schedule = getParent()->getSchedule();
1100	if (Schedule.is_null())
1101	return {};
1102	Schedule = Schedule.intersect_domain(uset: isl::union_set(Domain));
1103	if (Schedule.is_empty())
1104	return isl::map::from_aff(aff: isl::aff(isl::local_space(getDomainSpace())));
1105	isl::map M = M.from_union_map(umap: Schedule);
1106	M = M.coalesce();
1107	M = M.gist_domain(context: Domain);
1108	M = M.coalesce();
1109	return M;
1110	}
1111
1112	void ScopStmt::restrictDomain(isl::set NewDomain) {
1113	assert(NewDomain.is_subset(Domain) &&
1114	"New domain is not a subset of old domain!");
1115	Domain = NewDomain;
1116	}
1117
1118	void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
1119	Instruction *AccessInst = Access->getAccessInstruction();
1120
1121	if (Access->isArrayKind()) {
1122	MemoryAccessList &MAL = InstructionToAccess[AccessInst];
1123	MAL.emplace_front(args&: Access);
1124	} else if (Access->isValueKind() && Access->isWrite()) {
1125	Instruction *AccessVal = cast<Instruction>(Val: Access->getAccessValue());
1126	assert(!ValueWrites.lookup(AccessVal));
1127
1128	ValueWrites[AccessVal] = Access;
1129	} else if (Access->isValueKind() && Access->isRead()) {
1130	Value *AccessVal = Access->getAccessValue();
1131	assert(!ValueReads.lookup(AccessVal));
1132
1133	ValueReads[AccessVal] = Access;
1134	} else if (Access->isAnyPHIKind() && Access->isWrite()) {
1135	PHINode *PHI = cast<PHINode>(Val: Access->getAccessValue());
1136	assert(!PHIWrites.lookup(PHI));
1137
1138	PHIWrites[PHI] = Access;
1139	} else if (Access->isAnyPHIKind() && Access->isRead()) {
1140	PHINode *PHI = cast<PHINode>(Val: Access->getAccessValue());
1141	assert(!PHIReads.lookup(PHI));
1142
1143	PHIReads[PHI] = Access;
1144	}
1145
1146	if (Prepend) {
1147	MemAccs.insert(I: MemAccs.begin(), Elt: Access);
1148	return;
1149	}
1150	MemAccs.push_back(Elt: Access);
1151	}
1152
1153	void ScopStmt::realignParams() {
1154	for (MemoryAccess *MA : *this)
1155	MA->realignParams();
1156
1157	simplify(Set&: InvalidDomain);
1158	simplify(Set&: Domain);
1159
1160	isl::set Ctx = Parent.getContext();
1161	InvalidDomain = InvalidDomain.gist_params(context: Ctx);
1162	Domain = Domain.gist_params(context: Ctx);
1163
1164	// Predictable parameter order is required for JSON imports. Ensure alignment
1165	// by explicitly calling align_params.
1166	isl::space CtxSpace = Ctx.get_space();
1167	InvalidDomain = InvalidDomain.align_params(model: CtxSpace);
1168	Domain = Domain.align_params(model: CtxSpace);
1169	}
1170
1171	ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
1172	Loop *SurroundingLoop,
1173	std::vector<Instruction *> EntryBlockInstructions)
1174	: Parent(parent), InvalidDomain(), Domain(), R(&R), Build(), BaseName(Name),
1175	SurroundingLoop(SurroundingLoop), Instructions(EntryBlockInstructions) {}
1176
1177	ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
1178	Loop *SurroundingLoop,
1179	std::vector<Instruction *> Instructions)
1180	: Parent(parent), InvalidDomain(), Domain(), BB(&bb), Build(),
1181	BaseName(Name), SurroundingLoop(SurroundingLoop),
1182	Instructions(Instructions) {}
1183
1184	ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
1185	isl::set NewDomain)
1186	: Parent(parent), InvalidDomain(), Domain(NewDomain), Build() {
1187	BaseName = getIslCompatibleName(Prefix: "CopyStmt_", Middle: "",
1188	Suffix: std::to_string(val: parent.getCopyStmtsNum()));
1189	isl::id Id = isl::id::alloc(ctx: getIslCtx(), name: getBaseName(), user: this);
1190	Domain = Domain.set_tuple_id(Id);
1191	TargetRel = TargetRel.set_tuple_id(type: isl::dim::in, id: Id);
1192	auto *Access =
1193	new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
1194	parent.addAccessFunction(Access);
1195	addAccess(Access);
1196	SourceRel = SourceRel.set_tuple_id(type: isl::dim::in, id: Id);
1197	Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
1198	parent.addAccessFunction(Access);
1199	addAccess(Access);
1200	}
1201
1202	ScopStmt::~ScopStmt() = default;
1203
1204	std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Obj: Domain); }
1205
1206	std::string ScopStmt::getScheduleStr() const {
1207	return stringFromIslObj(Obj: getSchedule());
1208	}
1209
1210	void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
1211
1212	BasicBlock *ScopStmt::getEntryBlock() const {
1213	if (isBlockStmt())
1214	return getBasicBlock();
1215	return getRegion()->getEntry();
1216	}
1217
1218	unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
1219
1220	const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1221
1222	Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
1223	return NestLoops[Dimension];
1224	}
1225
1226	isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
1227
1228	isl::set ScopStmt::getDomain() const { return Domain; }
1229
1230	isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }
1231
1232	isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }
1233
1234	void ScopStmt::printInstructions(raw_ostream &OS) const {
1235	OS << "Instructions {\n";
1236
1237	for (Instruction *Inst : Instructions)
1238	OS.indent(NumSpaces: 16) << *Inst << "\n";
1239
1240	OS.indent(NumSpaces: 12) << "}\n";
1241	}
1242
1243	void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
1244	OS << "\t" << getBaseName() << "\n";
1245	OS.indent(NumSpaces: 12) << "Domain :=\n";
1246
1247	if (!Domain.is_null()) {
1248	OS.indent(NumSpaces: 16) << getDomainStr() << ";\n";
1249	} else
1250	OS.indent(NumSpaces: 16) << "n/a\n";
1251
1252	OS.indent(NumSpaces: 12) << "Schedule :=\n";
1253
1254	if (!Domain.is_null()) {
1255	OS.indent(NumSpaces: 16) << getScheduleStr() << ";\n";
1256	} else
1257	OS.indent(NumSpaces: 16) << "n/a\n";
1258
1259	for (MemoryAccess *Access : MemAccs)
1260	Access->print(OS);
1261
1262	if (PrintInstructions)
1263	printInstructions(OS&: OS.indent(NumSpaces: 12));
1264	}
1265
1266	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1267	LLVM_DUMP_METHOD void ScopStmt::dump() const { print(OS&: dbgs(), PrintInstructions: true); }
1268	#endif
1269
1270	void ScopStmt::removeAccessData(MemoryAccess *MA) {
1271	if (MA->isRead() && MA->isOriginalValueKind()) {
1272	bool Found = ValueReads.erase(Val: MA->getAccessValue());
1273	(void)Found;
1274	assert(Found && "Expected access data not found");
1275	}
1276	if (MA->isWrite() && MA->isOriginalValueKind()) {
1277	bool Found = ValueWrites.erase(Val: cast<Instruction>(Val: MA->getAccessValue()));
1278	(void)Found;
1279	assert(Found && "Expected access data not found");
1280	}
1281	if (MA->isWrite() && MA->isOriginalAnyPHIKind()) {
1282	bool Found = PHIWrites.erase(Val: cast<PHINode>(Val: MA->getAccessInstruction()));
1283	(void)Found;
1284	assert(Found && "Expected access data not found");
1285	}
1286	if (MA->isRead() && MA->isOriginalAnyPHIKind()) {
1287	bool Found = PHIReads.erase(Val: cast<PHINode>(Val: MA->getAccessInstruction()));
1288	(void)Found;
1289	assert(Found && "Expected access data not found");
1290	}
1291	}
1292
1293	void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {
1294	// Remove the memory accesses from this statement together with all scalar
1295	// accesses that were caused by it. MemoryKind::Value READs have no access
1296	// instruction, hence would not be removed by this function. However, it is
1297	// only used for invariant LoadInst accesses, its arguments are always affine,
1298	// hence synthesizable, and therefore there are no MemoryKind::Value READ
1299	// accesses to be removed.
1300	auto Predicate = [&](MemoryAccess *Acc) {
1301	return Acc->getAccessInstruction() == MA->getAccessInstruction();
1302	};
1303	for (auto *MA : MemAccs) {
1304	if (Predicate(MA)) {
1305	removeAccessData(MA);
1306	Parent.removeAccessData(Access: MA);
1307	}
1308	}
1309	llvm::erase_if(C&: MemAccs, P: Predicate);
1310	InstructionToAccess.erase(Val: MA->getAccessInstruction());
1311	}
1312
1313	void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
1314	if (AfterHoisting) {
1315	auto MAIt = std::find(first: MemAccs.begin(), last: MemAccs.end(), val: MA);
1316	assert(MAIt != MemAccs.end());
1317	MemAccs.erase(CI: MAIt);
1318
1319	removeAccessData(MA);
1320	Parent.removeAccessData(Access: MA);
1321	}
1322
1323	auto It = InstructionToAccess.find(Val: MA->getAccessInstruction());
1324	if (It != InstructionToAccess.end()) {
1325	It->second.remove(val: MA);
1326	if (It->second.empty())
1327	InstructionToAccess.erase(Val: MA->getAccessInstruction());
1328	}
1329	}
1330
1331	MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
1332	MemoryAccess *Access = lookupInputAccessOf(Val: V);
1333	if (Access)
1334	return Access;
1335
1336	ScopArrayInfo *SAI =
1337	Parent.getOrCreateScopArrayInfo(BasePtr: V, ElementType: V->getType(), Sizes: {}, Kind: MemoryKind::Value);
1338	Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
1339	true, {}, {}, V, MemoryKind::Value);
1340	Parent.addAccessFunction(Access);
1341	Access->buildAccessRelation(SAI);
1342	addAccess(Access);
1343	Parent.addAccessData(Access);
1344	return Access;
1345	}
1346
1347	raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
1348	S.print(OS, PrintInstructions: PollyPrintInstructions);
1349	return OS;
1350	}
1351
1352	//===----------------------------------------------------------------------===//
1353	/// Scop class implement
1354
1355	void Scop::setContext(isl::set NewContext) {
1356	Context = NewContext.align_params(model: Context.get_space());
1357	}
1358
1359	namespace {
1360
1361	/// Remap parameter values but keep AddRecs valid wrt. invariant loads.
1362	class SCEVSensitiveParameterRewriter final
1363	: public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
1364	const ValueToValueMap &VMap;
1365
1366	public:
1367	SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,
1368	ScalarEvolution &SE)
1369	: SCEVRewriteVisitor(SE), VMap(VMap) {}
1370
1371	static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,
1372	const ValueToValueMap &VMap) {
1373	SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1374	return SSPR.visit(S: E);
1375	}
1376
1377	const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
1378	auto *Start = visit(S: E->getStart());
1379	auto *AddRec = SE.getAddRecExpr(Start: SE.getConstant(Ty: E->getType(), V: 0),
1380	Step: visit(S: E->getStepRecurrence(SE)),
1381	L: E->getLoop(), Flags: SCEV::FlagAnyWrap);
1382	return SE.getAddExpr(LHS: Start, RHS: AddRec);
1383	}
1384
1385	const SCEV *visitUnknown(const SCEVUnknown *E) {
1386	if (auto *NewValue = VMap.lookup(Val: E->getValue()))
1387	return SE.getUnknown(V: NewValue);
1388	return E;
1389	}
1390	};
1391
1392	/// Check whether we should remap a SCEV expression.
1393	class SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
1394	const ValueToValueMap &VMap;
1395	bool FoundInside = false;
1396	const Scop *S;
1397
1398	public:
1399	SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,
1400	const Scop *S)
1401	: SCEVTraversal(*this), VMap(VMap), S(S) {}
1402
1403	static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
1404	const ValueToValueMap &VMap, const Scop *S) {
1405	SCEVFindInsideScop SFIS(VMap, SE, S);
1406	SFIS.visitAll(Root: E);
1407	return SFIS.FoundInside;
1408	}
1409
1410	bool follow(const SCEV *E) {
1411	if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: E)) {
1412	FoundInside |= S->getRegion().contains(L: AddRec->getLoop());
1413	} else if (auto *Unknown = dyn_cast<SCEVUnknown>(Val: E)) {
1414	if (Instruction *I = dyn_cast<Instruction>(Val: Unknown->getValue()))
1415	FoundInside |= S->getRegion().contains(Inst: I) && !VMap.count(Val: I);
1416	}
1417	return !FoundInside;
1418	}
1419
1420	bool isDone() { return FoundInside; }
1421	};
1422	} // end anonymous namespace
1423
1424	const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {
1425	// Check whether it makes sense to rewrite the SCEV. (ScalarEvolution
1426	// doesn't like addition between an AddRec and an expression that
1427	// doesn't have a dominance relationship with it.)
1428	if (SCEVFindInsideScop::hasVariant(E, SE&: *SE, VMap: InvEquivClassVMap, S: this))
1429	return E;
1430
1431	// Rewrite SCEV.
1432	return SCEVSensitiveParameterRewriter::rewrite(E, SE&: *SE, VMap: InvEquivClassVMap);
1433	}
1434
1435	void Scop::createParameterId(const SCEV *Parameter) {
1436	assert(Parameters.count(Parameter));
1437	assert(!ParameterIds.count(Parameter));
1438
1439	std::string ParameterName = "p_" + std::to_string(val: getNumParams() - 1);
1440
1441	if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Val: Parameter)) {
1442	Value *Val = ValueParameter->getValue();
1443
1444	if (UseInstructionNames) {
1445	// If this parameter references a specific Value and this value has a name
1446	// we use this name as it is likely to be unique and more useful than just
1447	// a number.
1448	if (Val->hasName())
1449	ParameterName = Val->getName().str();
1450	else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1451	auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1452	if (LoadOrigin->hasName()) {
1453	ParameterName += "_loaded_from_";
1454	ParameterName +=
1455	LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1456	}
1457	}
1458	}
1459
1460	ParameterName = getIslCompatibleName(Prefix: "", Middle: ParameterName, Suffix: "");
1461	}
1462
1463	isl::id Id = isl::id::alloc(ctx: getIslCtx(), name: ParameterName,
1464	user: const_cast<void *>((const void *)Parameter));
1465	ParameterIds[Parameter] = Id;
1466	}
1467
1468	void Scop::addParams(const ParameterSetTy &NewParameters) {
1469	for (const SCEV *Parameter : NewParameters) {
1470	// Normalize the SCEV to get the representing element for an invariant load.
1471	Parameter = extractConstantFactor(M: Parameter, SE&: *SE).second;
1472	Parameter = getRepresentingInvariantLoadSCEV(E: Parameter);
1473
1474	if (Parameters.insert(X: Parameter))
1475	createParameterId(Parameter);
1476	}
1477	}
1478
1479	isl::id Scop::getIdForParam(const SCEV *Parameter) const {
1480	// Normalize the SCEV to get the representing element for an invariant load.
1481	Parameter = getRepresentingInvariantLoadSCEV(E: Parameter);
1482	return ParameterIds.lookup(Val: Parameter);
1483	}
1484
1485	bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
1486	return DT.dominates(A: BB, B: getEntry());
1487	}
1488
1489	void Scop::buildContext() {
1490	isl::space Space = isl::space::params_alloc(ctx: getIslCtx(), nparam: 0);
1491	Context = isl::set::universe(space: Space);
1492	InvalidContext = isl::set::empty(space: Space);
1493	AssumedContext = isl::set::universe(space: Space);
1494	DefinedBehaviorContext = isl::set::universe(space: Space);
1495	}
1496
1497	void Scop::addParameterBounds() {
1498	unsigned PDim = 0;
1499	for (auto *Parameter : Parameters) {
1500	ConstantRange SRange = SE->getSignedRange(S: Parameter);
1501	Context = addRangeBoundsToSet(S: Context, Range: SRange, dim: PDim++, type: isl::dim::param);
1502	}
1503	intersectDefinedBehavior(Set: Context, Sign: AS_ASSUMPTION);
1504	}
1505
1506	void Scop::realignParams() {
1507	if (PollyIgnoreParamBounds)
1508	return;
1509
1510	// Add all parameters into a common model.
1511	isl::space Space = getFullParamSpace();
1512
1513	// Align the parameters of all data structures to the model.
1514	Context = Context.align_params(model: Space);
1515	AssumedContext = AssumedContext.align_params(model: Space);
1516	InvalidContext = InvalidContext.align_params(model: Space);
1517
1518	// As all parameters are known add bounds to them.
1519	addParameterBounds();
1520
1521	for (ScopStmt &Stmt : *this)
1522	Stmt.realignParams();
1523	// Simplify the schedule according to the context too.
1524	Schedule = Schedule.gist_domain_params(context: getContext());
1525
1526	// Predictable parameter order is required for JSON imports. Ensure alignment
1527	// by explicitly calling align_params.
1528	Schedule = Schedule.align_params(space: Space);
1529	}
1530
1531	static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
1532	const Scop &S) {
1533	// If we have modeled all blocks in the SCoP that have side effects we can
1534	// simplify the context with the constraints that are needed for anything to
1535	// be executed at all. However, if we have error blocks in the SCoP we already
1536	// assumed some parameter combinations cannot occur and removed them from the
1537	// domains, thus we cannot use the remaining domain to simplify the
1538	// assumptions.
1539	if (!S.hasErrorBlock()) {
1540	auto DomainParameters = S.getDomains().params();
1541	AssumptionContext = AssumptionContext.gist_params(context: DomainParameters);
1542	}
1543
1544	AssumptionContext = AssumptionContext.gist_params(context: S.getContext());
1545	return AssumptionContext;
1546	}
1547
1548	void Scop::simplifyContexts() {
1549	// The parameter constraints of the iteration domains give us a set of
1550	// constraints that need to hold for all cases where at least a single
1551	// statement iteration is executed in the whole scop. We now simplify the
1552	// assumed context under the assumption that such constraints hold and at
1553	// least a single statement iteration is executed. For cases where no
1554	// statement instances are executed, the assumptions we have taken about
1555	// the executed code do not matter and can be changed.
1556	//
1557	// WARNING: This only holds if the assumptions we have taken do not reduce
1558	// the set of statement instances that are executed. Otherwise we
1559	// may run into a case where the iteration domains suggest that
1560	// for a certain set of parameter constraints no code is executed,
1561	// but in the original program some computation would have been
1562	// performed. In such a case, modifying the run-time conditions and
1563	// possibly influencing the run-time check may cause certain scops
1564	// to not be executed.
1565	//
1566	// Example:
1567	//
1568	// When delinearizing the following code:
1569	//
1570	// for (long i = 0; i < 100; i++)
1571	// for (long j = 0; j < m; j++)
1572	// A[i+p][j] = 1.0;
1573	//
1574	// we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
1575	// otherwise we would access out of bound data. Now, knowing that code is
1576	// only executed for the case m >= 0, it is sufficient to assume p >= 0.
1577	AssumedContext = simplifyAssumptionContext(AssumptionContext: AssumedContext, S: *this);
1578	InvalidContext = InvalidContext.align_params(model: getParamSpace());
1579	simplify(Set&: DefinedBehaviorContext);
1580	DefinedBehaviorContext = DefinedBehaviorContext.align_params(model: getParamSpace());
1581	}
1582
1583	isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
1584	return getDomainConditions(BB: Stmt->getEntryBlock());
1585	}
1586
1587	isl::set Scop::getDomainConditions(BasicBlock *BB) const {
1588	auto DIt = DomainMap.find(Val: BB);
1589	if (DIt != DomainMap.end())
1590	return DIt->getSecond();
1591
1592	auto &RI = *R.getRegionInfo();
1593	auto *BBR = RI.getRegionFor(BB);
1594	while (BBR->getEntry() == BB)
1595	BBR = BBR->getParent();
1596	return getDomainConditions(BB: BBR->getEntry());
1597	}
1598
1599	Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
1600	DominatorTree &DT, ScopDetection::DetectionContext &DC,
1601	OptimizationRemarkEmitter &ORE, int ID)
1602	: IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
1603	R(R), name(std::nullopt), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
1604	ORE(ORE), Affinator(this, LI), ID(ID) {
1605
1606	// Options defaults that are different from ISL's.
1607	isl_options_set_schedule_serialize_sccs(ctx: IslCtx.get(), val: true);
1608
1609	SmallVector<char *, 8> IslArgv;
1610	IslArgv.reserve(N: 1 + IslArgs.size());
1611
1612	// Substitute for program name.
1613	IslArgv.push_back(Elt: const_cast<char *>("-polly-isl-arg"));
1614
1615	for (std::string &Arg : IslArgs)
1616	IslArgv.push_back(Elt: const_cast<char *>(Arg.c_str()));
1617
1618	// Abort if unknown argument is passed.
1619	// Note that "-V" (print isl version) will always call exit(0), so we cannot
1620	// avoid ISL aborting the program at this point.
1621	unsigned IslParseFlags = ISL_ARG_ALL;
1622
1623	isl_ctx_parse_options(ctx: IslCtx.get(), argc: IslArgv.size(), argv: IslArgv.data(),
1624	flags: IslParseFlags);
1625
1626	if (IslOnErrorAbort)
1627	isl_options_set_on_error(ctx: getIslCtx().get(), ISL_ON_ERROR_ABORT);
1628	buildContext();
1629	}
1630
1631	Scop::~Scop() = default;
1632
1633	void Scop::removeFromStmtMap(ScopStmt &Stmt) {
1634	for (Instruction *Inst : Stmt.getInstructions())
1635	InstStmtMap.erase(Val: Inst);
1636
1637	if (Stmt.isRegionStmt()) {
1638	for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
1639	StmtMap.erase(Val: BB);
1640	// Skip entry basic block, as its instructions are already deleted as
1641	// part of the statement's instruction list.
1642	if (BB == Stmt.getEntryBlock())
1643	continue;
1644	for (Instruction &Inst : *BB)
1645	InstStmtMap.erase(Val: &Inst);
1646	}
1647	} else {
1648	auto StmtMapIt = StmtMap.find(Val: Stmt.getBasicBlock());
1649	if (StmtMapIt != StmtMap.end())
1650	llvm::erase(C&: StmtMapIt->second, V: &Stmt);
1651	for (Instruction *Inst : Stmt.getInstructions())
1652	InstStmtMap.erase(Val: Inst);
1653	}
1654	}
1655
1656	void Scop::removeStmts(function_ref<bool(ScopStmt &)> ShouldDelete,
1657	bool AfterHoisting) {
1658	for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
1659	if (!ShouldDelete(*StmtIt)) {
1660	StmtIt++;
1661	continue;
1662	}
1663
1664	// Start with removing all of the statement's accesses including erasing it
1665	// from all maps that are pointing to them.
1666	// Make a temporary copy because removing MAs invalidates the iterator.
1667	SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());
1668	for (MemoryAccess *MA : MAList)
1669	StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);
1670
1671	removeFromStmtMap(Stmt&: *StmtIt);
1672	StmtIt = Stmts.erase(position: StmtIt);
1673	}
1674	}
1675
1676	void Scop::removeStmtNotInDomainMap() {
1677	removeStmts(ShouldDelete: [this](ScopStmt &Stmt) -> bool {
1678	isl::set Domain = DomainMap.lookup(Val: Stmt.getEntryBlock());
1679	if (Domain.is_null())
1680	return true;
1681	return Domain.is_empty();
1682	});
1683	}
1684
1685	void Scop::simplifySCoP(bool AfterHoisting) {
1686	removeStmts(
1687	ShouldDelete: [AfterHoisting](ScopStmt &Stmt) -> bool {
1688	// Never delete statements that contain calls to debug functions.
1689	if (hasDebugCall(Stmt: &Stmt))
1690	return false;
1691
1692	bool RemoveStmt = Stmt.isEmpty();
1693
1694	// Remove read only statements only after invariant load hoisting.
1695	if (!RemoveStmt && AfterHoisting) {
1696	bool OnlyRead = true;
1697	for (MemoryAccess *MA : Stmt) {
1698	if (MA->isRead())
1699	continue;
1700
1701	OnlyRead = false;
1702	break;
1703	}
1704
1705	RemoveStmt = OnlyRead;
1706	}
1707	return RemoveStmt;
1708	},
1709	AfterHoisting);
1710	}
1711
1712	InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {
1713	LoadInst *LInst = dyn_cast<LoadInst>(Val);
1714	if (!LInst)
1715	return nullptr;
1716
1717	if (Value *Rep = InvEquivClassVMap.lookup(Val: LInst))
1718	LInst = cast<LoadInst>(Val: Rep);
1719
1720	Type *Ty = LInst->getType();
1721	const SCEV *PointerSCEV = SE->getSCEV(V: LInst->getPointerOperand());
1722	for (auto &IAClass : InvariantEquivClasses) {
1723	if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
1724	continue;
1725
1726	auto &MAs = IAClass.InvariantAccesses;
1727	for (auto *MA : MAs)
1728	if (MA->getAccessInstruction() == Val)
1729	return &IAClass;
1730	}
1731
1732	return nullptr;
1733	}
1734
1735	ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
1736	ArrayRef<const SCEV *> Sizes,
1737	MemoryKind Kind,
1738	const char *BaseName) {
1739	assert((BasePtr || BaseName) &&
1740	"BasePtr and BaseName can not be nullptr at the same time.");
1741	assert(!(BasePtr && BaseName) && "BaseName is redundant.");
1742	auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(x&: BasePtr, y&: Kind)]
1743	: ScopArrayNameMap[BaseName];
1744	if (!SAI) {
1745	auto &DL = getFunction().getParent()->getDataLayout();
1746	SAI.reset(p: new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
1747	DL, this, BaseName));
1748	ScopArrayInfoSet.insert(X: SAI.get());
1749	} else {
1750	SAI->updateElementType(NewElementType: ElementType);
1751	// In case of mismatching array sizes, we bail out by setting the run-time
1752	// context to false.
1753	if (!SAI->updateSizes(NewSizes: Sizes))
1754	invalidate(Kind: DELINEARIZATION, Loc: DebugLoc());
1755	}
1756	return SAI.get();
1757	}
1758
1759	ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,
1760	const std::string &BaseName,
1761	const std::vector<unsigned> &Sizes) {
1762	auto *DimSizeType = Type::getInt64Ty(C&: getSE()->getContext());
1763	std::vector<const SCEV *> SCEVSizes;
1764
1765	for (auto size : Sizes)
1766	if (size)
1767	SCEVSizes.push_back(x: getSE()->getConstant(Ty: DimSizeType, V: size, isSigned: false));
1768	else
1769	SCEVSizes.push_back(x: nullptr);
1770
1771	auto *SAI = getOrCreateScopArrayInfo(BasePtr: nullptr, ElementType, Sizes: SCEVSizes,
1772	Kind: MemoryKind::Array, BaseName: BaseName.c_str());
1773	return SAI;
1774	}
1775
1776	ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind) {
1777	auto *SAI = ScopArrayInfoMap[std::make_pair(x&: BasePtr, y&: Kind)].get();
1778	return SAI;
1779	}
1780
1781	ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
1782	auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);
1783	assert(SAI && "No ScopArrayInfo available for this base pointer");
1784	return SAI;
1785	}
1786
1787	std::string Scop::getContextStr() const {
1788	return stringFromIslObj(Obj: getContext());
1789	}
1790
1791	std::string Scop::getAssumedContextStr() const {
1792	assert(!AssumedContext.is_null() && "Assumed context not yet built");
1793	return stringFromIslObj(Obj: AssumedContext);
1794	}
1795
1796	std::string Scop::getInvalidContextStr() const {
1797	return stringFromIslObj(Obj: InvalidContext);
1798	}
1799
1800	std::string Scop::getNameStr() const {
1801	std::string ExitName, EntryName;
1802	std::tie(args&: EntryName, args&: ExitName) = getEntryExitStr();
1803	return EntryName + "---" + ExitName;
1804	}
1805
1806	std::pair<std::string, std::string> Scop::getEntryExitStr() const {
1807	std::string ExitName, EntryName;
1808	raw_string_ostream ExitStr(ExitName);
1809	raw_string_ostream EntryStr(EntryName);
1810
1811	R.getEntry()->printAsOperand(O&: EntryStr, PrintType: false);
1812	EntryStr.str();
1813
1814	if (R.getExit()) {
1815	R.getExit()->printAsOperand(O&: ExitStr, PrintType: false);
1816	ExitStr.str();
1817	} else
1818	ExitName = "FunctionExit";
1819
1820	return std::make_pair(x&: EntryName, y&: ExitName);
1821	}
1822
1823	isl::set Scop::getContext() const { return Context; }
1824
1825	isl::space Scop::getParamSpace() const { return getContext().get_space(); }
1826
1827	isl::space Scop::getFullParamSpace() const {
1828
1829	isl::space Space = isl::space::params_alloc(ctx: getIslCtx(), nparam: ParameterIds.size());
1830
1831	unsigned PDim = 0;
1832	for (const SCEV *Parameter : Parameters) {
1833	isl::id Id = getIdForParam(Parameter);
1834	Space = Space.set_dim_id(type: isl::dim::param, pos: PDim++, id: Id);
1835	}
1836
1837	return Space;
1838	}
1839
1840	isl::set Scop::getAssumedContext() const {
1841	assert(!AssumedContext.is_null() && "Assumed context not yet built");
1842	return AssumedContext;
1843	}
1844
1845	bool Scop::isProfitable(bool ScalarsAreUnprofitable) const {
1846	if (PollyProcessUnprofitable)
1847	return true;
1848
1849	if (isEmpty())
1850	return false;
1851
1852	unsigned OptimizableStmtsOrLoops = 0;
1853	for (auto &Stmt : *this) {
1854	if (Stmt.getNumIterators() == 0)
1855	continue;
1856
1857	bool ContainsArrayAccs = false;
1858	bool ContainsScalarAccs = false;
1859	for (auto *MA : Stmt) {
1860	if (MA->isRead())
1861	continue;
1862	ContainsArrayAccs |= MA->isLatestArrayKind();
1863	ContainsScalarAccs |= MA->isLatestScalarKind();
1864	}
1865
1866	if (!ScalarsAreUnprofitable || (ContainsArrayAccs && !ContainsScalarAccs))
1867	OptimizableStmtsOrLoops += Stmt.getNumIterators();
1868	}
1869
1870	return OptimizableStmtsOrLoops > 1;
1871	}
1872
1873	bool Scop::hasFeasibleRuntimeContext() const {
1874	if (Stmts.empty())
1875	return false;
1876
1877	isl::set PositiveContext = getAssumedContext();
1878	isl::set NegativeContext = getInvalidContext();
1879	PositiveContext = PositiveContext.intersect_params(params: Context);
1880	PositiveContext = PositiveContext.intersect_params(params: getDomains().params());
1881	return PositiveContext.is_empty().is_false() &&
1882	PositiveContext.is_subset(set2: NegativeContext).is_false();
1883	}
1884
1885	MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
1886	Value *PointerBase = MA->getOriginalBaseAddr();
1887
1888	auto *PointerBaseInst = dyn_cast<Instruction>(Val: PointerBase);
1889	if (!PointerBaseInst)
1890	return nullptr;
1891
1892	auto *BasePtrStmt = getStmtFor(Inst: PointerBaseInst);
1893	if (!BasePtrStmt)
1894	return nullptr;
1895
1896	return BasePtrStmt->getArrayAccessOrNULLFor(Inst: PointerBaseInst);
1897	}
1898
1899	static std::string toString(AssumptionKind Kind) {
1900	switch (Kind) {
1901	case ALIASING:
1902	return "No-aliasing";
1903	case INBOUNDS:
1904	return "Inbounds";
1905	case WRAPPING:
1906	return "No-overflows";
1907	case UNSIGNED:
1908	return "Signed-unsigned";
1909	case COMPLEXITY:
1910	return "Low complexity";
1911	case PROFITABLE:
1912	return "Profitable";
1913	case ERRORBLOCK:
1914	return "No-error";
1915	case INFINITELOOP:
1916	return "Finite loop";
1917	case INVARIANTLOAD:
1918	return "Invariant load";
1919	case DELINEARIZATION:
1920	return "Delinearization";
1921	}
1922	llvm_unreachable("Unknown AssumptionKind!");
1923	}
1924
1925	bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {
1926	if (Sign == AS_ASSUMPTION) {
1927	if (Context.is_subset(set2: Set))
1928	return false;
1929
1930	if (AssumedContext.is_subset(set2: Set))
1931	return false;
1932	} else {
1933	if (Set.is_disjoint(set2: Context))
1934	return false;
1935
1936	if (Set.is_subset(set2: InvalidContext))
1937	return false;
1938	}
1939	return true;
1940	}
1941
1942	bool Scop::trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
1943	AssumptionSign Sign, BasicBlock *BB) {
1944	if (PollyRemarksMinimal && !isEffectiveAssumption(Set, Sign))
1945	return false;
1946
1947	// Do never emit trivial assumptions as they only clutter the output.
1948	if (!PollyRemarksMinimal) {
1949	isl::set Univ;
1950	if (Sign == AS_ASSUMPTION)
1951	Univ = isl::set::universe(space: Set.get_space());
1952
1953	bool IsTrivial = (Sign == AS_RESTRICTION && Set.is_empty()) ||
1954	(Sign == AS_ASSUMPTION && Univ.is_equal(set2: Set));
1955
1956	if (IsTrivial)
1957	return false;
1958	}
1959
1960	switch (Kind) {
1961	case ALIASING:
1962	AssumptionsAliasing++;
1963	break;
1964	case INBOUNDS:
1965	AssumptionsInbounds++;
1966	break;
1967	case WRAPPING:
1968	AssumptionsWrapping++;
1969	break;
1970	case UNSIGNED:
1971	AssumptionsUnsigned++;
1972	break;
1973	case COMPLEXITY:
1974	AssumptionsComplexity++;
1975	break;
1976	case PROFITABLE:
1977	AssumptionsUnprofitable++;
1978	break;
1979	case ERRORBLOCK:
1980	AssumptionsErrorBlock++;
1981	break;
1982	case INFINITELOOP:
1983	AssumptionsInfiniteLoop++;
1984	break;
1985	case INVARIANTLOAD:
1986	AssumptionsInvariantLoad++;
1987	break;
1988	case DELINEARIZATION:
1989	AssumptionsDelinearization++;
1990	break;
1991	}
1992
1993	auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t";
1994	std::string Msg = toString(Kind) + Suffix + stringFromIslObj(Obj: Set);
1995	if (BB)
1996	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc, BB)
1997	<< Msg);
1998	else
1999	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc,
2000	R.getEntry())
2001	<< Msg);
2002	return true;
2003	}
2004
2005	void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
2006	AssumptionSign Sign, BasicBlock *BB,
2007	bool RequiresRTC) {
2008	// Simplify the assumptions/restrictions first.
2009	Set = Set.gist_params(context: getContext());
2010	intersectDefinedBehavior(Set, Sign);
2011
2012	if (!RequiresRTC)
2013	return;
2014
2015	if (!trackAssumption(Kind, Set, Loc, Sign, BB))
2016	return;
2017
2018	if (Sign == AS_ASSUMPTION)
2019	AssumedContext = AssumedContext.intersect(set2: Set).coalesce();
2020	else
2021	InvalidContext = InvalidContext.unite(set2: Set).coalesce();
2022	}
2023
2024	void Scop::intersectDefinedBehavior(isl::set Set, AssumptionSign Sign) {
2025	if (DefinedBehaviorContext.is_null())
2026	return;
2027
2028	if (Sign == AS_ASSUMPTION)
2029	DefinedBehaviorContext = DefinedBehaviorContext.intersect(set2: Set);
2030	else
2031	DefinedBehaviorContext = DefinedBehaviorContext.subtract(set2: Set);
2032
2033	// Limit the complexity of the context. If complexity is exceeded, simplify
2034	// the set and check again.
2035	if (DefinedBehaviorContext.n_basic_set().release() >
2036	MaxDisjunktsInDefinedBehaviourContext) {
2037	simplify(Set&: DefinedBehaviorContext);
2038	if (DefinedBehaviorContext.n_basic_set().release() >
2039	MaxDisjunktsInDefinedBehaviourContext)
2040	DefinedBehaviorContext = {};
2041	}
2042	}
2043
2044	void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
2045	LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");
2046	addAssumption(Kind, Set: isl::set::empty(space: getParamSpace()), Loc, Sign: AS_ASSUMPTION, BB);
2047	}
2048
2049	isl::set Scop::getInvalidContext() const { return InvalidContext; }
2050
2051	void Scop::printContext(raw_ostream &OS) const {
2052	OS << "Context:\n";
2053	OS.indent(NumSpaces: 4) << Context << "\n";
2054
2055	OS.indent(NumSpaces: 4) << "Assumed Context:\n";
2056	OS.indent(NumSpaces: 4) << AssumedContext << "\n";
2057
2058	OS.indent(NumSpaces: 4) << "Invalid Context:\n";
2059	OS.indent(NumSpaces: 4) << InvalidContext << "\n";
2060
2061	OS.indent(NumSpaces: 4) << "Defined Behavior Context:\n";
2062	if (!DefinedBehaviorContext.is_null())
2063	OS.indent(NumSpaces: 4) << DefinedBehaviorContext << "\n";
2064	else
2065	OS.indent(NumSpaces: 4) << "<unavailable>\n";
2066
2067	unsigned Dim = 0;
2068	for (const SCEV *Parameter : Parameters)
2069	OS.indent(NumSpaces: 4) << "p" << Dim++ << ": " << *Parameter << "\n";
2070	}
2071
2072	void Scop::printAliasAssumptions(raw_ostream &OS) const {
2073	int noOfGroups = 0;
2074	for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
2075	if (Pair.second.size() == 0)
2076	noOfGroups += 1;
2077	else
2078	noOfGroups += Pair.second.size();
2079	}
2080
2081	OS.indent(NumSpaces: 4) << "Alias Groups (" << noOfGroups << "):\n";
2082	if (MinMaxAliasGroups.empty()) {
2083	OS.indent(NumSpaces: 8) << "n/a\n";
2084	return;
2085	}
2086
2087	for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
2088
2089	// If the group has no read only accesses print the write accesses.
2090	if (Pair.second.empty()) {
2091	OS.indent(NumSpaces: 8) << "[[";
2092	for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
2093	OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2094	<< ">";
2095	}
2096	OS << " ]]\n";
2097	}
2098
2099	for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
2100	OS.indent(NumSpaces: 8) << "[[";
2101	OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
2102	for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
2103	OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2104	<< ">";
2105	}
2106	OS << " ]]\n";
2107	}
2108	}
2109	}
2110
2111	void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {
2112	OS << "Statements {\n";
2113
2114	for (const ScopStmt &Stmt : *this) {
2115	OS.indent(NumSpaces: 4);
2116	Stmt.print(OS, PrintInstructions);
2117	}
2118
2119	OS.indent(NumSpaces: 4) << "}\n";
2120	}
2121
2122	void Scop::printArrayInfo(raw_ostream &OS) const {
2123	OS << "Arrays {\n";
2124
2125	for (auto &Array : arrays())
2126	Array->print(OS);
2127
2128	OS.indent(NumSpaces: 4) << "}\n";
2129
2130	OS.indent(NumSpaces: 4) << "Arrays (Bounds as pw_affs) {\n";
2131
2132	for (auto &Array : arrays())
2133	Array->print(OS, /* SizeAsPwAff */ true);
2134
2135	OS.indent(NumSpaces: 4) << "}\n";
2136	}
2137
2138	void Scop::print(raw_ostream &OS, bool PrintInstructions) const {
2139	OS.indent(NumSpaces: 4) << "Function: " << getFunction().getName() << "\n";
2140	OS.indent(NumSpaces: 4) << "Region: " << getNameStr() << "\n";
2141	OS.indent(NumSpaces: 4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
2142	OS.indent(NumSpaces: 4) << "Invariant Accesses: {\n";
2143	for (const auto &IAClass : InvariantEquivClasses) {
2144	const auto &MAs = IAClass.InvariantAccesses;
2145	if (MAs.empty()) {
2146	OS.indent(NumSpaces: 12) << "Class Pointer: " << *IAClass.IdentifyingPointer << "\n";
2147	} else {
2148	MAs.front()->print(OS);
2149	OS.indent(NumSpaces: 12) << "Execution Context: " << IAClass.ExecutionContext
2150	<< "\n";
2151	}
2152	}
2153	OS.indent(NumSpaces: 4) << "}\n";
2154	printContext(OS&: OS.indent(NumSpaces: 4));
2155	printArrayInfo(OS&: OS.indent(NumSpaces: 4));
2156	printAliasAssumptions(OS);
2157	printStatements(OS&: OS.indent(NumSpaces: 4), PrintInstructions);
2158	}
2159
2160	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2161	LLVM_DUMP_METHOD void Scop::dump() const { print(OS&: dbgs(), PrintInstructions: true); }
2162	#endif
2163
2164	isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }
2165
2166	__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
2167	bool NonNegative,
2168	RecordedAssumptionsTy *RecordedAssumptions) {
2169	// First try to use the SCEVAffinator to generate a piecewise defined
2170	// affine function from @p E in the context of @p BB. If that tasks becomes to
2171	// complex the affinator might return a nullptr. In such a case we invalidate
2172	// the SCoP and return a dummy value. This way we do not need to add error
2173	// handling code to all users of this function.
2174	auto PWAC = Affinator.getPwAff(E, BB, RecordedAssumptions);
2175	if (!PWAC.first.is_null()) {
2176	// TODO: We could use a heuristic and either use:
2177	// SCEVAffinator::takeNonNegativeAssumption
2178	// or
2179	// SCEVAffinator::interpretAsUnsigned
2180	// to deal with unsigned or "NonNegative" SCEVs.
2181	if (NonNegative)
2182	Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions);
2183	return PWAC;
2184	}
2185
2186	auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
2187	invalidate(Kind: COMPLEXITY, Loc: DL, BB);
2188	return Affinator.getPwAff(E: SE->getZero(Ty: E->getType()), BB, RecordedAssumptions);
2189	}
2190
2191	isl::union_set Scop::getDomains() const {
2192	isl_space *EmptySpace = isl_space_params_alloc(ctx: getIslCtx().get(), nparam: 0);
2193	isl_union_set *Domain = isl_union_set_empty(space: EmptySpace);
2194
2195	for (const ScopStmt &Stmt : *this)
2196	Domain = isl_union_set_add_set(uset: Domain, set: Stmt.getDomain().release());
2197
2198	return isl::manage(ptr: Domain);
2199	}
2200
2201	isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB,
2202	RecordedAssumptionsTy *RecordedAssumptions) {
2203	PWACtx PWAC = getPwAff(E, BB, NonNegative: RecordedAssumptions);
2204	return PWAC.first;
2205	}
2206
2207	isl::union_map
2208	Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
2209	isl::union_map Accesses = isl::union_map::empty(ctx: getIslCtx());
2210
2211	for (ScopStmt &Stmt : *this) {
2212	for (MemoryAccess *MA : Stmt) {
2213	if (!Predicate(*MA))
2214	continue;
2215
2216	isl::set Domain = Stmt.getDomain();
2217	isl::map AccessDomain = MA->getAccessRelation();
2218	AccessDomain = AccessDomain.intersect_domain(set: Domain);
2219	Accesses = Accesses.unite(umap2: AccessDomain);
2220	}
2221	}
2222
2223	return Accesses.coalesce();
2224	}
2225
2226	isl::union_map Scop::getMustWrites() {
2227	return getAccessesOfType(Predicate: [](MemoryAccess &MA) { return MA.isMustWrite(); });
2228	}
2229
2230	isl::union_map Scop::getMayWrites() {
2231	return getAccessesOfType(Predicate: [](MemoryAccess &MA) { return MA.isMayWrite(); });
2232	}
2233
2234	isl::union_map Scop::getWrites() {
2235	return getAccessesOfType(Predicate: [](MemoryAccess &MA) { return MA.isWrite(); });
2236	}
2237
2238	isl::union_map Scop::getReads() {
2239	return getAccessesOfType(Predicate: [](MemoryAccess &MA) { return MA.isRead(); });
2240	}
2241
2242	isl::union_map Scop::getAccesses() {
2243	return getAccessesOfType(Predicate: [](MemoryAccess &MA) { return true; });
2244	}
2245
2246	isl::union_map Scop::getAccesses(ScopArrayInfo *Array) {
2247	return getAccessesOfType(
2248	Predicate: [Array](MemoryAccess &MA) { return MA.getScopArrayInfo() == Array; });
2249	}
2250
2251	isl::union_map Scop::getSchedule() const {
2252	auto Tree = getScheduleTree();
2253	return Tree.get_map();
2254	}
2255
2256	isl::schedule Scop::getScheduleTree() const {
2257	return Schedule.intersect_domain(domain: getDomains());
2258	}
2259
2260	void Scop::setSchedule(isl::union_map NewSchedule) {
2261	auto S = isl::schedule::from_domain(domain: getDomains());
2262	Schedule = S.insert_partial_schedule(
2263	partial: isl::multi_union_pw_aff::from_union_map(umap: NewSchedule));
2264	ScheduleModified = true;
2265	}
2266
2267	void Scop::setScheduleTree(isl::schedule NewSchedule) {
2268	Schedule = NewSchedule;
2269	ScheduleModified = true;
2270	}
2271
2272	bool Scop::restrictDomains(isl::union_set Domain) {
2273	bool Changed = false;
2274	for (ScopStmt &Stmt : *this) {
2275	isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());
2276	isl::union_set NewStmtDomain = StmtDomain.intersect(uset2: Domain);
2277
2278	if (StmtDomain.is_subset(uset2: NewStmtDomain))
2279	continue;
2280
2281	Changed = true;
2282
2283	NewStmtDomain = NewStmtDomain.coalesce();
2284
2285	if (NewStmtDomain.is_empty())
2286	Stmt.restrictDomain(NewDomain: isl::set::empty(space: Stmt.getDomainSpace()));
2287	else
2288	Stmt.restrictDomain(NewDomain: isl::set(NewStmtDomain));
2289	}
2290	return Changed;
2291	}
2292
2293	ScalarEvolution *Scop::getSE() const { return SE; }
2294
2295	void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
2296	std::vector<Instruction *> Instructions) {
2297	assert(BB && "Unexpected nullptr!");
2298	Stmts.emplace_back(args&: *this, args&: *BB, args&: Name, args&: SurroundingLoop, args&: Instructions);
2299	auto *Stmt = &Stmts.back();
2300	StmtMap[BB].push_back(x: Stmt);
2301	for (Instruction *Inst : Instructions) {
2302	assert(!InstStmtMap.count(Inst) &&
2303	"Unexpected statement corresponding to the instruction.");
2304	InstStmtMap[Inst] = Stmt;
2305	}
2306	}
2307
2308	void Scop::addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,
2309	std::vector<Instruction *> Instructions) {
2310	assert(R && "Unexpected nullptr!");
2311	Stmts.emplace_back(args&: *this, args&: *R, args&: Name, args&: SurroundingLoop, args&: Instructions);
2312	auto *Stmt = &Stmts.back();
2313
2314	for (Instruction *Inst : Instructions) {
2315	assert(!InstStmtMap.count(Inst) &&
2316	"Unexpected statement corresponding to the instruction.");
2317	InstStmtMap[Inst] = Stmt;
2318	}
2319
2320	for (BasicBlock *BB : R->blocks()) {
2321	StmtMap[BB].push_back(x: Stmt);
2322	if (BB == R->getEntry())
2323	continue;
2324	for (Instruction &Inst : *BB) {
2325	assert(!InstStmtMap.count(&Inst) &&
2326	"Unexpected statement corresponding to the instruction.");
2327	InstStmtMap[&Inst] = Stmt;
2328	}
2329	}
2330	}
2331
2332	ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,
2333	isl::set Domain) {
2334	#ifndef NDEBUG
2335	isl::set SourceDomain = SourceRel.domain();
2336	isl::set TargetDomain = TargetRel.domain();
2337	assert(Domain.is_subset(TargetDomain) &&
2338	"Target access not defined for complete statement domain");
2339	assert(Domain.is_subset(SourceDomain) &&
2340	"Source access not defined for complete statement domain");
2341	#endif
2342	Stmts.emplace_back(args&: *this, args&: SourceRel, args&: TargetRel, args&: Domain);
2343	CopyStmtsNum++;
2344	return &(Stmts.back());
2345	}
2346
2347	ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
2348	auto StmtMapIt = StmtMap.find(Val: BB);
2349	if (StmtMapIt == StmtMap.end())
2350	return {};
2351	return StmtMapIt->second;
2352	}
2353
2354	ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {
2355	auto *PHI = cast<PHINode>(Val: U.getUser());
2356	BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
2357
2358	// If the value is a non-synthesizable from the incoming block, use the
2359	// statement that contains it as user statement.
2360	if (auto *IncomingInst = dyn_cast<Instruction>(Val: U.get())) {
2361	if (IncomingInst->getParent() == IncomingBB) {
2362	if (ScopStmt *IncomingStmt = getStmtFor(Inst: IncomingInst))
2363	return IncomingStmt;
2364	}
2365	}
2366
2367	// Otherwise, use the epilogue/last statement.
2368	return getLastStmtFor(BB: IncomingBB);
2369	}
2370
2371	ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
2372	ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
2373	if (!StmtList.empty())
2374	return StmtList.back();
2375	return nullptr;
2376	}
2377
2378	ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {
2379	if (RN->isSubRegion())
2380	return getStmtListFor(R: RN->getNodeAs<Region>());
2381	return getStmtListFor(BB: RN->getNodeAs<BasicBlock>());
2382	}
2383
2384	ArrayRef<ScopStmt *> Scop::getStmtListFor(Region *R) const {
2385	return getStmtListFor(BB: R->getEntry());
2386	}
2387
2388	int Scop::getRelativeLoopDepth(const Loop *L) const {
2389	if (!L || !R.contains(L))
2390	return -1;
2391	// outermostLoopInRegion always returns nullptr for top level regions
2392	if (R.isTopLevelRegion()) {
2393	// LoopInfo's depths start at 1, we start at 0
2394	return L->getLoopDepth() - 1;
2395	} else {
2396	Loop *OuterLoop = R.outermostLoopInRegion(L: const_cast<Loop *>(L));
2397	assert(OuterLoop);
2398	return L->getLoopDepth() - OuterLoop->getLoopDepth();
2399	}
2400	}
2401
2402	ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
2403	for (auto &SAI : arrays()) {
2404	if (SAI->getName() == BaseName)
2405	return SAI;
2406	}
2407	return nullptr;
2408	}
2409
2410	void Scop::addAccessData(MemoryAccess *Access) {
2411	const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo();
2412	assert(SAI && "can only use after access relations have been constructed");
2413
2414	if (Access->isOriginalValueKind() && Access->isRead())
2415	ValueUseAccs[SAI].push_back(Elt: Access);
2416	else if (Access->isOriginalAnyPHIKind() && Access->isWrite())
2417	PHIIncomingAccs[SAI].push_back(Elt: Access);
2418	}
2419
2420	void Scop::removeAccessData(MemoryAccess *Access) {
2421	if (Access->isOriginalValueKind() && Access->isWrite()) {
2422	ValueDefAccs.erase(Val: Access->getAccessValue());
2423	} else if (Access->isOriginalValueKind() && Access->isRead()) {
2424	auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];
2425	llvm::erase(C&: Uses, V: Access);
2426	} else if (Access->isOriginalPHIKind() && Access->isRead()) {
2427	PHINode *PHI = cast<PHINode>(Val: Access->getAccessInstruction());
2428	PHIReadAccs.erase(Val: PHI);
2429	} else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) {
2430	auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];
2431	llvm::erase(C&: Incomings, V: Access);
2432	}
2433	}
2434
2435	MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {
2436	assert(SAI->isValueKind());
2437
2438	Instruction *Val = dyn_cast<Instruction>(Val: SAI->getBasePtr());
2439	if (!Val)
2440	return nullptr;
2441
2442	return ValueDefAccs.lookup(Val);
2443	}
2444
2445	ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {
2446	assert(SAI->isValueKind());
2447	auto It = ValueUseAccs.find(Val: SAI);
2448	if (It == ValueUseAccs.end())
2449	return {};
2450	return It->second;
2451	}
2452
2453	MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {
2454	assert(SAI->isPHIKind() || SAI->isExitPHIKind());
2455
2456	if (SAI->isExitPHIKind())
2457	return nullptr;
2458
2459	PHINode *PHI = cast<PHINode>(Val: SAI->getBasePtr());
2460	return PHIReadAccs.lookup(Val: PHI);
2461	}
2462
2463	ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {
2464	assert(SAI->isPHIKind() || SAI->isExitPHIKind());
2465	auto It = PHIIncomingAccs.find(Val: SAI);
2466	if (It == PHIIncomingAccs.end())
2467	return {};
2468	return It->second;
2469	}
2470
2471	bool Scop::isEscaping(Instruction *Inst) {
2472	assert(contains(Inst) && "The concept of escaping makes only sense for "
2473	"values defined inside the SCoP");
2474
2475	for (Use &Use : Inst->uses()) {
2476	BasicBlock *UserBB = getUseBlock(U: Use);
2477	if (!contains(BB: UserBB))
2478	return true;
2479
2480	// When the SCoP region exit needs to be simplified, PHIs in the region exit
2481	// move to a new basic block such that its incoming blocks are not in the
2482	// SCoP anymore.
2483	if (hasSingleExitEdge() && isa<PHINode>(Val: Use.getUser()) &&
2484	isExit(BB: cast<PHINode>(Val: Use.getUser())->getParent()))
2485	return true;
2486	}
2487	return false;
2488	}
2489
2490	void Scop::incrementNumberOfAliasingAssumptions(unsigned step) {
2491	AssumptionsAliasing += step;
2492	}
2493
2494	Scop::ScopStatistics Scop::getStatistics() const {
2495	ScopStatistics Result;
2496	#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2497	auto LoopStat = ScopDetection::countBeneficialLoops(R: &R, SE&: *SE, LI&: *getLI(), MinProfitableTrips: 0);
2498
2499	int NumTotalLoops = LoopStat.NumLoops;
2500	Result.NumBoxedLoops = getBoxedLoops().size();
2501	Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;
2502
2503	for (const ScopStmt &Stmt : *this) {
2504	isl::set Domain = Stmt.getDomain().intersect_params(params: getContext());
2505	bool IsInLoop = Stmt.getNumIterators() >= 1;
2506	for (MemoryAccess *MA : Stmt) {
2507	if (!MA->isWrite())
2508	continue;
2509
2510	if (MA->isLatestValueKind()) {
2511	Result.NumValueWrites += 1;
2512	if (IsInLoop)
2513	Result.NumValueWritesInLoops += 1;
2514	}
2515
2516	if (MA->isLatestAnyPHIKind()) {
2517	Result.NumPHIWrites += 1;
2518	if (IsInLoop)
2519	Result.NumPHIWritesInLoops += 1;
2520	}
2521
2522	isl::set AccSet =
2523	MA->getAccessRelation().intersect_domain(set: Domain).range();
2524	if (AccSet.is_singleton()) {
2525	Result.NumSingletonWrites += 1;
2526	if (IsInLoop)
2527	Result.NumSingletonWritesInLoops += 1;
2528	}
2529	}
2530	}
2531	#endif
2532	return Result;
2533	}
2534
2535	raw_ostream &polly::operator<<(raw_ostream &OS, const Scop &scop) {
2536	scop.print(OS, PrintInstructions: PollyPrintInstructions);
2537	return OS;
2538	}
2539
2540	//===----------------------------------------------------------------------===//
2541	void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
2542	AU.addRequired<LoopInfoWrapperPass>();
2543	AU.addRequired<RegionInfoPass>();
2544	AU.addRequired<DominatorTreeWrapperPass>();
2545	AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2546	AU.addRequiredTransitive<ScopDetectionWrapperPass>();
2547	AU.addRequired<AAResultsWrapperPass>();
2548	AU.addRequired<AssumptionCacheTracker>();
2549	AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2550	AU.setPreservesAll();
2551	}
2552
2553	void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
2554	Scop::ScopStatistics ScopStats) {
2555	assert(Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops);
2556
2557	NumScops++;
2558	NumLoopsInScop += Stats.NumLoops;
2559	MaxNumLoopsInScop =
2560	std::max(a: MaxNumLoopsInScop.getValue(), b: (uint64_t)Stats.NumLoops);
2561
2562	if (Stats.MaxDepth == 0)
2563	NumScopsDepthZero++;
2564	else if (Stats.MaxDepth == 1)
2565	NumScopsDepthOne++;
2566	else if (Stats.MaxDepth == 2)
2567	NumScopsDepthTwo++;
2568	else if (Stats.MaxDepth == 3)
2569	NumScopsDepthThree++;
2570	else if (Stats.MaxDepth == 4)
2571	NumScopsDepthFour++;
2572	else if (Stats.MaxDepth == 5)
2573	NumScopsDepthFive++;
2574	else
2575	NumScopsDepthLarger++;
2576
2577	NumAffineLoops += ScopStats.NumAffineLoops;
2578	NumBoxedLoops += ScopStats.NumBoxedLoops;
2579
2580	NumValueWrites += ScopStats.NumValueWrites;
2581	NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
2582	NumPHIWrites += ScopStats.NumPHIWrites;
2583	NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
2584	NumSingletonWrites += ScopStats.NumSingletonWrites;
2585	NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
2586	}
2587
2588	bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
2589	auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2590
2591	if (!SD.isMaxRegionInScop(R: *R))
2592	return false;
2593
2594	Function *F = R->getEntry()->getParent();
2595	auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2596	auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2597	auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2598	auto const &DL = F->getParent()->getDataLayout();
2599	auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2600	auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F&: *F);
2601	auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2602
2603	ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
2604	S = SB.getScop(); // take ownership of scop object
2605
2606	#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2607	if (S) {
2608	ScopDetection::LoopStats Stats =
2609	ScopDetection::countBeneficialLoops(R: &S->getRegion(), SE, LI, MinProfitableTrips: 0);
2610	updateLoopCountStatistic(Stats, ScopStats: S->getStatistics());
2611	}
2612	#endif
2613
2614	return false;
2615	}
2616
2617	void ScopInfoRegionPass::print(raw_ostream &OS, const Module *) const {
2618	if (S)
2619	S->print(OS, PrintInstructions: PollyPrintInstructions);
2620	else
2621	OS << "Invalid Scop!\n";
2622	}
2623
2624	char ScopInfoRegionPass::ID = 0;
2625
2626	Pass *polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
2627
2628	INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",
2629	"Polly - Create polyhedral description of Scops", false,
2630	false);
2631	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
2632	INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
2633	INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
2634	INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
2635	INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
2636	INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
2637	INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
2638	INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
2639	"Polly - Create polyhedral description of Scops", false,
2640	false)
2641
2642	//===----------------------------------------------------------------------===//
2643
2644	namespace {
2645
2646	/// Print result from ScopInfoRegionPass.
2647	class ScopInfoPrinterLegacyRegionPass final : public RegionPass {
2648	public:
2649	static char ID;
2650
2651	ScopInfoPrinterLegacyRegionPass() : ScopInfoPrinterLegacyRegionPass(outs()) {}
2652
2653	explicit ScopInfoPrinterLegacyRegionPass(llvm::raw_ostream &OS)
2654	: RegionPass(ID), OS(OS) {}
2655
2656	bool runOnRegion(Region *R, RGPassManager &RGM) override {
2657	ScopInfoRegionPass &P = getAnalysis<ScopInfoRegionPass>();
2658
2659	OS << "Printing analysis '" << P.getPassName() << "' for region: '"
2660	<< R->getNameStr() << "' in function '"
2661	<< R->getEntry()->getParent()->getName() << "':\n";
2662	P.print(OS);
2663
2664	return false;
2665	}
2666
2667	void getAnalysisUsage(AnalysisUsage &AU) const override {
2668	RegionPass::getAnalysisUsage(AU);
2669	AU.addRequired<ScopInfoRegionPass>();
2670	AU.setPreservesAll();
2671	}
2672
2673	private:
2674	llvm::raw_ostream &OS;
2675	};
2676
2677	char ScopInfoPrinterLegacyRegionPass::ID = 0;
2678	} // namespace
2679
2680	Pass *polly::createScopInfoPrinterLegacyRegionPass(raw_ostream &OS) {
2681	return new ScopInfoPrinterLegacyRegionPass(OS);
2682	}
2683
2684	INITIALIZE_PASS_BEGIN(ScopInfoPrinterLegacyRegionPass, "polly-print-scops",
2685	"Polly - Print polyhedral description of Scops", false,
2686	false);
2687	INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
2688	INITIALIZE_PASS_END(ScopInfoPrinterLegacyRegionPass, "polly-print-scops",
2689	"Polly - Print polyhedral description of Scops", false,
2690	false)
2691
2692	//===----------------------------------------------------------------------===//
2693
2694	ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
2695	LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
2696	AssumptionCache &AC, OptimizationRemarkEmitter &ORE)
2697	: DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {
2698	recompute();
2699	}
2700
2701	void ScopInfo::recompute() {
2702	RegionToScopMap.clear();
2703	/// Create polyhedral description of scops for all the valid regions of a
2704	/// function.
2705	for (auto &It : SD) {
2706	Region *R = const_cast<Region *>(It);
2707	if (!SD.isMaxRegionInScop(R: *R))
2708	continue;
2709
2710	ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
2711	std::unique_ptr<Scop> S = SB.getScop();
2712	if (!S)
2713	continue;
2714	#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2715	ScopDetection::LoopStats Stats =
2716	ScopDetection::countBeneficialLoops(R: &S->getRegion(), SE, LI, MinProfitableTrips: 0);
2717	updateLoopCountStatistic(Stats, ScopStats: S->getStatistics());
2718	#endif
2719	bool Inserted = RegionToScopMap.insert(KV: {R, std::move(S)}).second;
2720	assert(Inserted && "Building Scop for the same region twice!");
2721	(void)Inserted;
2722	}
2723	}
2724
2725	bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
2726	FunctionAnalysisManager::Invalidator &Inv) {
2727	// Check whether the analysis, all analyses on functions have been preserved
2728	// or anything we're holding references to is being invalidated
2729	auto PAC = PA.getChecker<ScopInfoAnalysis>();
2730	return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2731	Inv.invalidate<ScopAnalysis>(IR&: F, PA) ||
2732	Inv.invalidate<ScalarEvolutionAnalysis>(IR&: F, PA) ||
2733	Inv.invalidate<LoopAnalysis>(IR&: F, PA) ||
2734	Inv.invalidate<AAManager>(IR&: F, PA) ||
2735	Inv.invalidate<DominatorTreeAnalysis>(IR&: F, PA) ||
2736	Inv.invalidate<AssumptionAnalysis>(IR&: F, PA);
2737	}
2738
2739	AnalysisKey ScopInfoAnalysis::Key;
2740
2741	ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
2742	FunctionAnalysisManager &FAM) {
2743	auto &SD = FAM.getResult<ScopAnalysis>(IR&: F);
2744	auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(IR&: F);
2745	auto &LI = FAM.getResult<LoopAnalysis>(IR&: F);
2746	auto &AA = FAM.getResult<AAManager>(IR&: F);
2747	auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F);
2748	auto &AC = FAM.getResult<AssumptionAnalysis>(IR&: F);
2749	auto &DL = F.getParent()->getDataLayout();
2750	auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
2751	return {DL, SD, SE, LI, AA, DT, AC, ORE};
2752	}
2753
2754	PreservedAnalyses ScopInfoPrinterPass::run(Function &F,
2755	FunctionAnalysisManager &FAM) {
2756	auto &SI = FAM.getResult<ScopInfoAnalysis>(IR&: F);
2757	// Since the legacy PM processes Scops in bottom up, we print them in reverse
2758	// order here to keep the output persistent
2759	for (auto &It : reverse(C&: SI)) {
2760	if (It.second)
2761	It.second->print(OS&: Stream, PrintInstructions: PollyPrintInstructions);
2762	else
2763	Stream << "Invalid Scop!\n";
2764	}
2765	return PreservedAnalyses::all();
2766	}
2767
2768	void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2769	AU.addRequired<LoopInfoWrapperPass>();
2770	AU.addRequired<RegionInfoPass>();
2771	AU.addRequired<DominatorTreeWrapperPass>();
2772	AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2773	AU.addRequiredTransitive<ScopDetectionWrapperPass>();
2774	AU.addRequired<AAResultsWrapperPass>();
2775	AU.addRequired<AssumptionCacheTracker>();
2776	AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2777	AU.setPreservesAll();
2778	}
2779
2780	bool ScopInfoWrapperPass::runOnFunction(Function &F) {
2781	auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2782	auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2783	auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2784	auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2785	auto const &DL = F.getParent()->getDataLayout();
2786	auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2787	auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2788	auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2789
2790	Result.reset(p: new ScopInfo{DL, SD, SE, LI, AA, DT, AC, ORE});
2791	return false;
2792	}
2793
2794	void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
2795	for (auto &It : *Result) {
2796	if (It.second)
2797	It.second->print(OS, PrintInstructions: PollyPrintInstructions);
2798	else
2799	OS << "Invalid Scop!\n";
2800	}
2801	}
2802
2803	char ScopInfoWrapperPass::ID = 0;
2804
2805	Pass *polly::createScopInfoWrapperPassPass() {
2806	return new ScopInfoWrapperPass();
2807	}
2808
2809	INITIALIZE_PASS_BEGIN(
2810	ScopInfoWrapperPass, "polly-function-scops",
2811	"Polly - Create polyhedral description of all Scops of a function", false,
2812	false);
2813	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
2814	INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
2815	INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
2816	INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
2817	INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
2818	INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
2819	INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
2820	INITIALIZE_PASS_END(
2821	ScopInfoWrapperPass, "polly-function-scops",
2822	"Polly - Create polyhedral description of all Scops of a function", false,
2823	false)
2824
2825	//===----------------------------------------------------------------------===//
2826
2827	namespace {
2828	/// Print result from ScopInfoWrapperPass.
2829	class ScopInfoPrinterLegacyFunctionPass final : public FunctionPass {
2830	public:
2831	static char ID;
2832
2833	ScopInfoPrinterLegacyFunctionPass()
2834	: ScopInfoPrinterLegacyFunctionPass(outs()) {}
2835	explicit ScopInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS)
2836	: FunctionPass(ID), OS(OS) {}
2837
2838	bool runOnFunction(Function &F) override {
2839	ScopInfoWrapperPass &P = getAnalysis<ScopInfoWrapperPass>();
2840
2841	OS << "Printing analysis '" << P.getPassName() << "' for function '"
2842	<< F.getName() << "':\n";
2843	P.print(OS);
2844
2845	return false;
2846	}
2847
2848	void getAnalysisUsage(AnalysisUsage &AU) const override {
2849	FunctionPass::getAnalysisUsage(AU);
2850	AU.addRequired<ScopInfoWrapperPass>();
2851	AU.setPreservesAll();
2852	}
2853
2854	private:
2855	llvm::raw_ostream &OS;
2856	};
2857
2858	char ScopInfoPrinterLegacyFunctionPass::ID = 0;
2859	} // namespace
2860
2861	Pass *polly::createScopInfoPrinterLegacyFunctionPass(raw_ostream &OS) {
2862	return new ScopInfoPrinterLegacyFunctionPass(OS);
2863	}
2864
2865	INITIALIZE_PASS_BEGIN(
2866	ScopInfoPrinterLegacyFunctionPass, "polly-print-function-scops",
2867	"Polly - Print polyhedral description of all Scops of a function", false,
2868	false);
2869	INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
2870	INITIALIZE_PASS_END(
2871	ScopInfoPrinterLegacyFunctionPass, "polly-print-function-scops",
2872	"Polly - Print polyhedral description of all Scops of a function", false,
2873	false)
2874