1	//===- ScopBuilder.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	//===----------------------------------------------------------------------===//
15
16	#include "polly/ScopBuilder.h"
17	#include "polly/Options.h"
18	#include "polly/ScopDetection.h"
19	#include "polly/ScopInfo.h"
20	#include "polly/Support/GICHelper.h"
21	#include "polly/Support/ISLTools.h"
22	#include "polly/Support/SCEVValidator.h"
23	#include "polly/Support/ScopHelper.h"
24	#include "polly/Support/VirtualInstruction.h"
25	#include "llvm/ADT/ArrayRef.h"
26	#include "llvm/ADT/EquivalenceClasses.h"
27	#include "llvm/ADT/PostOrderIterator.h"
28	#include "llvm/ADT/Sequence.h"
29	#include "llvm/ADT/SmallSet.h"
30	#include "llvm/ADT/Statistic.h"
31	#include "llvm/Analysis/AliasAnalysis.h"
32	#include "llvm/Analysis/AssumptionCache.h"
33	#include "llvm/Analysis/Delinearization.h"
34	#include "llvm/Analysis/Loads.h"
35	#include "llvm/Analysis/LoopInfo.h"
36	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
37	#include "llvm/Analysis/RegionInfo.h"
38	#include "llvm/Analysis/RegionIterator.h"
39	#include "llvm/Analysis/ScalarEvolution.h"
40	#include "llvm/Analysis/ScalarEvolutionExpressions.h"
41	#include "llvm/IR/BasicBlock.h"
42	#include "llvm/IR/DataLayout.h"
43	#include "llvm/IR/DebugLoc.h"
44	#include "llvm/IR/DerivedTypes.h"
45	#include "llvm/IR/Dominators.h"
46	#include "llvm/IR/Function.h"
47	#include "llvm/IR/InstrTypes.h"
48	#include "llvm/IR/Instruction.h"
49	#include "llvm/IR/Instructions.h"
50	#include "llvm/IR/Type.h"
51	#include "llvm/IR/Use.h"
52	#include "llvm/IR/Value.h"
53	#include "llvm/Support/CommandLine.h"
54	#include "llvm/Support/Compiler.h"
55	#include "llvm/Support/Debug.h"
56	#include "llvm/Support/ErrorHandling.h"
57	#include "llvm/Support/raw_ostream.h"
58	#include <cassert>
59
60	using namespace llvm;
61	using namespace polly;
62
63	#define DEBUG_TYPE "polly-scops"
64
65	STATISTIC(ScopFound, "Number of valid Scops");
66	STATISTIC(RichScopFound, "Number of Scops containing a loop");
67	STATISTIC(InfeasibleScops,
68	"Number of SCoPs with statically infeasible context.");
69
70	bool polly::ModelReadOnlyScalars;
71
72	// The maximal number of dimensions we allow during invariant load construction.
73	// More complex access ranges will result in very high compile time and are also
74	// unlikely to result in good code. This value is very high and should only
75	// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
76	static unsigned const MaxDimensionsInAccessRange = 9;
77
78	static cl::opt<bool, true> XModelReadOnlyScalars(
79	"polly-analyze-read-only-scalars",
80	cl::desc("Model read-only scalar values in the scop description"),
81	cl::location(L&: ModelReadOnlyScalars), cl::Hidden, cl::init(Val: true),
82	cl::cat(PollyCategory));
83
84	static cl::opt<int>
85	OptComputeOut("polly-analysis-computeout",
86	cl::desc("Bound the scop analysis by a maximal amount of "
87	"computational steps (0 means no bound)"),
88	cl::Hidden, cl::init(Val: 800000), cl::cat(PollyCategory));
89
90	static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
91	"polly-allow-dereference-of-all-function-parameters",
92	cl::desc(
93	"Treat all parameters to functions that are pointers as dereferencible."
94	" This is useful for invariant load hoisting, since we can generate"
95	" less runtime checks. This is only valid if all pointers to functions"
96	" are always initialized, so that Polly can choose to hoist"
97	" their loads. "),
98	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
99
100	static cl::opt<bool>
101	PollyIgnoreInbounds("polly-ignore-inbounds",
102	cl::desc("Do not take inbounds assumptions at all"),
103	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
104
105	static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
106	"polly-rtc-max-arrays-per-group",
107	cl::desc("The maximal number of arrays to compare in each alias group."),
108	cl::Hidden, cl::init(Val: 20), cl::cat(PollyCategory));
109
110	static cl::opt<unsigned> RunTimeChecksMaxAccessDisjuncts(
111	"polly-rtc-max-array-disjuncts",
112	cl::desc("The maximal number of disjunts allowed in memory accesses to "
113	"to build RTCs."),
114	cl::Hidden, cl::init(Val: 8), cl::cat(PollyCategory));
115
116	static cl::opt<unsigned> RunTimeChecksMaxParameters(
117	"polly-rtc-max-parameters",
118	cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
119	cl::init(Val: 8), cl::cat(PollyCategory));
120
121	static cl::opt<bool> UnprofitableScalarAccs(
122	"polly-unprofitable-scalar-accs",
123	cl::desc("Count statements with scalar accesses as not optimizable"),
124	cl::Hidden, cl::init(Val: false), cl::cat(PollyCategory));
125
126	static cl::opt<std::string> UserContextStr(
127	"polly-context", cl::value_desc("isl parameter set"),
128	cl::desc("Provide additional constraints on the context parameters"),
129	cl::init(Val: ""), cl::cat(PollyCategory));
130
131	static cl::opt<bool> DetectReductions("polly-detect-reductions",
132	cl::desc("Detect and exploit reductions"),
133	cl::Hidden, cl::init(Val: true),
134	cl::cat(PollyCategory));
135
136	// Multiplicative reductions can be disabled separately as these kind of
137	// operations can overflow easily. Additive reductions and bit operations
138	// are in contrast pretty stable.
139	static cl::opt<bool> DisableMultiplicativeReductions(
140	"polly-disable-multiplicative-reductions",
141	cl::desc("Disable multiplicative reductions"), cl::Hidden,
142	cl::cat(PollyCategory));
143
144	enum class GranularityChoice { BasicBlocks, ScalarIndependence, Stores };
145
146	static cl::opt<GranularityChoice> StmtGranularity(
147	"polly-stmt-granularity",
148	cl::desc(
149	"Algorithm to use for splitting basic blocks into multiple statements"),
150	cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
151	"One statement per basic block"),
152	clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep",
153	"Scalar independence heuristic"),
154	clEnumValN(GranularityChoice::Stores, "store",
155	"Store-level granularity")),
156	cl::init(Val: GranularityChoice::ScalarIndependence), cl::cat(PollyCategory));
157
158	/// Helper to treat non-affine regions and basic blocks the same.
159	///
160	///{
161
162	/// Return the block that is the representing block for @p RN.
163	static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
164	return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
165	: RN->getNodeAs<BasicBlock>();
166	}
167
168	/// Return the @p idx'th block that is executed after @p RN.
169	static inline BasicBlock *
170	getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
171	if (RN->isSubRegion()) {
172	assert(idx == 0);
173	return RN->getNodeAs<Region>()->getExit();
174	}
175	return TI->getSuccessor(Idx: idx);
176	}
177
178	static bool containsErrorBlock(RegionNode *RN, const Region &R,
179	ScopDetection *SD) {
180	if (!RN->isSubRegion())
181	return SD->isErrorBlock(BB&: *RN->getNodeAs<BasicBlock>(), R);
182	for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
183	if (SD->isErrorBlock(BB&: *BB, R))
184	return true;
185	return false;
186	}
187
188	///}
189
190	/// Create a map to map from a given iteration to a subsequent iteration.
191	///
192	/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
193	/// is incremented by one and all other dimensions are equal, e.g.,
194	/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
195	///
196	/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
197	static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
198	isl::space MapSpace = SetSpace.map_from_set();
199	isl::map NextIterationMap = isl::map::universe(space: MapSpace);
200	for (unsigned u : rangeIslSize(Begin: 0, End: NextIterationMap.domain_tuple_dim()))
201	if (u != Dim)
202	NextIterationMap =
203	NextIterationMap.equate(type1: isl::dim::in, pos1: u, type2: isl::dim::out, pos2: u);
204	isl::constraint C =
205	isl::constraint::alloc_equality(ls: isl::local_space(MapSpace));
206	C = C.set_constant_si(1);
207	C = C.set_coefficient_si(type: isl::dim::in, pos: Dim, v: 1);
208	C = C.set_coefficient_si(type: isl::dim::out, pos: Dim, v: -1);
209	NextIterationMap = NextIterationMap.add_constraint(constraint: C);
210	return NextIterationMap;
211	}
212
213	/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
214	static isl::set collectBoundedParts(isl::set S) {
215	isl::set BoundedParts = isl::set::empty(space: S.get_space());
216	for (isl::basic_set BSet : S.get_basic_set_list())
217	if (BSet.is_bounded())
218	BoundedParts = BoundedParts.unite(set2: isl::set(BSet));
219	return BoundedParts;
220	}
221
222	/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
223	///
224	/// @returns A separation of @p S into first an unbounded then a bounded subset,
225	/// both with regards to the dimension @p Dim.
226	static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
227	unsigned Dim) {
228	for (unsigned u : rangeIslSize(Begin: 0, End: S.tuple_dim()))
229	S = S.lower_bound_si(type: isl::dim::set, pos: u, value: 0);
230
231	unsigned NumDimsS = unsignedFromIslSize(Size: S.tuple_dim());
232	isl::set OnlyDimS = S;
233
234	// Remove dimensions that are greater than Dim as they are not interesting.
235	assert(NumDimsS >= Dim + 1);
236	OnlyDimS = OnlyDimS.project_out(type: isl::dim::set, first: Dim + 1, n: NumDimsS - Dim - 1);
237
238	// Create artificial parametric upper bounds for dimensions smaller than Dim
239	// as we are not interested in them.
240	OnlyDimS = OnlyDimS.insert_dims(type: isl::dim::param, pos: 0, n: Dim);
241
242	for (unsigned u = 0; u < Dim; u++) {
243	isl::constraint C = isl::constraint::alloc_inequality(
244	ls: isl::local_space(OnlyDimS.get_space()));
245	C = C.set_coefficient_si(type: isl::dim::param, pos: u, v: 1);
246	C = C.set_coefficient_si(type: isl::dim::set, pos: u, v: -1);
247	OnlyDimS = OnlyDimS.add_constraint(constraint: C);
248	}
249
250	// Collect all bounded parts of OnlyDimS.
251	isl::set BoundedParts = collectBoundedParts(S: OnlyDimS);
252
253	// Create the dimensions greater than Dim again.
254	BoundedParts =
255	BoundedParts.insert_dims(type: isl::dim::set, pos: Dim + 1, n: NumDimsS - Dim - 1);
256
257	// Remove the artificial upper bound parameters again.
258	BoundedParts = BoundedParts.remove_dims(type: isl::dim::param, first: 0, n: Dim);
259
260	isl::set UnboundedParts = S.subtract(set2: BoundedParts);
261	return std::make_pair(x&: UnboundedParts, y&: BoundedParts);
262	}
263
264	/// Create the conditions under which @p L @p Pred @p R is true.
265	static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
266	isl::pw_aff R) {
267	switch (Pred) {
268	case ICmpInst::ICMP_EQ:
269	return L.eq_set(pwaff2: R);
270	case ICmpInst::ICMP_NE:
271	return L.ne_set(pwaff2: R);
272	case ICmpInst::ICMP_SLT:
273	return L.lt_set(pwaff2: R);
274	case ICmpInst::ICMP_SLE:
275	return L.le_set(pwaff2: R);
276	case ICmpInst::ICMP_SGT:
277	return L.gt_set(pwaff2: R);
278	case ICmpInst::ICMP_SGE:
279	return L.ge_set(pwaff2: R);
280	case ICmpInst::ICMP_ULT:
281	return L.lt_set(pwaff2: R);
282	case ICmpInst::ICMP_UGT:
283	return L.gt_set(pwaff2: R);
284	case ICmpInst::ICMP_ULE:
285	return L.le_set(pwaff2: R);
286	case ICmpInst::ICMP_UGE:
287	return L.ge_set(pwaff2: R);
288	default:
289	llvm_unreachable("Non integer predicate not supported");
290	}
291	}
292
293	isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL,
294	Loop *NewL) {
295	// If the loops are the same there is nothing to do.
296	if (NewL == OldL)
297	return Dom;
298
299	int OldDepth = scop->getRelativeLoopDepth(L: OldL);
300	int NewDepth = scop->getRelativeLoopDepth(L: NewL);
301	// If both loops are non-affine loops there is nothing to do.
302	if (OldDepth == -1 && NewDepth == -1)
303	return Dom;
304
305	// Distinguish three cases:
306	// 1) The depth is the same but the loops are not.
307	// => One loop was left one was entered.
308	// 2) The depth increased from OldL to NewL.
309	// => One loop was entered, none was left.
310	// 3) The depth decreased from OldL to NewL.
311	// => Loops were left were difference of the depths defines how many.
312	if (OldDepth == NewDepth) {
313	assert(OldL->getParentLoop() == NewL->getParentLoop());
314	Dom = Dom.project_out(type: isl::dim::set, first: NewDepth, n: 1);
315	Dom = Dom.add_dims(type: isl::dim::set, n: 1);
316	} else if (OldDepth < NewDepth) {
317	assert(OldDepth + 1 == NewDepth);
318	auto &R = scop->getRegion();
319	(void)R;
320	assert(NewL->getParentLoop() == OldL ||
321	((!OldL || !R.contains(OldL)) && R.contains(NewL)));
322	Dom = Dom.add_dims(type: isl::dim::set, n: 1);
323	} else {
324	assert(OldDepth > NewDepth);
325	unsigned Diff = OldDepth - NewDepth;
326	unsigned NumDim = unsignedFromIslSize(Size: Dom.tuple_dim());
327	assert(NumDim >= Diff);
328	Dom = Dom.project_out(type: isl::dim::set, first: NumDim - Diff, n: Diff);
329	}
330
331	return Dom;
332	}
333
334	/// Compute the isl representation for the SCEV @p E in this BB.
335	///
336	/// @param BB The BB for which isl representation is to be
337	/// computed.
338	/// @param InvalidDomainMap A map of BB to their invalid domains.
339	/// @param E The SCEV that should be translated.
340	/// @param NonNegative Flag to indicate the @p E has to be non-negative.
341	///
342	/// Note that this function will also adjust the invalid context accordingly.
343
344	__isl_give isl_pw_aff *
345	ScopBuilder::getPwAff(BasicBlock *BB,
346	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
347	const SCEV *E, bool NonNegative) {
348	PWACtx PWAC = scop->getPwAff(E, BB, NonNegative, RecordedAssumptions: &RecordedAssumptions);
349	InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(set2: PWAC.second);
350	return PWAC.first.release();
351	}
352
353	/// Build condition sets for unsigned ICmpInst(s).
354	/// Special handling is required for unsigned operands to ensure that if
355	/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
356	/// it should wrap around.
357	///
358	/// @param IsStrictUpperBound holds information on the predicate relation
359	/// between TestVal and UpperBound, i.e,
360	/// TestVal < UpperBound OR TestVal <= UpperBound
361	__isl_give isl_set *ScopBuilder::buildUnsignedConditionSets(
362	BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
363	const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
364	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
365	bool IsStrictUpperBound) {
366	// Do not take NonNeg assumption on TestVal
367	// as it might have MSB (Sign bit) set.
368	isl_pw_aff *TestVal = getPwAff(BB, InvalidDomainMap, E: SCEV_TestVal, NonNegative: false);
369	// Take NonNeg assumption on UpperBound.
370	isl_pw_aff *UpperBound =
371	getPwAff(BB, InvalidDomainMap, E: SCEV_UpperBound, NonNegative: true);
372
373	// 0 <= TestVal
374	isl_set *First =
375	isl_pw_aff_le_set(pwaff1: isl_pw_aff_zero_on_domain(ls: isl_local_space_from_space(
376	space: isl_pw_aff_get_domain_space(pwaff: TestVal))),
377	pwaff2: isl_pw_aff_copy(pwaff: TestVal));
378
379	isl_set *Second;
380	if (IsStrictUpperBound)
381	// TestVal < UpperBound
382	Second = isl_pw_aff_lt_set(pwaff1: TestVal, pwaff2: UpperBound);
383	else
384	// TestVal <= UpperBound
385	Second = isl_pw_aff_le_set(pwaff1: TestVal, pwaff2: UpperBound);
386
387	isl_set *ConsequenceCondSet = isl_set_intersect(set1: First, set2: Second);
388	return ConsequenceCondSet;
389	}
390
391	bool ScopBuilder::buildConditionSets(
392	BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
393	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
394	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
395	Value *Condition = getConditionFromTerminator(TI: SI);
396	assert(Condition && "No condition for switch");
397
398	isl_pw_aff *LHS, *RHS;
399	LHS = getPwAff(BB, InvalidDomainMap, E: SE.getSCEVAtScope(V: Condition, L));
400
401	unsigned NumSuccessors = SI->getNumSuccessors();
402	ConditionSets.resize(N: NumSuccessors);
403	for (auto &Case : SI->cases()) {
404	unsigned Idx = Case.getSuccessorIndex();
405	ConstantInt *CaseValue = Case.getCaseValue();
406
407	RHS = getPwAff(BB, InvalidDomainMap, E: SE.getSCEV(V: CaseValue));
408	isl_set *CaseConditionSet =
409	buildConditionSet(Pred: ICmpInst::ICMP_EQ, L: isl::manage_copy(ptr: LHS),
410	R: isl::manage(ptr: RHS))
411	.release();
412	ConditionSets[Idx] = isl_set_coalesce(
413	set: isl_set_intersect(set1: CaseConditionSet, set2: isl_set_copy(set: Domain)));
414	}
415
416	assert(ConditionSets[0] == nullptr && "Default condition set was set");
417	isl_set *ConditionSetUnion = isl_set_copy(set: ConditionSets[1]);
418	for (unsigned u = 2; u < NumSuccessors; u++)
419	ConditionSetUnion =
420	isl_set_union(set1: ConditionSetUnion, set2: isl_set_copy(set: ConditionSets[u]));
421	ConditionSets[0] = isl_set_subtract(set1: isl_set_copy(set: Domain), set2: ConditionSetUnion);
422
423	isl_pw_aff_free(pwaff: LHS);
424
425	return true;
426	}
427
428	bool ScopBuilder::buildConditionSets(
429	BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
430	__isl_keep isl_set *Domain,
431	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
432	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
433	isl_set *ConsequenceCondSet = nullptr;
434
435	if (auto Load = dyn_cast<LoadInst>(Val: Condition)) {
436	const SCEV *LHSSCEV = SE.getSCEVAtScope(V: Load, L);
437	const SCEV *RHSSCEV = SE.getZero(Ty: LHSSCEV->getType());
438	bool NonNeg = false;
439	isl_pw_aff *LHS = getPwAff(BB, InvalidDomainMap, E: LHSSCEV, NonNegative: NonNeg);
440	isl_pw_aff *RHS = getPwAff(BB, InvalidDomainMap, E: RHSSCEV, NonNegative: NonNeg);
441	ConsequenceCondSet = buildConditionSet(Pred: ICmpInst::ICMP_SLE, L: isl::manage(ptr: LHS),
442	R: isl::manage(ptr: RHS))
443	.release();
444	} else if (auto *PHI = dyn_cast<PHINode>(Val: Condition)) {
445	auto *Unique = dyn_cast<ConstantInt>(
446	Val: getUniqueNonErrorValue(PHI, R: &scop->getRegion(), SD: &SD));
447	assert(Unique &&
448	"A PHINode condition should only be accepted by ScopDetection if "
449	"getUniqueNonErrorValue returns non-NULL");
450
451	if (Unique->isZero())
452	ConsequenceCondSet = isl_set_empty(space: isl_set_get_space(set: Domain));
453	else
454	ConsequenceCondSet = isl_set_universe(space: isl_set_get_space(set: Domain));
455	} else if (auto *CCond = dyn_cast<ConstantInt>(Val: Condition)) {
456	if (CCond->isZero())
457	ConsequenceCondSet = isl_set_empty(space: isl_set_get_space(set: Domain));
458	else
459	ConsequenceCondSet = isl_set_universe(space: isl_set_get_space(set: Domain));
460	} else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val: Condition)) {
461	auto Opcode = BinOp->getOpcode();
462	assert(Opcode == Instruction::And || Opcode == Instruction::Or);
463
464	bool Valid = buildConditionSets(BB, Condition: BinOp->getOperand(i_nocapture: 0), TI, L, Domain,
465	InvalidDomainMap, ConditionSets) &&
466	buildConditionSets(BB, Condition: BinOp->getOperand(i_nocapture: 1), TI, L, Domain,
467	InvalidDomainMap, ConditionSets);
468	if (!Valid) {
469	while (!ConditionSets.empty())
470	isl_set_free(set: ConditionSets.pop_back_val());
471	return false;
472	}
473
474	isl_set_free(set: ConditionSets.pop_back_val());
475	isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
476	isl_set_free(set: ConditionSets.pop_back_val());
477	isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
478
479	if (Opcode == Instruction::And)
480	ConsequenceCondSet = isl_set_intersect(set1: ConsCondPart0, set2: ConsCondPart1);
481	else
482	ConsequenceCondSet = isl_set_union(set1: ConsCondPart0, set2: ConsCondPart1);
483	} else {
484	auto *ICond = dyn_cast<ICmpInst>(Val: Condition);
485	assert(ICond &&
486	"Condition of exiting branch was neither constant nor ICmp!");
487
488	Region &R = scop->getRegion();
489
490	isl_pw_aff *LHS, *RHS;
491	// For unsigned comparisons we assumed the signed bit of neither operand
492	// to be set. The comparison is equal to a signed comparison under this
493	// assumption.
494	bool NonNeg = ICond->isUnsigned();
495	const SCEV *LeftOperand = SE.getSCEVAtScope(V: ICond->getOperand(i_nocapture: 0), L),
496	*RightOperand = SE.getSCEVAtScope(V: ICond->getOperand(i_nocapture: 1), L);
497
498	LeftOperand = tryForwardThroughPHI(Expr: LeftOperand, R, SE, SD: &SD);
499	RightOperand = tryForwardThroughPHI(Expr: RightOperand, R, SE, SD: &SD);
500
501	switch (ICond->getPredicate()) {
502	case ICmpInst::ICMP_ULT:
503	ConsequenceCondSet =
504	buildUnsignedConditionSets(BB, Condition, Domain, SCEV_TestVal: LeftOperand,
505	SCEV_UpperBound: RightOperand, InvalidDomainMap, IsStrictUpperBound: true);
506	break;
507	case ICmpInst::ICMP_ULE:
508	ConsequenceCondSet =
509	buildUnsignedConditionSets(BB, Condition, Domain, SCEV_TestVal: LeftOperand,
510	SCEV_UpperBound: RightOperand, InvalidDomainMap, IsStrictUpperBound: false);
511	break;
512	case ICmpInst::ICMP_UGT:
513	ConsequenceCondSet =
514	buildUnsignedConditionSets(BB, Condition, Domain, SCEV_TestVal: RightOperand,
515	SCEV_UpperBound: LeftOperand, InvalidDomainMap, IsStrictUpperBound: true);
516	break;
517	case ICmpInst::ICMP_UGE:
518	ConsequenceCondSet =
519	buildUnsignedConditionSets(BB, Condition, Domain, SCEV_TestVal: RightOperand,
520	SCEV_UpperBound: LeftOperand, InvalidDomainMap, IsStrictUpperBound: false);
521	break;
522	default:
523	LHS = getPwAff(BB, InvalidDomainMap, E: LeftOperand, NonNegative: NonNeg);
524	RHS = getPwAff(BB, InvalidDomainMap, E: RightOperand, NonNegative: NonNeg);
525	ConsequenceCondSet = buildConditionSet(Pred: ICond->getPredicate(),
526	L: isl::manage(ptr: LHS), R: isl::manage(ptr: RHS))
527	.release();
528	break;
529	}
530	}
531
532	// If no terminator was given we are only looking for parameter constraints
533	// under which @p Condition is true/false.
534	if (!TI)
535	ConsequenceCondSet = isl_set_params(set: ConsequenceCondSet);
536	assert(ConsequenceCondSet);
537	ConsequenceCondSet = isl_set_coalesce(
538	set: isl_set_intersect(set1: ConsequenceCondSet, set2: isl_set_copy(set: Domain)));
539
540	isl_set *AlternativeCondSet = nullptr;
541	bool TooComplex =
542	isl_set_n_basic_set(set: ConsequenceCondSet) >= (int)MaxDisjunctsInDomain;
543
544	if (!TooComplex) {
545	AlternativeCondSet = isl_set_subtract(set1: isl_set_copy(set: Domain),
546	set2: isl_set_copy(set: ConsequenceCondSet));
547	TooComplex =
548	isl_set_n_basic_set(set: AlternativeCondSet) >= (int)MaxDisjunctsInDomain;
549	}
550
551	if (TooComplex) {
552	scop->invalidate(Kind: COMPLEXITY, Loc: TI ? TI->getDebugLoc() : DebugLoc(),
553	BB: TI ? TI->getParent() : nullptr /* BasicBlock */);
554	isl_set_free(set: AlternativeCondSet);
555	isl_set_free(set: ConsequenceCondSet);
556	return false;
557	}
558
559	ConditionSets.push_back(Elt: ConsequenceCondSet);
560	ConditionSets.push_back(Elt: isl_set_coalesce(set: AlternativeCondSet));
561
562	return true;
563	}
564
565	bool ScopBuilder::buildConditionSets(
566	BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
567	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
568	SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
569	if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI))
570	return buildConditionSets(BB, SI, L, Domain, InvalidDomainMap,
571	ConditionSets);
572
573	assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
574
575	if (TI->getNumSuccessors() == 1) {
576	ConditionSets.push_back(Elt: isl_set_copy(set: Domain));
577	return true;
578	}
579
580	Value *Condition = getConditionFromTerminator(TI);
581	assert(Condition && "No condition for Terminator");
582
583	return buildConditionSets(BB, Condition, TI, L, Domain, InvalidDomainMap,
584	ConditionSets);
585	}
586
587	bool ScopBuilder::propagateDomainConstraints(
588	Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
589	// Iterate over the region R and propagate the domain constrains from the
590	// predecessors to the current node. In contrast to the
591	// buildDomainsWithBranchConstraints function, this one will pull the domain
592	// information from the predecessors instead of pushing it to the successors.
593	// Additionally, we assume the domains to be already present in the domain
594	// map here. However, we iterate again in reverse post order so we know all
595	// predecessors have been visited before a block or non-affine subregion is
596	// visited.
597
598	ReversePostOrderTraversal<Region *> RTraversal(R);
599	for (auto *RN : RTraversal) {
600	// Recurse for affine subregions but go on for basic blocks and non-affine
601	// subregions.
602	if (RN->isSubRegion()) {
603	Region *SubRegion = RN->getNodeAs<Region>();
604	if (!scop->isNonAffineSubRegion(R: SubRegion)) {
605	if (!propagateDomainConstraints(R: SubRegion, InvalidDomainMap))
606	return false;
607	continue;
608	}
609	}
610
611	BasicBlock *BB = getRegionNodeBasicBlock(RN);
612	isl::set &Domain = scop->getOrInitEmptyDomain(BB);
613	assert(!Domain.is_null());
614
615	// Under the union of all predecessor conditions we can reach this block.
616	isl::set PredDom = getPredecessorDomainConstraints(BB, Domain);
617	Domain = Domain.intersect(set2: PredDom).coalesce();
618	Domain = Domain.align_params(model: scop->getParamSpace());
619
620	Loop *BBLoop = getRegionNodeLoop(RN, LI);
621	if (BBLoop && BBLoop->getHeader() == BB && scop->contains(L: BBLoop))
622	if (!addLoopBoundsToHeaderDomain(L: BBLoop, InvalidDomainMap))
623	return false;
624	}
625
626	return true;
627	}
628
629	void ScopBuilder::propagateDomainConstraintsToRegionExit(
630	BasicBlock *BB, Loop *BBLoop,
631	SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,
632	DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
633	// Check if the block @p BB is the entry of a region. If so we propagate it's
634	// domain to the exit block of the region. Otherwise we are done.
635	auto *RI = scop->getRegion().getRegionInfo();
636	auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
637	auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
638	if (!BBReg || BBReg->getEntry() != BB || !scop->contains(BB: ExitBB))
639	return;
640
641	// Do not propagate the domain if there is a loop backedge inside the region
642	// that would prevent the exit block from being executed.
643	auto *L = BBLoop;
644	while (L && scop->contains(L)) {
645	SmallVector<BasicBlock *, 4> LatchBBs;
646	BBLoop->getLoopLatches(LoopLatches&: LatchBBs);
647	for (auto *LatchBB : LatchBBs)
648	if (BB != LatchBB && BBReg->contains(BB: LatchBB))
649	return;
650	L = L->getParentLoop();
651	}
652
653	isl::set Domain = scop->getOrInitEmptyDomain(BB);
654	assert(!Domain.is_null() && "Cannot propagate a nullptr");
655
656	Loop *ExitBBLoop = getFirstNonBoxedLoopFor(BB: ExitBB, LI, BoxedLoops: scop->getBoxedLoops());
657
658	// Since the dimensions of @p BB and @p ExitBB might be different we have to
659	// adjust the domain before we can propagate it.
660	isl::set AdjustedDomain = adjustDomainDimensions(Dom: Domain, OldL: BBLoop, NewL: ExitBBLoop);
661	isl::set &ExitDomain = scop->getOrInitEmptyDomain(BB: ExitBB);
662
663	// If the exit domain is not yet created we set it otherwise we "add" the
664	// current domain.
665	ExitDomain =
666	!ExitDomain.is_null() ? AdjustedDomain.unite(set2: ExitDomain) : AdjustedDomain;
667
668	// Initialize the invalid domain.
669	InvalidDomainMap[ExitBB] = ExitDomain.empty(space: ExitDomain.get_space());
670
671	FinishedExitBlocks.insert(Ptr: ExitBB);
672	}
673
674	isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB,
675	isl::set Domain) {
676	// If @p BB is the ScopEntry we are done
677	if (scop->getRegion().getEntry() == BB)
678	return isl::set::universe(space: Domain.get_space());
679
680	// The region info of this function.
681	auto &RI = *scop->getRegion().getRegionInfo();
682
683	Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, BoxedLoops: scop->getBoxedLoops());
684
685	// A domain to collect all predecessor domains, thus all conditions under
686	// which the block is executed. To this end we start with the empty domain.
687	isl::set PredDom = isl::set::empty(space: Domain.get_space());
688
689	// Set of regions of which the entry block domain has been propagated to BB.
690	// all predecessors inside any of the regions can be skipped.
691	SmallSet<Region *, 8> PropagatedRegions;
692
693	for (auto *PredBB : predecessors(BB)) {
694	// Skip backedges.
695	if (DT.dominates(A: BB, B: PredBB))
696	continue;
697
698	// If the predecessor is in a region we used for propagation we can skip it.
699	auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(BB: PredBB); };
700	if (llvm::any_of(Range&: PropagatedRegions, P: PredBBInRegion)) {
701	continue;
702	}
703
704	// Check if there is a valid region we can use for propagation, thus look
705	// for a region that contains the predecessor and has @p BB as exit block.
706	// FIXME: This was an side-effect-free (and possibly infinite) loop when
707	// committed and seems not to be needed.
708	auto *PredR = RI.getRegionFor(BB: PredBB);
709	while (PredR->getExit() != BB && !PredR->contains(BB))
710	PredR = PredR->getParent();
711
712	// If a valid region for propagation was found use the entry of that region
713	// for propagation, otherwise the PredBB directly.
714	if (PredR->getExit() == BB) {
715	PredBB = PredR->getEntry();
716	PropagatedRegions.insert(Ptr: PredR);
717	}
718
719	isl::set PredBBDom = scop->getDomainConditions(BB: PredBB);
720	Loop *PredBBLoop =
721	getFirstNonBoxedLoopFor(BB: PredBB, LI, BoxedLoops: scop->getBoxedLoops());
722	PredBBDom = adjustDomainDimensions(Dom: PredBBDom, OldL: PredBBLoop, NewL: BBLoop);
723	PredDom = PredDom.unite(set2: PredBBDom);
724	}
725
726	return PredDom;
727	}
728
729	bool ScopBuilder::addLoopBoundsToHeaderDomain(
730	Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
731	int LoopDepth = scop->getRelativeLoopDepth(L);
732	assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
733
734	BasicBlock *HeaderBB = L->getHeader();
735	assert(scop->isDomainDefined(HeaderBB));
736	isl::set &HeaderBBDom = scop->getOrInitEmptyDomain(BB: HeaderBB);
737
738	isl::map NextIterationMap =
739	createNextIterationMap(SetSpace: HeaderBBDom.get_space(), Dim: LoopDepth);
740
741	isl::set UnionBackedgeCondition = HeaderBBDom.empty(space: HeaderBBDom.get_space());
742
743	SmallVector<BasicBlock *, 4> LatchBlocks;
744	L->getLoopLatches(LoopLatches&: LatchBlocks);
745
746	for (BasicBlock *LatchBB : LatchBlocks) {
747	// If the latch is only reachable via error statements we skip it.
748	if (!scop->isDomainDefined(BB: LatchBB))
749	continue;
750
751	isl::set LatchBBDom = scop->getDomainConditions(BB: LatchBB);
752
753	isl::set BackedgeCondition;
754
755	Instruction *TI = LatchBB->getTerminator();
756	BranchInst *BI = dyn_cast<BranchInst>(Val: TI);
757	assert(BI && "Only branch instructions allowed in loop latches");
758
759	if (BI->isUnconditional())
760	BackedgeCondition = LatchBBDom;
761	else {
762	SmallVector<isl_set *, 8> ConditionSets;
763	int idx = BI->getSuccessor(i: 0) != HeaderBB;
764	if (!buildConditionSets(BB: LatchBB, TI, L, Domain: LatchBBDom.get(),
765	InvalidDomainMap, ConditionSets))
766	return false;
767
768	// Free the non back edge condition set as we do not need it.
769	isl_set_free(set: ConditionSets[1 - idx]);
770
771	BackedgeCondition = isl::manage(ptr: ConditionSets[idx]);
772	}
773
774	int LatchLoopDepth = scop->getRelativeLoopDepth(L: LI.getLoopFor(BB: LatchBB));
775	assert(LatchLoopDepth >= LoopDepth);
776	BackedgeCondition = BackedgeCondition.project_out(
777	type: isl::dim::set, first: LoopDepth + 1, n: LatchLoopDepth - LoopDepth);
778	UnionBackedgeCondition = UnionBackedgeCondition.unite(set2: BackedgeCondition);
779	}
780
781	isl::map ForwardMap = ForwardMap.lex_le(set_space: HeaderBBDom.get_space());
782	for (int i = 0; i < LoopDepth; i++)
783	ForwardMap = ForwardMap.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
784
785	isl::set UnionBackedgeConditionComplement =
786	UnionBackedgeCondition.complement();
787	UnionBackedgeConditionComplement =
788	UnionBackedgeConditionComplement.lower_bound_si(type: isl::dim::set, pos: LoopDepth,
789	value: 0);
790	UnionBackedgeConditionComplement =
791	UnionBackedgeConditionComplement.apply(map: ForwardMap);
792	HeaderBBDom = HeaderBBDom.subtract(set2: UnionBackedgeConditionComplement);
793	HeaderBBDom = HeaderBBDom.apply(map: NextIterationMap);
794
795	auto Parts = partitionSetParts(S: HeaderBBDom, Dim: LoopDepth);
796	HeaderBBDom = Parts.second;
797
798	// Check if there is a <nsw> tagged AddRec for this loop and if so do not
799	// require a runtime check. The assumption is already implied by the <nsw>
800	// tag.
801	bool RequiresRTC = !scop->hasNSWAddRecForLoop(L);
802
803	isl::set UnboundedCtx = Parts.first.params();
804	recordAssumption(RecordedAssumptions: &RecordedAssumptions, Kind: INFINITELOOP, Set: UnboundedCtx,
805	Loc: HeaderBB->getTerminator()->getDebugLoc(), Sign: AS_RESTRICTION,
806	BB: nullptr, RTC: RequiresRTC);
807	return true;
808	}
809
810	void ScopBuilder::buildInvariantEquivalenceClasses() {
811	DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
812
813	const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
814	for (LoadInst *LInst : RIL) {
815	const SCEV *PointerSCEV = SE.getSCEV(V: LInst->getPointerOperand());
816
817	Type *Ty = LInst->getType();
818	LoadInst *&ClassRep = EquivClasses[std::make_pair(x&: PointerSCEV, y&: Ty)];
819	if (ClassRep) {
820	scop->addInvariantLoadMapping(LoadInst: LInst, ClassRep);
821	continue;
822	}
823
824	ClassRep = LInst;
825	scop->addInvariantEquivClass(
826	InvariantEquivClass: InvariantEquivClassTy{.IdentifyingPointer: PointerSCEV, .InvariantAccesses: MemoryAccessList(), .ExecutionContext: {}, .AccessType: Ty});
827	}
828	}
829
830	bool ScopBuilder::buildDomains(
831	Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
832	bool IsOnlyNonAffineRegion = scop->isNonAffineSubRegion(R);
833	auto *EntryBB = R->getEntry();
834	auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(BB: EntryBB);
835	int LD = scop->getRelativeLoopDepth(L);
836	auto *S =
837	isl_set_universe(space: isl_space_set_alloc(ctx: scop->getIslCtx().get(), nparam: 0, dim: LD + 1));
838
839	InvalidDomainMap[EntryBB] = isl::manage(ptr: isl_set_empty(space: isl_set_get_space(set: S)));
840	isl::set Domain = isl::manage(ptr: S);
841	scop->setDomain(BB: EntryBB, Domain);
842
843	if (IsOnlyNonAffineRegion)
844	return !containsErrorBlock(RN: R->getNode(), R: *R, SD: &SD);
845
846	if (!buildDomainsWithBranchConstraints(R, InvalidDomainMap))
847	return false;
848
849	if (!propagateDomainConstraints(R, InvalidDomainMap))
850	return false;
851
852	// Error blocks and blocks dominated by them have been assumed to never be
853	// executed. Representing them in the Scop does not add any value. In fact,
854	// it is likely to cause issues during construction of the ScopStmts. The
855	// contents of error blocks have not been verified to be expressible and
856	// will cause problems when building up a ScopStmt for them.
857	// Furthermore, basic blocks dominated by error blocks may reference
858	// instructions in the error block which, if the error block is not modeled,
859	// can themselves not be constructed properly. To this end we will replace
860	// the domains of error blocks and those only reachable via error blocks
861	// with an empty set. Additionally, we will record for each block under which
862	// parameter combination it would be reached via an error block in its
863	// InvalidDomain. This information is needed during load hoisting.
864	if (!propagateInvalidStmtDomains(R, InvalidDomainMap))
865	return false;
866
867	return true;
868	}
869
870	bool ScopBuilder::buildDomainsWithBranchConstraints(
871	Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
872	// To create the domain for each block in R we iterate over all blocks and
873	// subregions in R and propagate the conditions under which the current region
874	// element is executed. To this end we iterate in reverse post order over R as
875	// it ensures that we first visit all predecessors of a region node (either a
876	// basic block or a subregion) before we visit the region node itself.
877	// Initially, only the domain for the SCoP region entry block is set and from
878	// there we propagate the current domain to all successors, however we add the
879	// condition that the successor is actually executed next.
880	// As we are only interested in non-loop carried constraints here we can
881	// simply skip loop back edges.
882
883	SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
884	ReversePostOrderTraversal<Region *> RTraversal(R);
885	for (auto *RN : RTraversal) {
886	// Recurse for affine subregions but go on for basic blocks and non-affine
887	// subregions.
888	if (RN->isSubRegion()) {
889	Region *SubRegion = RN->getNodeAs<Region>();
890	if (!scop->isNonAffineSubRegion(R: SubRegion)) {
891	if (!buildDomainsWithBranchConstraints(R: SubRegion, InvalidDomainMap))
892	return false;
893	continue;
894	}
895	}
896
897	if (containsErrorBlock(RN, R: scop->getRegion(), SD: &SD))
898	scop->notifyErrorBlock();
899	;
900
901	BasicBlock *BB = getRegionNodeBasicBlock(RN);
902	Instruction *TI = BB->getTerminator();
903
904	if (isa<UnreachableInst>(Val: TI))
905	continue;
906
907	if (!scop->isDomainDefined(BB))
908	continue;
909	isl::set Domain = scop->getDomainConditions(BB);
910
911	scop->updateMaxLoopDepth(Depth: unsignedFromIslSize(Size: Domain.tuple_dim()));
912
913	auto *BBLoop = getRegionNodeLoop(RN, LI);
914	// Propagate the domain from BB directly to blocks that have a superset
915	// domain, at the moment only region exit nodes of regions that start in BB.
916	propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks,
917	InvalidDomainMap);
918
919	// If all successors of BB have been set a domain through the propagation
920	// above we do not need to build condition sets but can just skip this
921	// block. However, it is important to note that this is a local property
922	// with regards to the region @p R. To this end FinishedExitBlocks is a
923	// local variable.
924	auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
925	return FinishedExitBlocks.count(Ptr: SuccBB);
926	};
927	if (std::all_of(first: succ_begin(BB), last: succ_end(BB), pred: IsFinishedRegionExit))
928	continue;
929
930	// Build the condition sets for the successor nodes of the current region
931	// node. If it is a non-affine subregion we will always execute the single
932	// exit node, hence the single entry node domain is the condition set. For
933	// basic blocks we use the helper function buildConditionSets.
934	SmallVector<isl_set *, 8> ConditionSets;
935	if (RN->isSubRegion())
936	ConditionSets.push_back(Elt: Domain.copy());
937	else if (!buildConditionSets(BB, TI, L: BBLoop, Domain: Domain.get(), InvalidDomainMap,
938	ConditionSets))
939	return false;
940
941	// Now iterate over the successors and set their initial domain based on
942	// their condition set. We skip back edges here and have to be careful when
943	// we leave a loop not to keep constraints over a dimension that doesn't
944	// exist anymore.
945	assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
946	for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
947	isl::set CondSet = isl::manage(ptr: ConditionSets[u]);
948	BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, idx: u);
949
950	// Skip blocks outside the region.
951	if (!scop->contains(BB: SuccBB))
952	continue;
953
954	// If we propagate the domain of some block to "SuccBB" we do not have to
955	// adjust the domain.
956	if (FinishedExitBlocks.count(Ptr: SuccBB))
957	continue;
958
959	// Skip back edges.
960	if (DT.dominates(A: SuccBB, B: BB))
961	continue;
962
963	Loop *SuccBBLoop =
964	getFirstNonBoxedLoopFor(BB: SuccBB, LI, BoxedLoops: scop->getBoxedLoops());
965
966	CondSet = adjustDomainDimensions(Dom: CondSet, OldL: BBLoop, NewL: SuccBBLoop);
967
968	// Set the domain for the successor or merge it with an existing domain in
969	// case there are multiple paths (without loop back edges) to the
970	// successor block.
971	isl::set &SuccDomain = scop->getOrInitEmptyDomain(BB: SuccBB);
972
973	if (!SuccDomain.is_null()) {
974	SuccDomain = SuccDomain.unite(set2: CondSet).coalesce();
975	} else {
976	// Initialize the invalid domain.
977	InvalidDomainMap[SuccBB] = CondSet.empty(space: CondSet.get_space());
978	SuccDomain = CondSet;
979	}
980
981	SuccDomain = SuccDomain.detect_equalities();
982
983	// Check if the maximal number of domain disjunctions was reached.
984	// In case this happens we will clean up and bail.
985	if (unsignedFromIslSize(Size: SuccDomain.n_basic_set()) < MaxDisjunctsInDomain)
986	continue;
987
988	scop->invalidate(Kind: COMPLEXITY, Loc: DebugLoc());
989	while (++u < ConditionSets.size())
990	isl_set_free(set: ConditionSets[u]);
991	return false;
992	}
993	}
994
995	return true;
996	}
997
998	bool ScopBuilder::propagateInvalidStmtDomains(
999	Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1000	ReversePostOrderTraversal<Region *> RTraversal(R);
1001	for (auto *RN : RTraversal) {
1002
1003	// Recurse for affine subregions but go on for basic blocks and non-affine
1004	// subregions.
1005	if (RN->isSubRegion()) {
1006	Region *SubRegion = RN->getNodeAs<Region>();
1007	if (!scop->isNonAffineSubRegion(R: SubRegion)) {
1008	propagateInvalidStmtDomains(R: SubRegion, InvalidDomainMap);
1009	continue;
1010	}
1011	}
1012
1013	bool ContainsErrorBlock = containsErrorBlock(RN, R: scop->getRegion(), SD: &SD);
1014	BasicBlock *BB = getRegionNodeBasicBlock(RN);
1015	isl::set &Domain = scop->getOrInitEmptyDomain(BB);
1016	assert(!Domain.is_null() && "Cannot propagate a nullptr");
1017
1018	isl::set InvalidDomain = InvalidDomainMap[BB];
1019
1020	bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(set2: InvalidDomain);
1021
1022	if (!IsInvalidBlock) {
1023	InvalidDomain = InvalidDomain.intersect(set2: Domain);
1024	} else {
1025	InvalidDomain = Domain;
1026	isl::set DomPar = Domain.params();
1027	recordAssumption(RecordedAssumptions: &RecordedAssumptions, Kind: ERRORBLOCK, Set: DomPar,
1028	Loc: BB->getTerminator()->getDebugLoc(), Sign: AS_RESTRICTION);
1029	Domain = isl::set::empty(space: Domain.get_space());
1030	}
1031
1032	if (InvalidDomain.is_empty()) {
1033	InvalidDomainMap[BB] = InvalidDomain;
1034	continue;
1035	}
1036
1037	auto *BBLoop = getRegionNodeLoop(RN, LI);
1038	auto *TI = BB->getTerminator();
1039	unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
1040	for (unsigned u = 0; u < NumSuccs; u++) {
1041	auto *SuccBB = getRegionNodeSuccessor(RN, TI, idx: u);
1042
1043	// Skip successors outside the SCoP.
1044	if (!scop->contains(BB: SuccBB))
1045	continue;
1046
1047	// Skip backedges.
1048	if (DT.dominates(A: SuccBB, B: BB))
1049	continue;
1050
1051	Loop *SuccBBLoop =
1052	getFirstNonBoxedLoopFor(BB: SuccBB, LI, BoxedLoops: scop->getBoxedLoops());
1053
1054	auto AdjustedInvalidDomain =
1055	adjustDomainDimensions(Dom: InvalidDomain, OldL: BBLoop, NewL: SuccBBLoop);
1056
1057	isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
1058	SuccInvalidDomain = SuccInvalidDomain.unite(set2: AdjustedInvalidDomain);
1059	SuccInvalidDomain = SuccInvalidDomain.coalesce();
1060
1061	InvalidDomainMap[SuccBB] = SuccInvalidDomain;
1062
1063	// Check if the maximal number of domain disjunctions was reached.
1064	// In case this happens we will bail.
1065	if (unsignedFromIslSize(Size: SuccInvalidDomain.n_basic_set()) <
1066	MaxDisjunctsInDomain)
1067	continue;
1068
1069	InvalidDomainMap.erase(Val: BB);
1070	scop->invalidate(Kind: COMPLEXITY, Loc: TI->getDebugLoc(), BB: TI->getParent());
1071	return false;
1072	}
1073
1074	InvalidDomainMap[BB] = InvalidDomain;
1075	}
1076
1077	return true;
1078	}
1079
1080	void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
1081	Region *NonAffineSubRegion,
1082	bool IsExitBlock) {
1083	// PHI nodes that are in the exit block of the region, hence if IsExitBlock is
1084	// true, are not modeled as ordinary PHI nodes as they are not part of the
1085	// region. However, we model the operands in the predecessor blocks that are
1086	// part of the region as regular scalar accesses.
1087
1088	// If we can synthesize a PHI we can skip it, however only if it is in
1089	// the region. If it is not it can only be in the exit block of the region.
1090	// In this case we model the operands but not the PHI itself.
1091	auto *Scope = LI.getLoopFor(BB: PHI->getParent());
1092	if (!IsExitBlock && canSynthesize(V: PHI, S: *scop, SE: &SE, Scope))
1093	return;
1094
1095	// PHI nodes are modeled as if they had been demoted prior to the SCoP
1096	// detection. Hence, the PHI is a load of a new memory location in which the
1097	// incoming value was written at the end of the incoming basic block.
1098	bool OnlyNonAffineSubRegionOperands = true;
1099	for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
1100	Value *Op = PHI->getIncomingValue(i: u);
1101	BasicBlock *OpBB = PHI->getIncomingBlock(i: u);
1102	ScopStmt *OpStmt = scop->getIncomingStmtFor(U: PHI->getOperandUse(i: u));
1103
1104	// Do not build PHI dependences inside a non-affine subregion, but make
1105	// sure that the necessary scalar values are still made available.
1106	if (NonAffineSubRegion && NonAffineSubRegion->contains(BB: OpBB)) {
1107	auto *OpInst = dyn_cast<Instruction>(Val: Op);
1108	if (!OpInst || !NonAffineSubRegion->contains(Inst: OpInst))
1109	ensureValueRead(V: Op, UserStmt: OpStmt);
1110	continue;
1111	}
1112
1113	OnlyNonAffineSubRegionOperands = false;
1114	ensurePHIWrite(PHI, IncomintStmt: OpStmt, IncomingBlock: OpBB, IncomingValue: Op, IsExitBlock);
1115	}
1116
1117	if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
1118	addPHIReadAccess(PHIStmt, PHI);
1119	}
1120	}
1121
1122	void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
1123	Instruction *Inst) {
1124	assert(!isa<PHINode>(Inst));
1125
1126	// Pull-in required operands.
1127	for (Use &Op : Inst->operands())
1128	ensureValueRead(V: Op.get(), UserStmt);
1129	}
1130
1131	// Create a sequence of two schedules. Either argument may be null and is
1132	// interpreted as the empty schedule. Can also return null if both schedules are
1133	// empty.
1134	static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
1135	if (Prev.is_null())
1136	return Succ;
1137	if (Succ.is_null())
1138	return Prev;
1139
1140	return Prev.sequence(schedule2: Succ);
1141	}
1142
1143	// Create an isl_multi_union_aff that defines an identity mapping from the
1144	// elements of USet to their N-th dimension.
1145	//
1146	// # Example:
1147	//
1148	// Domain: { A[i,j]; B[i,j,k] }
1149	// N: 1
1150	//
1151	// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
1152	//
1153	// @param USet A union set describing the elements for which to generate a
1154	// mapping.
1155	// @param N The dimension to map to.
1156	// @returns A mapping from USet to its N-th dimension.
1157	static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, unsigned N) {
1158	assert(!USet.is_null());
1159	assert(!USet.is_empty());
1160
1161	auto Result = isl::union_pw_multi_aff::empty(space: USet.get_space());
1162
1163	for (isl::set S : USet.get_set_list()) {
1164	unsigned Dim = unsignedFromIslSize(Size: S.tuple_dim());
1165	assert(Dim >= N);
1166	auto PMA = isl::pw_multi_aff::project_out_map(space: S.get_space(), type: isl::dim::set,
1167	first: N, n: Dim - N);
1168	if (N > 1)
1169	PMA = PMA.drop_dims(type: isl::dim::out, first: 0, n: N - 1);
1170
1171	Result = Result.add_pw_multi_aff(pma: PMA);
1172	}
1173
1174	return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
1175	}
1176
1177	void ScopBuilder::buildSchedule() {
1178	Loop *L = getLoopSurroundingScop(S&: *scop, LI);
1179	LoopStackTy LoopStack({LoopStackElementTy(L, {}, 0)});
1180	buildSchedule(RN: scop->getRegion().getNode(), LoopStack);
1181	assert(LoopStack.size() == 1 && LoopStack.back().L == L);
1182	scop->setScheduleTree(LoopStack[0].Schedule);
1183	}
1184
1185	/// To generate a schedule for the elements in a Region we traverse the Region
1186	/// in reverse-post-order and add the contained RegionNodes in traversal order
1187	/// to the schedule of the loop that is currently at the top of the LoopStack.
1188	/// For loop-free codes, this results in a correct sequential ordering.
1189	///
1190	/// Example:
1191	/// bb1(0)
1192	/// / \.
1193	/// bb2(1) bb3(2)
1194	/// \ / \.
1195	/// bb4(3) bb5(4)
1196	/// \ /
1197	/// bb6(5)
1198	///
1199	/// Including loops requires additional processing. Whenever a loop header is
1200	/// encountered, the corresponding loop is added to the @p LoopStack. Starting
1201	/// from an empty schedule, we first process all RegionNodes that are within
1202	/// this loop and complete the sequential schedule at this loop-level before
1203	/// processing about any other nodes. To implement this
1204	/// loop-nodes-first-processing, the reverse post-order traversal is
1205	/// insufficient. Hence, we additionally check if the traversal yields
1206	/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
1207	/// These region-nodes are then queue and only traverse after the all nodes
1208	/// within the current loop have been processed.
1209	void ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) {
1210	Loop *OuterScopLoop = getLoopSurroundingScop(S&: *scop, LI);
1211
1212	ReversePostOrderTraversal<Region *> RTraversal(R);
1213	std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
1214	std::deque<RegionNode *> DelayList;
1215	bool LastRNWaiting = false;
1216
1217	// Iterate over the region @p R in reverse post-order but queue
1218	// sub-regions/blocks iff they are not part of the last encountered but not
1219	// completely traversed loop. The variable LastRNWaiting is a flag to indicate
1220	// that we queued the last sub-region/block from the reverse post-order
1221	// iterator. If it is set we have to explore the next sub-region/block from
1222	// the iterator (if any) to guarantee progress. If it is not set we first try
1223	// the next queued sub-region/blocks.
1224	while (!WorkList.empty() || !DelayList.empty()) {
1225	RegionNode *RN;
1226
1227	if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
1228	RN = WorkList.front();
1229	WorkList.pop_front();
1230	LastRNWaiting = false;
1231	} else {
1232	RN = DelayList.front();
1233	DelayList.pop_front();
1234	}
1235
1236	Loop *L = getRegionNodeLoop(RN, LI);
1237	if (!scop->contains(L))
1238	L = OuterScopLoop;
1239
1240	Loop *LastLoop = LoopStack.back().L;
1241	if (LastLoop != L) {
1242	if (LastLoop && !LastLoop->contains(L)) {
1243	LastRNWaiting = true;
1244	DelayList.push_back(x: RN);
1245	continue;
1246	}
1247	LoopStack.push_back(Elt: {L, {}, 0});
1248	}
1249	buildSchedule(RN, LoopStack);
1250	}
1251	}
1252
1253	void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) {
1254	if (RN->isSubRegion()) {
1255	auto *LocalRegion = RN->getNodeAs<Region>();
1256	if (!scop->isNonAffineSubRegion(R: LocalRegion)) {
1257	buildSchedule(R: LocalRegion, LoopStack);
1258	return;
1259	}
1260	}
1261
1262	assert(LoopStack.rbegin() != LoopStack.rend());
1263	auto LoopData = LoopStack.rbegin();
1264	LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
1265
1266	for (auto *Stmt : scop->getStmtListFor(RN)) {
1267	isl::union_set UDomain{Stmt->getDomain()};
1268	auto StmtSchedule = isl::schedule::from_domain(domain: UDomain);
1269	LoopData->Schedule = combineInSequence(Prev: LoopData->Schedule, Succ: StmtSchedule);
1270	}
1271
1272	// Check if we just processed the last node in this loop. If we did, finalize
1273	// the loop by:
1274	//
1275	// - adding new schedule dimensions
1276	// - folding the resulting schedule into the parent loop schedule
1277	// - dropping the loop schedule from the LoopStack.
1278	//
1279	// Then continue to check surrounding loops, which might also have been
1280	// completed by this node.
1281	size_t Dimension = LoopStack.size();
1282	while (LoopData->L &&
1283	LoopData->NumBlocksProcessed == getNumBlocksInLoop(L: LoopData->L)) {
1284	isl::schedule Schedule = LoopData->Schedule;
1285	auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
1286
1287	assert(std::next(LoopData) != LoopStack.rend());
1288	Loop *L = LoopData->L;
1289	++LoopData;
1290	--Dimension;
1291
1292	if (!Schedule.is_null()) {
1293	isl::union_set Domain = Schedule.get_domain();
1294	isl::multi_union_pw_aff MUPA = mapToDimension(USet: Domain, N: Dimension);
1295	Schedule = Schedule.insert_partial_schedule(partial: MUPA);
1296
1297	if (hasDisableAllTransformsHint(L)) {
1298	/// If any of the loops has a disable_nonforced heuristic, mark the
1299	/// entire SCoP as such. The ISL rescheduler can only reschedule the
1300	/// SCoP in its entirety.
1301	/// TODO: ScopDetection could avoid including such loops or warp them as
1302	/// boxed loop. It still needs to pass-through loop with user-defined
1303	/// metadata.
1304	scop->markDisableHeuristics();
1305	}
1306
1307	// It is easier to insert the marks here that do it retroactively.
1308	isl::id IslLoopId = createIslLoopAttr(Ctx: scop->getIslCtx(), L);
1309	if (!IslLoopId.is_null())
1310	Schedule =
1311	Schedule.get_root().child(pos: 0).insert_mark(mark: IslLoopId).get_schedule();
1312
1313	LoopData->Schedule = combineInSequence(Prev: LoopData->Schedule, Succ: Schedule);
1314	}
1315
1316	LoopData->NumBlocksProcessed += NumBlocksProcessed;
1317	}
1318	// Now pop all loops processed up there from the LoopStack
1319	LoopStack.erase(CS: LoopStack.begin() + Dimension, CE: LoopStack.end());
1320	}
1321
1322	void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
1323	// Check for uses of this instruction outside the scop. Because we do not
1324	// iterate over such instructions and therefore did not "ensure" the existence
1325	// of a write, we must determine such use here.
1326	if (scop->isEscaping(Inst))
1327	ensureValueWrite(Inst);
1328	}
1329
1330	void ScopBuilder::addRecordedAssumptions() {
1331	for (auto &AS : llvm::reverse(C&: RecordedAssumptions)) {
1332
1333	if (!AS.BB) {
1334	scop->addAssumption(Kind: AS.Kind, Set: AS.Set, Loc: AS.Loc, Sign: AS.Sign,
1335	BB: nullptr /* BasicBlock */, RTC: AS.RequiresRTC);
1336	continue;
1337	}
1338
1339	// If the domain was deleted the assumptions are void.
1340	isl_set *Dom = scop->getDomainConditions(BB: AS.BB).release();
1341	if (!Dom)
1342	continue;
1343
1344	// If a basic block was given use its domain to simplify the assumption.
1345	// In case of restrictions we know they only have to hold on the domain,
1346	// thus we can intersect them with the domain of the block. However, for
1347	// assumptions the domain has to imply them, thus:
1348	// _ _____
1349	// Dom => S <==> A v B <==> A - B
1350	//
1351	// To avoid the complement we will register A - B as a restriction not an
1352	// assumption.
1353	isl_set *S = AS.Set.copy();
1354	if (AS.Sign == AS_RESTRICTION)
1355	S = isl_set_params(set: isl_set_intersect(set1: S, set2: Dom));
1356	else /* (AS.Sign == AS_ASSUMPTION) */
1357	S = isl_set_params(set: isl_set_subtract(set1: Dom, set2: S));
1358
1359	scop->addAssumption(Kind: AS.Kind, Set: isl::manage(ptr: S), Loc: AS.Loc, Sign: AS_RESTRICTION, BB: AS.BB,
1360	RTC: AS.RequiresRTC);
1361	}
1362	}
1363
1364	void ScopBuilder::addUserAssumptions(
1365	AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1366	for (auto &Assumption : AC.assumptions()) {
1367	auto *CI = dyn_cast_or_null<CallInst>(Val&: Assumption);
1368	if (!CI || CI->arg_size() != 1)
1369	continue;
1370
1371	bool InScop = scop->contains(I: CI);
1372	if (!InScop && !scop->isDominatedBy(DT, BB: CI->getParent()))
1373	continue;
1374
1375	auto *L = LI.getLoopFor(BB: CI->getParent());
1376	auto *Val = CI->getArgOperand(i: 0);
1377	ParameterSetTy DetectedParams;
1378	auto &R = scop->getRegion();
1379	if (!isAffineConstraint(V: Val, R: &R, Scope: L, SE, Params&: DetectedParams)) {
1380	ORE.emit(
1381	OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
1382	<< "Non-affine user assumption ignored.");
1383	continue;
1384	}
1385
1386	// Collect all newly introduced parameters.
1387	ParameterSetTy NewParams;
1388	for (auto *Param : DetectedParams) {
1389	Param = extractConstantFactor(M: Param, SE).second;
1390	Param = scop->getRepresentingInvariantLoadSCEV(S: Param);
1391	if (scop->isParam(Param))
1392	continue;
1393	NewParams.insert(X: Param);
1394	}
1395
1396	SmallVector<isl_set *, 2> ConditionSets;
1397	auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
1398	BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
1399	auto *Dom = InScop ? isl_set_copy(set: scop->getDomainConditions(BB).get())
1400	: isl_set_copy(set: scop->getContext().get());
1401	assert(Dom && "Cannot propagate a nullptr.");
1402	bool Valid = buildConditionSets(BB, Condition: Val, TI, L, Domain: Dom, InvalidDomainMap,
1403	ConditionSets);
1404	isl_set_free(set: Dom);
1405
1406	if (!Valid)
1407	continue;
1408
1409	isl_set *AssumptionCtx = nullptr;
1410	if (InScop) {
1411	AssumptionCtx = isl_set_complement(set: isl_set_params(set: ConditionSets[1]));
1412	isl_set_free(set: ConditionSets[0]);
1413	} else {
1414	AssumptionCtx = isl_set_complement(set: ConditionSets[1]);
1415	AssumptionCtx = isl_set_intersect(set1: AssumptionCtx, set2: ConditionSets[0]);
1416	}
1417
1418	// Project out newly introduced parameters as they are not otherwise useful.
1419	if (!NewParams.empty()) {
1420	for (isl_size u = 0; u < isl_set_n_param(set: AssumptionCtx); u++) {
1421	auto *Id = isl_set_get_dim_id(set: AssumptionCtx, type: isl_dim_param, pos: u);
1422	auto *Param = static_cast<const SCEV *>(isl_id_get_user(id: Id));
1423	isl_id_free(id: Id);
1424
1425	if (!NewParams.count(key: Param))
1426	continue;
1427
1428	AssumptionCtx =
1429	isl_set_project_out(set: AssumptionCtx, type: isl_dim_param, first: u--, n: 1);
1430	}
1431	}
1432	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
1433	<< "Use user assumption: "
1434	<< stringFromIslObj(Obj: AssumptionCtx, DefaultValue: "null"));
1435	isl::set newContext =
1436	scop->getContext().intersect(set2: isl::manage(ptr: AssumptionCtx));
1437	scop->setContext(newContext);
1438	}
1439	}
1440
1441	bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
1442	// Memory builtins are not considered in this function.
1443	if (!Inst.isLoad() && !Inst.isStore())
1444	return false;
1445
1446	Value *Val = Inst.getValueOperand();
1447	Type *ElementType = Val->getType();
1448	Value *Address = Inst.getPointerOperand();
1449	const SCEV *AccessFunction =
1450	SE.getSCEVAtScope(V: Address, L: LI.getLoopFor(BB: Inst->getParent()));
1451	const SCEVUnknown *BasePointer =
1452	dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AccessFunction));
1453	enum MemoryAccess::AccessType AccType =
1454	isa<LoadInst>(Val: Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
1455
1456	if (auto *BitCast = dyn_cast<BitCastInst>(Val: Address))
1457	Address = BitCast->getOperand(i_nocapture: 0);
1458
1459	auto *GEP = dyn_cast<GetElementPtrInst>(Val: Address);
1460	if (!GEP || DL.getTypeAllocSize(Ty: GEP->getResultElementType()) !=
1461	DL.getTypeAllocSize(Ty: ElementType))
1462	return false;
1463
1464	SmallVector<const SCEV *, 4> Subscripts;
1465	SmallVector<int, 4> Sizes;
1466	getIndexExpressionsFromGEP(SE, GEP, Subscripts, Sizes);
1467	auto *BasePtr = GEP->getOperand(i_nocapture: 0);
1468
1469	if (auto *BasePtrCast = dyn_cast<BitCastInst>(Val: BasePtr))
1470	BasePtr = BasePtrCast->getOperand(i_nocapture: 0);
1471
1472	// Check for identical base pointers to ensure that we do not miss index
1473	// offsets that have been added before this GEP is applied.
1474	if (BasePtr != BasePointer->getValue())
1475	return false;
1476
1477	std::vector<const SCEV *> SizesSCEV;
1478
1479	const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1480
1481	Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1482	for (auto *Subscript : Subscripts) {
1483	InvariantLoadsSetTy AccessILS;
1484	if (!isAffineExpr(R: &scop->getRegion(), Scope: SurroundingLoop, Expression: Subscript, SE,
1485	ILS: &AccessILS))
1486	return false;
1487
1488	for (LoadInst *LInst : AccessILS)
1489	if (!ScopRIL.count(key: LInst))
1490	return false;
1491	}
1492
1493	if (Sizes.empty())
1494	return false;
1495
1496	SizesSCEV.push_back(x: nullptr);
1497
1498	for (auto V : Sizes)
1499	SizesSCEV.push_back(x: SE.getSCEV(
1500	V: ConstantInt::get(Ty: IntegerType::getInt64Ty(C&: BasePtr->getContext()), V)));
1501
1502	addArrayAccess(Stmt, MemAccInst: Inst, AccType, BaseAddress: BasePointer->getValue(), ElemType: ElementType,
1503	IsAffine: true, Subscripts, Sizes: SizesSCEV, AccessValue: Val);
1504	return true;
1505	}
1506
1507	bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
1508	// Memory builtins are not considered by this function.
1509	if (!Inst.isLoad() && !Inst.isStore())
1510	return false;
1511
1512	if (!PollyDelinearize)
1513	return false;
1514
1515	Value *Address = Inst.getPointerOperand();
1516	Value *Val = Inst.getValueOperand();
1517	Type *ElementType = Val->getType();
1518	unsigned ElementSize = DL.getTypeAllocSize(Ty: ElementType);
1519	enum MemoryAccess::AccessType AccType =
1520	isa<LoadInst>(Val: Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
1521
1522	const SCEV *AccessFunction =
1523	SE.getSCEVAtScope(V: Address, L: LI.getLoopFor(BB: Inst->getParent()));
1524	const SCEVUnknown *BasePointer =
1525	dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AccessFunction));
1526
1527	assert(BasePointer && "Could not find base pointer");
1528
1529	auto &InsnToMemAcc = scop->getInsnToMemAccMap();
1530	auto AccItr = InsnToMemAcc.find(x: Inst);
1531	if (AccItr == InsnToMemAcc.end())
1532	return false;
1533
1534	std::vector<const SCEV *> Sizes = {nullptr};
1535
1536	Sizes.insert(position: Sizes.end(), first: AccItr->second.Shape->DelinearizedSizes.begin(),
1537	last: AccItr->second.Shape->DelinearizedSizes.end());
1538
1539	// In case only the element size is contained in the 'Sizes' array, the
1540	// access does not access a real multi-dimensional array. Hence, we allow
1541	// the normal single-dimensional access construction to handle this.
1542	if (Sizes.size() == 1)
1543	return false;
1544
1545	// Remove the element size. This information is already provided by the
1546	// ElementSize parameter. In case the element size of this access and the
1547	// element size used for delinearization differs the delinearization is
1548	// incorrect. Hence, we invalidate the scop.
1549	//
1550	// TODO: Handle delinearization with differing element sizes.
1551	auto DelinearizedSize =
1552	cast<SCEVConstant>(Val: Sizes.back())->getAPInt().getSExtValue();
1553	Sizes.pop_back();
1554	if (ElementSize != DelinearizedSize)
1555	scop->invalidate(Kind: DELINEARIZATION, Loc: Inst->getDebugLoc(), BB: Inst->getParent());
1556
1557	addArrayAccess(Stmt, MemAccInst: Inst, AccType, BaseAddress: BasePointer->getValue(), ElemType: ElementType,
1558	IsAffine: true, Subscripts: AccItr->second.DelinearizedSubscripts, Sizes, AccessValue: Val);
1559	return true;
1560	}
1561
1562	bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
1563	auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Val&: Inst);
1564
1565	if (MemIntr == nullptr)
1566	return false;
1567
1568	auto *L = LI.getLoopFor(BB: Inst->getParent());
1569	auto *LengthVal = SE.getSCEVAtScope(V: MemIntr->getLength(), L);
1570	assert(LengthVal);
1571
1572	// Check if the length val is actually affine or if we overapproximate it
1573	InvariantLoadsSetTy AccessILS;
1574	const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1575
1576	Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1577	bool LengthIsAffine = isAffineExpr(R: &scop->getRegion(), Scope: SurroundingLoop,
1578	Expression: LengthVal, SE, ILS: &AccessILS);
1579	for (LoadInst *LInst : AccessILS)
1580	if (!ScopRIL.count(key: LInst))
1581	LengthIsAffine = false;
1582	if (!LengthIsAffine)
1583	LengthVal = nullptr;
1584
1585	auto *DestPtrVal = MemIntr->getDest();
1586	assert(DestPtrVal);
1587
1588	auto *DestAccFunc = SE.getSCEVAtScope(V: DestPtrVal, L);
1589	assert(DestAccFunc);
1590	// Ignore accesses to "NULL".
1591	// TODO: We could use this to optimize the region further, e.g., intersect
1592	// the context with
1593	// isl_set_complement(isl_set_params(getDomain()))
1594	// as we know it would be undefined to execute this instruction anyway.
1595	if (DestAccFunc->isZero())
1596	return true;
1597
1598	if (auto *U = dyn_cast<SCEVUnknown>(Val: DestAccFunc)) {
1599	if (isa<ConstantPointerNull>(Val: U->getValue()))
1600	return true;
1601	}
1602
1603	auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: DestAccFunc));
1604	assert(DestPtrSCEV);
1605	DestAccFunc = SE.getMinusSCEV(LHS: DestAccFunc, RHS: DestPtrSCEV);
1606	addArrayAccess(Stmt, MemAccInst: Inst, AccType: MemoryAccess::MUST_WRITE, BaseAddress: DestPtrSCEV->getValue(),
1607	ElemType: IntegerType::getInt8Ty(C&: DestPtrVal->getContext()),
1608	IsAffine: LengthIsAffine, Subscripts: {DestAccFunc, LengthVal}, Sizes: {nullptr},
1609	AccessValue: Inst.getValueOperand());
1610
1611	auto *MemTrans = dyn_cast<MemTransferInst>(Val: MemIntr);
1612	if (!MemTrans)
1613	return true;
1614
1615	auto *SrcPtrVal = MemTrans->getSource();
1616	assert(SrcPtrVal);
1617
1618	auto *SrcAccFunc = SE.getSCEVAtScope(V: SrcPtrVal, L);
1619	assert(SrcAccFunc);
1620	// Ignore accesses to "NULL".
1621	// TODO: See above TODO
1622	if (SrcAccFunc->isZero())
1623	return true;
1624
1625	auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: SrcAccFunc));
1626	assert(SrcPtrSCEV);
1627	SrcAccFunc = SE.getMinusSCEV(LHS: SrcAccFunc, RHS: SrcPtrSCEV);
1628	addArrayAccess(Stmt, MemAccInst: Inst, AccType: MemoryAccess::READ, BaseAddress: SrcPtrSCEV->getValue(),
1629	ElemType: IntegerType::getInt8Ty(C&: SrcPtrVal->getContext()),
1630	IsAffine: LengthIsAffine, Subscripts: {SrcAccFunc, LengthVal}, Sizes: {nullptr},
1631	AccessValue: Inst.getValueOperand());
1632
1633	return true;
1634	}
1635
1636	bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
1637	auto *CI = dyn_cast_or_null<CallInst>(Val&: Inst);
1638
1639	if (CI == nullptr)
1640	return false;
1641
1642	if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(V: CI) || isDebugCall(Inst: CI))
1643	return true;
1644
1645	auto *AF = SE.getConstant(Ty: IntegerType::getInt64Ty(C&: CI->getContext()), V: 0);
1646	auto *CalledFunction = CI->getCalledFunction();
1647	MemoryEffects ME = AA.getMemoryEffects(F: CalledFunction);
1648	if (ME.doesNotAccessMemory())
1649	return true;
1650
1651	if (ME.onlyAccessesArgPointees()) {
1652	ModRefInfo ArgMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
1653	auto AccType =
1654	!isModSet(MRI: ArgMR) ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
1655	Loop *L = LI.getLoopFor(BB: Inst->getParent());
1656	for (const auto &Arg : CI->args()) {
1657	if (!Arg->getType()->isPointerTy())
1658	continue;
1659
1660	auto *ArgSCEV = SE.getSCEVAtScope(V: Arg, L);
1661	if (ArgSCEV->isZero())
1662	continue;
1663
1664	if (auto *U = dyn_cast<SCEVUnknown>(Val: ArgSCEV)) {
1665	if (isa<ConstantPointerNull>(Val: U->getValue()))
1666	return true;
1667	}
1668
1669	auto *ArgBasePtr = cast<SCEVUnknown>(Val: SE.getPointerBase(V: ArgSCEV));
1670	addArrayAccess(Stmt, MemAccInst: Inst, AccType, BaseAddress: ArgBasePtr->getValue(),
1671	ElemType: ArgBasePtr->getType(), IsAffine: false, Subscripts: {AF}, Sizes: {nullptr}, AccessValue: CI);
1672	}
1673	return true;
1674	}
1675
1676	if (ME.onlyReadsMemory()) {
1677	GlobalReads.emplace_back(Args&: Stmt, Args&: CI);
1678	return true;
1679	}
1680	return false;
1681	}
1682
1683	bool ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
1684	// Memory builtins are not considered by this function.
1685	if (!Inst.isLoad() && !Inst.isStore())
1686	return false;
1687
1688	Value *Address = Inst.getPointerOperand();
1689	Value *Val = Inst.getValueOperand();
1690	Type *ElementType = Val->getType();
1691	enum MemoryAccess::AccessType AccType =
1692	isa<LoadInst>(Val: Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
1693
1694	const SCEV *AccessFunction =
1695	SE.getSCEVAtScope(V: Address, L: LI.getLoopFor(BB: Inst->getParent()));
1696	const SCEVUnknown *BasePointer =
1697	dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AccessFunction));
1698
1699	assert(BasePointer && "Could not find base pointer");
1700	AccessFunction = SE.getMinusSCEV(LHS: AccessFunction, RHS: BasePointer);
1701
1702	// Check if the access depends on a loop contained in a non-affine subregion.
1703	bool isVariantInNonAffineLoop = false;
1704	SetVector<const Loop *> Loops;
1705	findLoops(Expr: AccessFunction, Loops);
1706	for (const Loop *L : Loops)
1707	if (Stmt->contains(L)) {
1708	isVariantInNonAffineLoop = true;
1709	break;
1710	}
1711
1712	InvariantLoadsSetTy AccessILS;
1713
1714	Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1715	bool IsAffine = !isVariantInNonAffineLoop &&
1716	isAffineExpr(R: &scop->getRegion(), Scope: SurroundingLoop,
1717	Expression: AccessFunction, SE, ILS: &AccessILS);
1718
1719	const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1720	for (LoadInst *LInst : AccessILS)
1721	if (!ScopRIL.count(key: LInst))
1722	IsAffine = false;
1723
1724	if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
1725	AccType = MemoryAccess::MAY_WRITE;
1726
1727	addArrayAccess(Stmt, MemAccInst: Inst, AccType, BaseAddress: BasePointer->getValue(), ElemType: ElementType,
1728	IsAffine, Subscripts: {AccessFunction}, Sizes: {nullptr}, AccessValue: Val);
1729	return true;
1730	}
1731
1732	void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
1733	if (buildAccessMemIntrinsic(Inst, Stmt))
1734	return;
1735
1736	if (buildAccessCallInst(Inst, Stmt))
1737	return;
1738
1739	if (buildAccessMultiDimFixed(Inst, Stmt))
1740	return;
1741
1742	if (buildAccessMultiDimParam(Inst, Stmt))
1743	return;
1744
1745	if (buildAccessSingleDim(Inst, Stmt))
1746	return;
1747
1748	llvm_unreachable(
1749	"At least one of the buildAccess functions must handled this access, or "
1750	"ScopDetection should have rejected this SCoP");
1751	}
1752
1753	void ScopBuilder::buildAccessFunctions() {
1754	for (auto &Stmt : *scop) {
1755	if (Stmt.isBlockStmt()) {
1756	buildAccessFunctions(Stmt: &Stmt, BB&: *Stmt.getBasicBlock());
1757	continue;
1758	}
1759
1760	Region *R = Stmt.getRegion();
1761	for (BasicBlock *BB : R->blocks())
1762	buildAccessFunctions(Stmt: &Stmt, BB&: *BB, NonAffineSubRegion: R);
1763	}
1764
1765	// Build write accesses for values that are used after the SCoP.
1766	// The instructions defining them might be synthesizable and therefore not
1767	// contained in any statement, hence we iterate over the original instructions
1768	// to identify all escaping values.
1769	for (BasicBlock *BB : scop->getRegion().blocks()) {
1770	for (Instruction &Inst : *BB)
1771	buildEscapingDependences(Inst: &Inst);
1772	}
1773	}
1774
1775	bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {
1776	return !Inst->isTerminator() && !isIgnoredIntrinsic(V: Inst) &&
1777	!canSynthesize(V: Inst, S: *scop, SE: &SE, Scope: L);
1778	}
1779
1780	/// Generate a name for a statement.
1781	///
1782	/// @param BB The basic block the statement will represent.
1783	/// @param BBIdx The index of the @p BB relative to other BBs/regions.
1784	/// @param Count The index of the created statement in @p BB.
1785	/// @param IsMain Whether this is the main of all statement for @p BB. If true,
1786	/// no suffix will be added.
1787	/// @param IsLast Uses a special indicator for the last statement of a BB.
1788	static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count,
1789	bool IsMain, bool IsLast = false) {
1790	std::string Suffix;
1791	if (!IsMain) {
1792	if (UseInstructionNames)
1793	Suffix = '_';
1794	if (IsLast)
1795	Suffix += "last";
1796	else if (Count < 26)
1797	Suffix += 'a' + Count;
1798	else
1799	Suffix += std::to_string(val: Count);
1800	}
1801	return getIslCompatibleName(Prefix: "Stmt", Val: BB, Number: BBIdx, Suffix, UseInstructionNames);
1802	}
1803
1804	/// Generate a name for a statement that represents a non-affine subregion.
1805	///
1806	/// @param R The region the statement will represent.
1807	/// @param RIdx The index of the @p R relative to other BBs/regions.
1808	static std::string makeStmtName(Region *R, long RIdx) {
1809	return getIslCompatibleName(Prefix: "Stmt", Middle: R->getNameStr(), Number: RIdx, Suffix: "",
1810	UseInstructionNames);
1811	}
1812
1813	void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore) {
1814	Loop *SurroundingLoop = LI.getLoopFor(BB);
1815
1816	int Count = 0;
1817	long BBIdx = scop->getNextStmtIdx();
1818	std::vector<Instruction *> Instructions;
1819	for (Instruction &Inst : *BB) {
1820	if (shouldModelInst(Inst: &Inst, L: SurroundingLoop))
1821	Instructions.push_back(x: &Inst);
1822	if (Inst.getMetadata(Kind: "polly_split_after") ||
1823	(SplitOnStore && isa<StoreInst>(Val: Inst))) {
1824	std::string Name = makeStmtName(BB, BBIdx, Count, IsMain: Count == 0);
1825	scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1826	Count++;
1827	Instructions.clear();
1828	}
1829	}
1830
1831	std::string Name = makeStmtName(BB, BBIdx, Count, IsMain: Count == 0);
1832	scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1833	}
1834
1835	/// Is @p Inst an ordered instruction?
1836	///
1837	/// An unordered instruction is an instruction, such that a sequence of
1838	/// unordered instructions can be permuted without changing semantics. Any
1839	/// instruction for which this is not always the case is ordered.
1840	static bool isOrderedInstruction(Instruction *Inst) {
1841	return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();
1842	}
1843
1844	/// Join instructions to the same statement if one uses the scalar result of the
1845	/// other.
1846	static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,
1847	ArrayRef<Instruction *> ModeledInsts) {
1848	for (Instruction *Inst : ModeledInsts) {
1849	if (isa<PHINode>(Val: Inst))
1850	continue;
1851
1852	for (Use &Op : Inst->operands()) {
1853	Instruction *OpInst = dyn_cast<Instruction>(Val: Op.get());
1854	if (!OpInst)
1855	continue;
1856
1857	// Check if OpInst is in the BB and is a modeled instruction.
1858	auto OpVal = UnionFind.findValue(V: OpInst);
1859	if (OpVal == UnionFind.end())
1860	continue;
1861
1862	UnionFind.unionSets(V1: Inst, V2: OpInst);
1863	}
1864	}
1865	}
1866
1867	/// Ensure that the order of ordered instructions does not change.
1868	///
1869	/// If we encounter an ordered instruction enclosed in instructions belonging to
1870	/// a different statement (which might as well contain ordered instructions, but
1871	/// this is not tested here), join them.
1872	static void
1873	joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
1874	ArrayRef<Instruction *> ModeledInsts) {
1875	SetVector<Instruction *> SeenLeaders;
1876	for (Instruction *Inst : ModeledInsts) {
1877	if (!isOrderedInstruction(Inst))
1878	continue;
1879
1880	Instruction *Leader = UnionFind.getLeaderValue(V: Inst);
1881	// Since previous iterations might have merged sets, some items in
1882	// SeenLeaders are not leaders anymore. However, The new leader of
1883	// previously merged instructions must be one of the former leaders of
1884	// these merged instructions.
1885	bool Inserted = SeenLeaders.insert(X: Leader);
1886	if (Inserted)
1887	continue;
1888
1889	// Merge statements to close holes. Say, we have already seen statements A
1890	// and B, in this order. Then we see an instruction of A again and we would
1891	// see the pattern "A B A". This function joins all statements until the
1892	// only seen occurrence of A.
1893	for (Instruction *Prev : reverse(C&: SeenLeaders)) {
1894	// We are backtracking from the last element until we see Inst's leader
1895	// in SeenLeaders and merge all into one set. Although leaders of
1896	// instructions change during the execution of this loop, it's irrelevant
1897	// as we are just searching for the element that we already confirmed is
1898	// in the list.
1899	if (Prev == Leader)
1900	break;
1901	UnionFind.unionSets(V1: Prev, V2: Leader);
1902	}
1903	}
1904	}
1905
1906	/// If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for
1907	/// the incoming values from this block are executed after the PHI READ.
1908	///
1909	/// Otherwise it could overwrite the incoming value from before the BB with the
1910	/// value for the next execution. This can happen if the PHI WRITE is added to
1911	/// the statement with the instruction that defines the incoming value (instead
1912	/// of the last statement of the same BB). To ensure that the PHI READ and WRITE
1913	/// are in order, we put both into the statement. PHI WRITEs are always executed
1914	/// after PHI READs when they are in the same statement.
1915	///
1916	/// TODO: This is an overpessimization. We only have to ensure that the PHI
1917	/// WRITE is not put into a statement containing the PHI itself. That could also
1918	/// be done by
1919	/// - having all (strongly connected) PHIs in a single statement,
1920	/// - unite only the PHIs in the operand tree of the PHI WRITE (because it only
1921	/// has a chance of being lifted before a PHI by being in a statement with a
1922	/// PHI that comes before in the basic block), or
1923	/// - when uniting statements, ensure that no (relevant) PHIs are overtaken.
1924	static void joinOrderedPHIs(EquivalenceClasses<Instruction *> &UnionFind,
1925	ArrayRef<Instruction *> ModeledInsts) {
1926	for (Instruction *Inst : ModeledInsts) {
1927	PHINode *PHI = dyn_cast<PHINode>(Val: Inst);
1928	if (!PHI)
1929	continue;
1930
1931	int Idx = PHI->getBasicBlockIndex(BB: PHI->getParent());
1932	if (Idx < 0)
1933	continue;
1934
1935	Instruction *IncomingVal =
1936	dyn_cast<Instruction>(Val: PHI->getIncomingValue(i: Idx));
1937	if (!IncomingVal)
1938	continue;
1939
1940	UnionFind.unionSets(V1: PHI, V2: IncomingVal);
1941	}
1942	}
1943
1944	void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
1945	Loop *L = LI.getLoopFor(BB);
1946
1947	// Extracting out modeled instructions saves us from checking
1948	// shouldModelInst() repeatedly.
1949	SmallVector<Instruction *, 32> ModeledInsts;
1950	EquivalenceClasses<Instruction *> UnionFind;
1951	Instruction *MainInst = nullptr, *MainLeader = nullptr;
1952	for (Instruction &Inst : *BB) {
1953	if (!shouldModelInst(Inst: &Inst, L))
1954	continue;
1955	ModeledInsts.push_back(Elt: &Inst);
1956	UnionFind.insert(Data: &Inst);
1957
1958	// When a BB is split into multiple statements, the main statement is the
1959	// one containing the 'main' instruction. We select the first instruction
1960	// that is unlikely to be removed (because it has side-effects) as the main
1961	// one. It is used to ensure that at least one statement from the bb has the
1962	// same name as with -polly-stmt-granularity=bb.
1963	if (!MainInst && (isa<StoreInst>(Val: Inst) ||
1964	(isa<CallInst>(Val: Inst) && !isa<IntrinsicInst>(Val: Inst))))
1965	MainInst = &Inst;
1966	}
1967
1968	joinOperandTree(UnionFind, ModeledInsts);
1969	joinOrderedInstructions(UnionFind, ModeledInsts);
1970	joinOrderedPHIs(UnionFind, ModeledInsts);
1971
1972	// The list of instructions for statement (statement represented by the leader
1973	// instruction).
1974	MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
1975
1976	// The order of statements must be preserved w.r.t. their ordered
1977	// instructions. Without this explicit scan, we would also use non-ordered
1978	// instructions (whose order is arbitrary) to determine statement order.
1979	for (Instruction *Inst : ModeledInsts) {
1980	if (!isOrderedInstruction(Inst))
1981	continue;
1982
1983	auto LeaderIt = UnionFind.findLeader(V: Inst);
1984	if (LeaderIt == UnionFind.member_end())
1985	continue;
1986
1987	// Insert element for the leader instruction.
1988	(void)LeaderToInstList[*LeaderIt];
1989	}
1990
1991	// Collect the instructions of all leaders. UnionFind's member iterator
1992	// unfortunately are not in any specific order.
1993	for (Instruction *Inst : ModeledInsts) {
1994	auto LeaderIt = UnionFind.findLeader(V: Inst);
1995	if (LeaderIt == UnionFind.member_end())
1996	continue;
1997
1998	if (Inst == MainInst)
1999	MainLeader = *LeaderIt;
2000	std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
2001	InstList.push_back(x: Inst);
2002	}
2003
2004	// Finally build the statements.
2005	int Count = 0;
2006	long BBIdx = scop->getNextStmtIdx();
2007	for (auto &Instructions : LeaderToInstList) {
2008	std::vector<Instruction *> &InstList = Instructions.second;
2009
2010	// If there is no main instruction, make the first statement the main.
2011	bool IsMain = (MainInst ? MainLeader == Instructions.first : Count == 0);
2012
2013	std::string Name = makeStmtName(BB, BBIdx, Count, IsMain);
2014	scop->addScopStmt(BB, Name, SurroundingLoop: L, Instructions: std::move(InstList));
2015	Count += 1;
2016	}
2017
2018	// Unconditionally add an epilogue (last statement). It contains no
2019	// instructions, but holds the PHI write accesses for successor basic blocks,
2020	// if the incoming value is not defined in another statement if the same BB.
2021	// The epilogue becomes the main statement only if there is no other
2022	// statement that could become main.
2023	// The epilogue will be removed if no PHIWrite is added to it.
2024	std::string EpilogueName = makeStmtName(BB, BBIdx, Count, IsMain: Count == 0, IsLast: true);
2025	scop->addScopStmt(BB, Name: EpilogueName, SurroundingLoop: L, Instructions: {});
2026	}
2027
2028	void ScopBuilder::buildStmts(Region &SR) {
2029	if (scop->isNonAffineSubRegion(R: &SR)) {
2030	std::vector<Instruction *> Instructions;
2031	Loop *SurroundingLoop =
2032	getFirstNonBoxedLoopFor(BB: SR.getEntry(), LI, BoxedLoops: scop->getBoxedLoops());
2033	for (Instruction &Inst : *SR.getEntry())
2034	if (shouldModelInst(Inst: &Inst, L: SurroundingLoop))
2035	Instructions.push_back(x: &Inst);
2036	long RIdx = scop->getNextStmtIdx();
2037	std::string Name = makeStmtName(R: &SR, RIdx);
2038	scop->addScopStmt(R: &SR, Name, SurroundingLoop, EntryBlockInstructions: Instructions);
2039	return;
2040	}
2041
2042	for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
2043	if (I->isSubRegion())
2044	buildStmts(SR&: *I->getNodeAs<Region>());
2045	else {
2046	BasicBlock *BB = I->getNodeAs<BasicBlock>();
2047	switch (StmtGranularity) {
2048	case GranularityChoice::BasicBlocks:
2049	buildSequentialBlockStmts(BB);
2050	break;
2051	case GranularityChoice::ScalarIndependence:
2052	buildEqivClassBlockStmts(BB);
2053	break;
2054	case GranularityChoice::Stores:
2055	buildSequentialBlockStmts(BB, SplitOnStore: true);
2056	break;
2057	}
2058	}
2059	}
2060
2061	void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
2062	Region *NonAffineSubRegion) {
2063	assert(
2064	Stmt &&
2065	"The exit BB is the only one that cannot be represented by a statement");
2066	assert(Stmt->represents(&BB));
2067
2068	// We do not build access functions for error blocks, as they may contain
2069	// instructions we can not model.
2070	if (SD.isErrorBlock(BB, R: scop->getRegion()))
2071	return;
2072
2073	auto BuildAccessesForInst = [this, Stmt,
2074	NonAffineSubRegion](Instruction *Inst) {
2075	PHINode *PHI = dyn_cast<PHINode>(Val: Inst);
2076	if (PHI)
2077	buildPHIAccesses(PHIStmt: Stmt, PHI, NonAffineSubRegion, IsExitBlock: false);
2078
2079	if (auto MemInst = MemAccInst::dyn_cast(V&: *Inst)) {
2080	assert(Stmt && "Cannot build access function in non-existing statement");
2081	buildMemoryAccess(Inst: MemInst, Stmt);
2082	}
2083
2084	// PHI nodes have already been modeled above and terminators that are
2085	// not part of a non-affine subregion are fully modeled and regenerated
2086	// from the polyhedral domains. Hence, they do not need to be modeled as
2087	// explicit data dependences.
2088	if (!PHI)
2089	buildScalarDependences(UserStmt: Stmt, Inst);
2090	};
2091
2092	const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
2093	bool IsEntryBlock = (Stmt->getEntryBlock() == &BB);
2094	if (IsEntryBlock) {
2095	for (Instruction *Inst : Stmt->getInstructions())
2096	BuildAccessesForInst(Inst);
2097	if (Stmt->isRegionStmt())
2098	BuildAccessesForInst(BB.getTerminator());
2099	} else {
2100	for (Instruction &Inst : BB) {
2101	if (isIgnoredIntrinsic(V: &Inst))
2102	continue;
2103
2104	// Invariant loads already have been processed.
2105	if (isa<LoadInst>(Val: Inst) && RIL.count(key: cast<LoadInst>(Val: &Inst)))
2106	continue;
2107
2108	BuildAccessesForInst(&Inst);
2109	}
2110	}
2111	}
2112
2113	MemoryAccess *ScopBuilder::addMemoryAccess(
2114	ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,
2115	Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
2116	ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
2117	MemoryKind Kind) {
2118	bool isKnownMustAccess = false;
2119
2120	// Accesses in single-basic block statements are always executed.
2121	if (Stmt->isBlockStmt())
2122	isKnownMustAccess = true;
2123
2124	if (Stmt->isRegionStmt()) {
2125	// Accesses that dominate the exit block of a non-affine region are always
2126	// executed. In non-affine regions there may exist MemoryKind::Values that
2127	// do not dominate the exit. MemoryKind::Values will always dominate the
2128	// exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
2129	// non-affine region.
2130	if (Inst && DT.dominates(A: Inst->getParent(), B: Stmt->getRegion()->getExit()))
2131	isKnownMustAccess = true;
2132	}
2133
2134	// Non-affine PHI writes do not "happen" at a particular instruction, but
2135	// after exiting the statement. Therefore they are guaranteed to execute and
2136	// overwrite the old value.
2137	if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
2138	isKnownMustAccess = true;
2139
2140	if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
2141	AccType = MemoryAccess::MAY_WRITE;
2142
2143	auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
2144	Affine, Subscripts, Sizes, AccessValue, Kind);
2145
2146	scop->addAccessFunction(Access);
2147	Stmt->addAccess(Access);
2148	return Access;
2149	}
2150
2151	void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
2152	MemoryAccess::AccessType AccType,
2153	Value *BaseAddress, Type *ElementType,
2154	bool IsAffine,
2155	ArrayRef<const SCEV *> Subscripts,
2156	ArrayRef<const SCEV *> Sizes,
2157	Value *AccessValue) {
2158	ArrayBasePointers.insert(X: BaseAddress);
2159	addMemoryAccess(Stmt, Inst: MemAccInst, AccType, BaseAddress, ElementType, Affine: IsAffine,
2160	AccessValue, Subscripts, Sizes, Kind: MemoryKind::Array);
2161	}
2162
2163	/// Check if @p Expr is divisible by @p Size.
2164	static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
2165	assert(Size != 0);
2166	if (Size == 1)
2167	return true;
2168
2169	// Only one factor needs to be divisible.
2170	if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Val: Expr)) {
2171	for (auto *FactorExpr : MulExpr->operands())
2172	if (isDivisible(Expr: FactorExpr, Size, SE))
2173	return true;
2174	return false;
2175	}
2176
2177	// For other n-ary expressions (Add, AddRec, Max,...) all operands need
2178	// to be divisible.
2179	if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Val: Expr)) {
2180	for (auto *OpExpr : NAryExpr->operands())
2181	if (!isDivisible(Expr: OpExpr, Size, SE))
2182	return false;
2183	return true;
2184	}
2185
2186	auto *SizeSCEV = SE.getConstant(Ty: Expr->getType(), V: Size);
2187	auto *UDivSCEV = SE.getUDivExpr(LHS: Expr, RHS: SizeSCEV);
2188	auto *MulSCEV = SE.getMulExpr(LHS: UDivSCEV, RHS: SizeSCEV);
2189	return MulSCEV == Expr;
2190	}
2191
2192	void ScopBuilder::foldSizeConstantsToRight() {
2193	isl::union_set Accessed = scop->getAccesses().range();
2194
2195	for (auto Array : scop->arrays()) {
2196	if (Array->getNumberOfDimensions() <= 1)
2197	continue;
2198
2199	isl::space Space = Array->getSpace();
2200	Space = Space.align_params(space2: Accessed.get_space());
2201
2202	if (!Accessed.contains(space: Space))
2203	continue;
2204
2205	isl::set Elements = Accessed.extract_set(space: Space);
2206	isl::map Transform = isl::map::universe(space: Array->getSpace().map_from_set());
2207
2208	std::vector<int> Int;
2209	unsigned Dims = unsignedFromIslSize(Size: Elements.tuple_dim());
2210	for (unsigned i = 0; i < Dims; i++) {
2211	isl::set DimOnly = isl::set(Elements).project_out(type: isl::dim::set, first: 0, n: i);
2212	DimOnly = DimOnly.project_out(type: isl::dim::set, first: 1, n: Dims - i - 1);
2213	DimOnly = DimOnly.lower_bound_si(type: isl::dim::set, pos: 0, value: 0);
2214
2215	isl::basic_set DimHull = DimOnly.affine_hull();
2216
2217	if (i == Dims - 1) {
2218	Int.push_back(x: 1);
2219	Transform = Transform.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
2220	continue;
2221	}
2222
2223	if (unsignedFromIslSize(Size: DimHull.dim(type: isl::dim::div)) == 1) {
2224	isl::aff Diff = DimHull.get_div(pos: 0);
2225	isl::val Val = Diff.get_denominator_val();
2226
2227	int ValInt = 1;
2228	if (Val.is_int()) {
2229	auto ValAPInt = APIntFromVal(V: Val);
2230	if (ValAPInt.isSignedIntN(N: 32))
2231	ValInt = ValAPInt.getSExtValue();
2232	} else {
2233	}
2234
2235	Int.push_back(x: ValInt);
2236	isl::constraint C = isl::constraint::alloc_equality(
2237	ls: isl::local_space(Transform.get_space()));
2238	C = C.set_coefficient_si(type: isl::dim::out, pos: i, v: ValInt);
2239	C = C.set_coefficient_si(type: isl::dim::in, pos: i, v: -1);
2240	Transform = Transform.add_constraint(constraint: C);
2241	continue;
2242	}
2243
2244	isl::basic_set ZeroSet = isl::basic_set(DimHull);
2245	ZeroSet = ZeroSet.fix_si(type: isl::dim::set, pos: 0, value: 0);
2246
2247	int ValInt = 1;
2248	if (ZeroSet.is_equal(bset2: DimHull)) {
2249	ValInt = 0;
2250	}
2251
2252	Int.push_back(x: ValInt);
2253	Transform = Transform.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
2254	}
2255
2256	isl::set MappedElements = isl::map(Transform).domain();
2257	if (!Elements.is_subset(set2: MappedElements))
2258	continue;
2259
2260	bool CanFold = true;
2261	if (Int[0] <= 1)
2262	CanFold = false;
2263
2264	unsigned NumDims = Array->getNumberOfDimensions();
2265	for (unsigned i = 1; i < NumDims - 1; i++)
2266	if (Int[0] != Int[i] && Int[i])
2267	CanFold = false;
2268
2269	if (!CanFold)
2270	continue;
2271
2272	for (auto &Access : scop->access_functions())
2273	if (Access->getScopArrayInfo() == Array)
2274	Access->setAccessRelation(
2275	Access->getAccessRelation().apply_range(map2: Transform));
2276
2277	std::vector<const SCEV *> Sizes;
2278	for (unsigned i = 0; i < NumDims; i++) {
2279	auto Size = Array->getDimensionSize(Dim: i);
2280
2281	if (i == NumDims - 1)
2282	Size = SE.getMulExpr(LHS: Size, RHS: SE.getConstant(Ty: Size->getType(), V: Int[0]));
2283	Sizes.push_back(x: Size);
2284	}
2285
2286	Array->updateSizes(Sizes, CheckConsistency: false /* CheckConsistency */);
2287	}
2288	}
2289
2290	void ScopBuilder::finalizeAccesses() {
2291	updateAccessDimensionality();
2292	foldSizeConstantsToRight();
2293	foldAccessRelations();
2294	assumeNoOutOfBounds();
2295	}
2296
2297	void ScopBuilder::updateAccessDimensionality() {
2298	// Check all array accesses for each base pointer and find a (virtual) element
2299	// size for the base pointer that divides all access functions.
2300	for (ScopStmt &Stmt : *scop)
2301	for (MemoryAccess *Access : Stmt) {
2302	if (!Access->isArrayKind())
2303	continue;
2304	ScopArrayInfo *Array =
2305	const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
2306
2307	if (Array->getNumberOfDimensions() != 1)
2308	continue;
2309	unsigned DivisibleSize = Array->getElemSizeInBytes();
2310	const SCEV *Subscript = Access->getSubscript(Dim: 0);
2311	while (!isDivisible(Expr: Subscript, Size: DivisibleSize, SE))
2312	DivisibleSize /= 2;
2313	auto *Ty = IntegerType::get(C&: SE.getContext(), NumBits: DivisibleSize * 8);
2314	Array->updateElementType(NewElementType: Ty);
2315	}
2316
2317	for (auto &Stmt : *scop)
2318	for (auto &Access : Stmt)
2319	Access->updateDimensionality();
2320	}
2321
2322	void ScopBuilder::foldAccessRelations() {
2323	for (auto &Stmt : *scop)
2324	for (auto &Access : Stmt)
2325	Access->foldAccessRelation();
2326	}
2327
2328	void ScopBuilder::assumeNoOutOfBounds() {
2329	if (PollyIgnoreInbounds)
2330	return;
2331	for (auto &Stmt : *scop)
2332	for (auto &Access : Stmt) {
2333	isl::set Outside = Access->assumeNoOutOfBound();
2334	const auto &Loc = Access->getAccessInstruction()
2335	? Access->getAccessInstruction()->getDebugLoc()
2336	: DebugLoc();
2337	recordAssumption(RecordedAssumptions: &RecordedAssumptions, Kind: INBOUNDS, Set: Outside, Loc,
2338	Sign: AS_ASSUMPTION);
2339	}
2340	}
2341
2342	void ScopBuilder::ensureValueWrite(Instruction *Inst) {
2343	// Find the statement that defines the value of Inst. That statement has to
2344	// write the value to make it available to those statements that read it.
2345	ScopStmt *Stmt = scop->getStmtFor(Inst);
2346
2347	// It is possible that the value is synthesizable within a loop (such that it
2348	// is not part of any statement), but not after the loop (where you need the
2349	// number of loop round-trips to synthesize it). In LCSSA-form a PHI node will
2350	// avoid this. In case the IR has no such PHI, use the last statement (where
2351	// the value is synthesizable) to write the value.
2352	if (!Stmt)
2353	Stmt = scop->getLastStmtFor(BB: Inst->getParent());
2354
2355	// Inst not defined within this SCoP.
2356	if (!Stmt)
2357	return;
2358
2359	// Do not process further if the instruction is already written.
2360	if (Stmt->lookupValueWriteOf(Inst))
2361	return;
2362
2363	addMemoryAccess(Stmt, Inst, AccType: MemoryAccess::MUST_WRITE, BaseAddress: Inst, ElementType: Inst->getType(),
2364	Affine: true, AccessValue: Inst, Subscripts: ArrayRef<const SCEV *>(),
2365	Sizes: ArrayRef<const SCEV *>(), Kind: MemoryKind::Value);
2366	}
2367
2368	void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
2369	// TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
2370	// to be able to replace this one. Currently, there is a split responsibility.
2371	// In a first step, the MemoryAccess is created, but without the
2372	// AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
2373	// AccessRelation is created. At least for scalar accesses, there is no new
2374	// information available at ScopStmt::buildAccessRelations(), so we could
2375	// create the AccessRelation right away. This is what
2376	// ScopStmt::ensureValueRead(Value*) does.
2377
2378	auto *Scope = UserStmt->getSurroundingLoop();
2379	auto VUse = VirtualUse::create(S: scop.get(), UserStmt, UserScope: Scope, Val: V, Virtual: false);
2380	switch (VUse.getKind()) {
2381	case VirtualUse::Constant:
2382	case VirtualUse::Block:
2383	case VirtualUse::Synthesizable:
2384	case VirtualUse::Hoisted:
2385	case VirtualUse::Intra:
2386	// Uses of these kinds do not need a MemoryAccess.
2387	break;
2388
2389	case VirtualUse::ReadOnly:
2390	// Add MemoryAccess for invariant values only if requested.
2391	if (!ModelReadOnlyScalars)
2392	break;
2393
2394	[[fallthrough]];
2395	case VirtualUse::Inter:
2396
2397	// Do not create another MemoryAccess for reloading the value if one already
2398	// exists.
2399	if (UserStmt->lookupValueReadOf(Inst: V))
2400	break;
2401
2402	addMemoryAccess(Stmt: UserStmt, Inst: nullptr, AccType: MemoryAccess::READ, BaseAddress: V, ElementType: V->getType(),
2403	Affine: true, AccessValue: V, Subscripts: ArrayRef<const SCEV *>(), Sizes: ArrayRef<const SCEV *>(),
2404	Kind: MemoryKind::Value);
2405
2406	// Inter-statement uses need to write the value in their defining statement.
2407	if (VUse.isInter())
2408	ensureValueWrite(Inst: cast<Instruction>(Val: V));
2409	break;
2410	}
2411	}
2412
2413	void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,
2414	BasicBlock *IncomingBlock,
2415	Value *IncomingValue, bool IsExitBlock) {
2416	// As the incoming block might turn out to be an error statement ensure we
2417	// will create an exit PHI SAI object. It is needed during code generation
2418	// and would be created later anyway.
2419	if (IsExitBlock)
2420	scop->getOrCreateScopArrayInfo(BasePtr: PHI, ElementType: PHI->getType(), Sizes: {},
2421	Kind: MemoryKind::ExitPHI);
2422
2423	// This is possible if PHI is in the SCoP's entry block. The incoming blocks
2424	// from outside the SCoP's region have no statement representation.
2425	if (!IncomingStmt)
2426	return;
2427
2428	// Take care for the incoming value being available in the incoming block.
2429	// This must be done before the check for multiple PHI writes because multiple
2430	// exiting edges from subregion each can be the effective written value of the
2431	// subregion. As such, all of them must be made available in the subregion
2432	// statement.
2433	ensureValueRead(V: IncomingValue, UserStmt: IncomingStmt);
2434
2435	// Do not add more than one MemoryAccess per PHINode and ScopStmt.
2436	if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
2437	assert(Acc->getAccessInstruction() == PHI);
2438	Acc->addIncoming(IncomingBlock, IncomingValue);
2439	return;
2440	}
2441
2442	MemoryAccess *Acc = addMemoryAccess(
2443	Stmt: IncomingStmt, Inst: PHI, AccType: MemoryAccess::MUST_WRITE, BaseAddress: PHI, ElementType: PHI->getType(), Affine: true,
2444	AccessValue: PHI, Subscripts: ArrayRef<const SCEV *>(), Sizes: ArrayRef<const SCEV *>(),
2445	Kind: IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
2446	assert(Acc);
2447	Acc->addIncoming(IncomingBlock, IncomingValue);
2448	}
2449
2450	void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {
2451	addMemoryAccess(Stmt: PHIStmt, Inst: PHI, AccType: MemoryAccess::READ, BaseAddress: PHI, ElementType: PHI->getType(), Affine: true,
2452	AccessValue: PHI, Subscripts: ArrayRef<const SCEV *>(), Sizes: ArrayRef<const SCEV *>(),
2453	Kind: MemoryKind::PHI);
2454	}
2455
2456	void ScopBuilder::buildDomain(ScopStmt &Stmt) {
2457	isl::id Id = isl::id::alloc(ctx: scop->getIslCtx(), name: Stmt.getBaseName(), user: &Stmt);
2458
2459	Stmt.Domain = scop->getDomainConditions(Stmt: &Stmt);
2460	Stmt.Domain = Stmt.Domain.set_tuple_id(Id);
2461	}
2462
2463	void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) {
2464	isl::set Domain = Stmt.getDomain();
2465	BasicBlock *BB = Stmt.getEntryBlock();
2466
2467	Loop *L = LI.getLoopFor(BB);
2468
2469	while (L && Stmt.isRegionStmt() && Stmt.getRegion()->contains(L))
2470	L = L->getParentLoop();
2471
2472	SmallVector<llvm::Loop *, 8> Loops;
2473
2474	while (L && Stmt.getParent()->getRegion().contains(L)) {
2475	Loops.push_back(Elt: L);
2476	L = L->getParentLoop();
2477	}
2478
2479	Stmt.NestLoops.insert(I: Stmt.NestLoops.begin(), From: Loops.rbegin(), To: Loops.rend());
2480	}
2481
2482	/// Return the reduction type for a given binary operator.
2483	static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
2484	const Instruction *Load) {
2485	if (!BinOp)
2486	return MemoryAccess::RT_NONE;
2487	switch (BinOp->getOpcode()) {
2488	case Instruction::FAdd:
2489	if (!BinOp->isFast())
2490	return MemoryAccess::RT_NONE;
2491	[[fallthrough]];
2492	case Instruction::Add:
2493	return MemoryAccess::RT_ADD;
2494	case Instruction::Or:
2495	return MemoryAccess::RT_BOR;
2496	case Instruction::Xor:
2497	return MemoryAccess::RT_BXOR;
2498	case Instruction::And:
2499	return MemoryAccess::RT_BAND;
2500	case Instruction::FMul:
2501	if (!BinOp->isFast())
2502	return MemoryAccess::RT_NONE;
2503	[[fallthrough]];
2504	case Instruction::Mul:
2505	if (DisableMultiplicativeReductions)
2506	return MemoryAccess::RT_NONE;
2507	return MemoryAccess::RT_MUL;
2508	default:
2509	return MemoryAccess::RT_NONE;
2510	}
2511	}
2512
2513	/// True if @p AllAccs intersects with @p MemAccs execpt @p LoadMA and @p
2514	/// StoreMA
2515	bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA,
2516	MemoryAccess *StoreMA, isl::set Domain,
2517	SmallVector<MemoryAccess *, 8> &MemAccs) {
2518	bool HasIntersectingAccs = false;
2519	auto AllAccsNoParams = AllAccs.project_out_all_params();
2520
2521	for (MemoryAccess *MA : MemAccs) {
2522	if (MA == LoadMA || MA == StoreMA)
2523	continue;
2524	auto AccRel = MA->getAccessRelation().intersect_domain(set: Domain);
2525	auto Accs = AccRel.range();
2526	auto AccsNoParams = Accs.project_out_all_params();
2527
2528	bool CompatibleSpace = AllAccsNoParams.has_equal_space(set2: AccsNoParams);
2529
2530	if (CompatibleSpace) {
2531	auto OverlapAccs = Accs.intersect(set2: AllAccs);
2532	bool DoesIntersect = !OverlapAccs.is_empty();
2533	HasIntersectingAccs |= DoesIntersect;
2534	}
2535	}
2536	return HasIntersectingAccs;
2537	}
2538
2539	/// Test if the accesses of @p LoadMA and @p StoreMA can form a reduction
2540	bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA,
2541	isl::set Domain,
2542	SmallVector<MemoryAccess *, 8> &MemAccs) {
2543	// First check if the base value is the same.
2544	isl::map LoadAccs = LoadMA->getAccessRelation();
2545	isl::map StoreAccs = StoreMA->getAccessRelation();
2546	bool Valid = LoadAccs.has_equal_space(map2: StoreAccs);
2547	LLVM_DEBUG(dbgs() << " == The accessed space below is "
2548	<< (Valid ? "" : "not ") << "equal!\n");
2549	LLVM_DEBUG(LoadMA->dump(); StoreMA->dump());
2550
2551	if (Valid) {
2552	// Then check if they actually access the same memory.
2553	isl::map R = isl::manage(ptr: LoadAccs.copy())
2554	.intersect_domain(set: isl::manage(ptr: Domain.copy()));
2555	isl::map W = isl::manage(ptr: StoreAccs.copy())
2556	.intersect_domain(set: isl::manage(ptr: Domain.copy()));
2557	isl::set RS = R.range();
2558	isl::set WS = W.range();
2559
2560	isl::set InterAccs =
2561	isl::manage(ptr: RS.copy()).intersect(set2: isl::manage(ptr: WS.copy()));
2562	Valid = !InterAccs.is_empty();
2563	LLVM_DEBUG(dbgs() << " == The accessed memory is " << (Valid ? "" : "not ")
2564	<< "overlapping!\n");
2565	}
2566
2567	if (Valid) {
2568	// Finally, check if they are no other instructions accessing this memory
2569	isl::map AllAccsRel = LoadAccs.unite(map2: StoreAccs);
2570	AllAccsRel = AllAccsRel.intersect_domain(set: Domain);
2571	isl::set AllAccs = AllAccsRel.range();
2572	Valid = !hasIntersectingAccesses(AllAccs, LoadMA, StoreMA, Domain, MemAccs);
2573
2574	LLVM_DEBUG(dbgs() << " == The accessed memory is " << (Valid ? "not " : "")
2575	<< "accessed by other instructions!\n");
2576	}
2577	return Valid;
2578	}
2579
2580	void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
2581	SmallVector<MemoryAccess *, 2> Loads;
2582	SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
2583
2584	// First collect candidate load-store reduction chains by iterating over all
2585	// stores and collecting possible reduction loads.
2586	for (MemoryAccess *StoreMA : Stmt) {
2587	if (StoreMA->isRead())
2588	continue;
2589
2590	Loads.clear();
2591	collectCandidateReductionLoads(StoreMA, Loads);
2592	for (MemoryAccess *LoadMA : Loads)
2593	Candidates.push_back(Elt: std::make_pair(x&: LoadMA, y&: StoreMA));
2594	}
2595
2596	// Then check each possible candidate pair.
2597	for (const auto &CandidatePair : Candidates) {
2598	MemoryAccess *LoadMA = CandidatePair.first;
2599	MemoryAccess *StoreMA = CandidatePair.second;
2600	bool Valid = checkCandidatePairAccesses(LoadMA, StoreMA, Domain: Stmt.getDomain(),
2601	MemAccs&: Stmt.MemAccs);
2602	if (!Valid)
2603	continue;
2604
2605	const LoadInst *Load =
2606	dyn_cast<const LoadInst>(Val: CandidatePair.first->getAccessInstruction());
2607	MemoryAccess::ReductionType RT =
2608	getReductionType(BinOp: dyn_cast<BinaryOperator>(Val: Load->user_back()), Load);
2609
2610	// If no overlapping access was found we mark the load and store as
2611	// reduction like.
2612	LoadMA->markAsReductionLike(RT);
2613	StoreMA->markAsReductionLike(RT);
2614	}
2615	}
2616
2617	void ScopBuilder::verifyInvariantLoads() {
2618	auto &RIL = scop->getRequiredInvariantLoads();
2619	for (LoadInst *LI : RIL) {
2620	assert(LI && scop->contains(LI));
2621	// If there exists a statement in the scop which has a memory access for
2622	// @p LI, then mark this scop as infeasible for optimization.
2623	for (ScopStmt &Stmt : *scop)
2624	if (Stmt.getArrayAccessOrNULLFor(Inst: LI)) {
2625	scop->invalidate(Kind: INVARIANTLOAD, Loc: LI->getDebugLoc(), BB: LI->getParent());
2626	return;
2627	}
2628	}
2629	}
2630
2631	void ScopBuilder::hoistInvariantLoads() {
2632	if (!PollyInvariantLoadHoisting)
2633	return;
2634
2635	isl::union_map Writes = scop->getWrites();
2636	for (ScopStmt &Stmt : *scop) {
2637	InvariantAccessesTy InvariantAccesses;
2638
2639	for (MemoryAccess *Access : Stmt) {
2640	isl::set NHCtx = getNonHoistableCtx(Access, Writes);
2641	if (!NHCtx.is_null())
2642	InvariantAccesses.push_back(Elt: {.MA: Access, .NonHoistableCtx: NHCtx});
2643	}
2644
2645	// Transfer the memory access from the statement to the SCoP.
2646	for (auto InvMA : InvariantAccesses)
2647	Stmt.removeMemoryAccess(MA: InvMA.MA);
2648	addInvariantLoads(Stmt, InvMAs&: InvariantAccesses);
2649	}
2650	}
2651
2652	/// Check if an access range is too complex.
2653	///
2654	/// An access range is too complex, if it contains either many disjuncts or
2655	/// very complex expressions. As a simple heuristic, we assume if a set to
2656	/// be too complex if the sum of existentially quantified dimensions and
2657	/// set dimensions is larger than a threshold. This reliably detects both
2658	/// sets with many disjuncts as well as sets with many divisions as they
2659	/// arise in h264.
2660	///
2661	/// @param AccessRange The range to check for complexity.
2662	///
2663	/// @returns True if the access range is too complex.
2664	static bool isAccessRangeTooComplex(isl::set AccessRange) {
2665	unsigned NumTotalDims = 0;
2666
2667	for (isl::basic_set BSet : AccessRange.get_basic_set_list()) {
2668	NumTotalDims += unsignedFromIslSize(Size: BSet.dim(type: isl::dim::div));
2669	NumTotalDims += unsignedFromIslSize(Size: BSet.dim(type: isl::dim::set));
2670	}
2671
2672	if (NumTotalDims > MaxDimensionsInAccessRange)
2673	return true;
2674
2675	return false;
2676	}
2677
2678	bool ScopBuilder::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
2679	isl::union_map Writes) {
2680	if (auto *BasePtrMA = scop->lookupBasePtrAccess(MA)) {
2681	return getNonHoistableCtx(Access: BasePtrMA, Writes).is_null();
2682	}
2683
2684	Value *BaseAddr = MA->getOriginalBaseAddr();
2685	if (auto *BasePtrInst = dyn_cast<Instruction>(Val: BaseAddr))
2686	if (!isa<LoadInst>(Val: BasePtrInst))
2687	return scop->contains(I: BasePtrInst);
2688
2689	return false;
2690	}
2691
2692	void ScopBuilder::addUserContext() {
2693	if (UserContextStr.empty())
2694	return;
2695
2696	isl::set UserContext = isl::set(scop->getIslCtx(), UserContextStr.c_str());
2697	isl::space Space = scop->getParamSpace();
2698	isl::size SpaceParams = Space.dim(type: isl::dim::param);
2699	if (unsignedFromIslSize(Size: SpaceParams) !=
2700	unsignedFromIslSize(Size: UserContext.dim(type: isl::dim::param))) {
2701	std::string SpaceStr = stringFromIslObj(Obj: Space, DefaultValue: "null");
2702	errs() << "Error: the context provided in -polly-context has not the same "
2703	<< "number of dimensions than the computed context. Due to this "
2704	<< "mismatch, the -polly-context option is ignored. Please provide "
2705	<< "the context in the parameter space: " << SpaceStr << ".\n";
2706	return;
2707	}
2708
2709	for (auto i : rangeIslSize(Begin: 0, End: SpaceParams)) {
2710	std::string NameContext =
2711	scop->getContext().get_dim_name(type: isl::dim::param, pos: i);
2712	std::string NameUserContext = UserContext.get_dim_name(type: isl::dim::param, pos: i);
2713
2714	if (NameContext != NameUserContext) {
2715	std::string SpaceStr = stringFromIslObj(Obj: Space, DefaultValue: "null");
2716	errs() << "Error: the name of dimension " << i
2717	<< " provided in -polly-context " << "is '" << NameUserContext
2718	<< "', but the name in the computed " << "context is '"
2719	<< NameContext << "'. Due to this name mismatch, "
2720	<< "the -polly-context option is ignored. Please provide "
2721	<< "the context in the parameter space: " << SpaceStr << ".\n";
2722	return;
2723	}
2724
2725	UserContext = UserContext.set_dim_id(type: isl::dim::param, pos: i,
2726	id: Space.get_dim_id(type: isl::dim::param, pos: i));
2727	}
2728	isl::set newContext = scop->getContext().intersect(set2: UserContext);
2729	scop->setContext(newContext);
2730	}
2731
2732	isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access,
2733	isl::union_map Writes) {
2734	// TODO: Loads that are not loop carried, hence are in a statement with
2735	// zero iterators, are by construction invariant, though we
2736	// currently "hoist" them anyway. This is necessary because we allow
2737	// them to be treated as parameters (e.g., in conditions) and our code
2738	// generation would otherwise use the old value.
2739
2740	auto &Stmt = *Access->getStatement();
2741	BasicBlock *BB = Stmt.getEntryBlock();
2742
2743	if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine() ||
2744	Access->isMemoryIntrinsic())
2745	return {};
2746
2747	// Skip accesses that have an invariant base pointer which is defined but
2748	// not loaded inside the SCoP. This can happened e.g., if a readnone call
2749	// returns a pointer that is used as a base address. However, as we want
2750	// to hoist indirect pointers, we allow the base pointer to be defined in
2751	// the region if it is also a memory access. Each ScopArrayInfo object
2752	// that has a base pointer origin has a base pointer that is loaded and
2753	// that it is invariant, thus it will be hoisted too. However, if there is
2754	// no base pointer origin we check that the base pointer is defined
2755	// outside the region.
2756	auto *LI = cast<LoadInst>(Val: Access->getAccessInstruction());
2757	if (hasNonHoistableBasePtrInScop(MA: Access, Writes))
2758	return {};
2759
2760	isl::map AccessRelation = Access->getAccessRelation();
2761	assert(!AccessRelation.is_empty());
2762
2763	if (AccessRelation.involves_dims(type: isl::dim::in, first: 0, n: Stmt.getNumIterators()))
2764	return {};
2765
2766	AccessRelation = AccessRelation.intersect_domain(set: Stmt.getDomain());
2767	isl::set SafeToLoad;
2768
2769	auto &DL = scop->getFunction().getParent()->getDataLayout();
2770	if (isSafeToLoadUnconditionally(V: LI->getPointerOperand(), Ty: LI->getType(),
2771	Alignment: LI->getAlign(), DL)) {
2772	SafeToLoad = isl::set::universe(space: AccessRelation.get_space().range());
2773	} else if (BB != LI->getParent()) {
2774	// Skip accesses in non-affine subregions as they might not be executed
2775	// under the same condition as the entry of the non-affine subregion.
2776	return {};
2777	} else {
2778	SafeToLoad = AccessRelation.range();
2779	}
2780
2781	if (isAccessRangeTooComplex(AccessRange: AccessRelation.range()))
2782	return {};
2783
2784	isl::union_map Written = Writes.intersect_range(uset: SafeToLoad);
2785	isl::set WrittenCtx = Written.params();
2786	bool IsWritten = !WrittenCtx.is_empty();
2787
2788	if (!IsWritten)
2789	return WrittenCtx;
2790
2791	WrittenCtx = WrittenCtx.remove_divs();
2792	bool TooComplex =
2793	unsignedFromIslSize(Size: WrittenCtx.n_basic_set()) >= MaxDisjunctsInDomain;
2794	if (TooComplex || !isRequiredInvariantLoad(LI))
2795	return {};
2796
2797	scop->addAssumption(Kind: INVARIANTLOAD, Set: WrittenCtx, Loc: LI->getDebugLoc(),
2798	Sign: AS_RESTRICTION, BB: LI->getParent());
2799	return WrittenCtx;
2800	}
2801
2802	static bool isAParameter(llvm::Value *maybeParam, const Function &F) {
2803	for (const llvm::Argument &Arg : F.args())
2804	if (&Arg == maybeParam)
2805	return true;
2806
2807	return false;
2808	}
2809
2810	bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,
2811	bool StmtInvalidCtxIsEmpty,
2812	bool MAInvalidCtxIsEmpty,
2813	bool NonHoistableCtxIsEmpty) {
2814	LoadInst *LInst = cast<LoadInst>(Val: MA->getAccessInstruction());
2815	const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
2816	if (PollyAllowDereferenceOfAllFunctionParams &&
2817	isAParameter(maybeParam: LInst->getPointerOperand(), F: scop->getFunction()))
2818	return true;
2819
2820	// TODO: We can provide more information for better but more expensive
2821	// results.
2822	if (!isDereferenceableAndAlignedPointer(
2823	V: LInst->getPointerOperand(), Ty: LInst->getType(), Alignment: LInst->getAlign(), DL))
2824	return false;
2825
2826	// If the location might be overwritten we do not hoist it unconditionally.
2827	//
2828	// TODO: This is probably too conservative.
2829	if (!NonHoistableCtxIsEmpty)
2830	return false;
2831
2832	// If a dereferenceable load is in a statement that is modeled precisely we
2833	// can hoist it.
2834	if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
2835	return true;
2836
2837	// Even if the statement is not modeled precisely we can hoist the load if it
2838	// does not involve any parameters that might have been specialized by the
2839	// statement domain.
2840	for (const SCEV *Subscript : MA->subscripts())
2841	if (!isa<SCEVConstant>(Val: Subscript))
2842	return false;
2843	return true;
2844	}
2845
2846	void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,
2847	InvariantAccessesTy &InvMAs) {
2848	if (InvMAs.empty())
2849	return;
2850
2851	isl::set StmtInvalidCtx = Stmt.getInvalidContext();
2852	bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
2853
2854	// Get the context under which the statement is executed but remove the error
2855	// context under which this statement is reached.
2856	isl::set DomainCtx = Stmt.getDomain().params();
2857	DomainCtx = DomainCtx.subtract(set2: StmtInvalidCtx);
2858
2859	if (unsignedFromIslSize(Size: DomainCtx.n_basic_set()) >= MaxDisjunctsInDomain) {
2860	auto *AccInst = InvMAs.front().MA->getAccessInstruction();
2861	scop->invalidate(Kind: COMPLEXITY, Loc: AccInst->getDebugLoc(), BB: AccInst->getParent());
2862	return;
2863	}
2864
2865	// Project out all parameters that relate to loads in the statement. Otherwise
2866	// we could have cyclic dependences on the constraints under which the
2867	// hoisted loads are executed and we could not determine an order in which to
2868	// pre-load them. This happens because not only lower bounds are part of the
2869	// domain but also upper bounds.
2870	for (auto &InvMA : InvMAs) {
2871	auto *MA = InvMA.MA;
2872	Instruction *AccInst = MA->getAccessInstruction();
2873	if (SE.isSCEVable(Ty: AccInst->getType())) {
2874	SetVector<Value *> Values;
2875	for (const SCEV *Parameter : scop->parameters()) {
2876	Values.clear();
2877	findValues(Expr: Parameter, SE, Values);
2878	if (!Values.count(key: AccInst))
2879	continue;
2880
2881	isl::id ParamId = scop->getIdForParam(Parameter);
2882	if (!ParamId.is_null()) {
2883	int Dim = DomainCtx.find_dim_by_id(type: isl::dim::param, id: ParamId);
2884	if (Dim >= 0)
2885	DomainCtx = DomainCtx.eliminate(type: isl::dim::param, first: Dim, n: 1);
2886	}
2887	}
2888	}
2889	}
2890
2891	for (auto &InvMA : InvMAs) {
2892	auto *MA = InvMA.MA;
2893	isl::set NHCtx = InvMA.NonHoistableCtx;
2894
2895	// Check for another invariant access that accesses the same location as
2896	// MA and if found consolidate them. Otherwise create a new equivalence
2897	// class at the end of InvariantEquivClasses.
2898	LoadInst *LInst = cast<LoadInst>(Val: MA->getAccessInstruction());
2899	Type *Ty = LInst->getType();
2900	const SCEV *PointerSCEV = SE.getSCEV(V: LInst->getPointerOperand());
2901
2902	isl::set MAInvalidCtx = MA->getInvalidContext();
2903	bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
2904	bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
2905
2906	isl::set MACtx;
2907	// Check if we know that this pointer can be speculatively accessed.
2908	if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
2909	NonHoistableCtxIsEmpty)) {
2910	MACtx = isl::set::universe(space: DomainCtx.get_space());
2911	} else {
2912	MACtx = DomainCtx;
2913	MACtx = MACtx.subtract(set2: MAInvalidCtx.unite(set2: NHCtx));
2914	MACtx = MACtx.gist_params(context: scop->getContext());
2915	}
2916
2917	bool Consolidated = false;
2918	for (auto &IAClass : scop->invariantEquivClasses()) {
2919	if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
2920	continue;
2921
2922	// If the pointer and the type is equal check if the access function wrt.
2923	// to the domain is equal too. It can happen that the domain fixes
2924	// parameter values and these can be different for distinct part of the
2925	// SCoP. If this happens we cannot consolidate the loads but need to
2926	// create a new invariant load equivalence class.
2927	auto &MAs = IAClass.InvariantAccesses;
2928	if (!MAs.empty()) {
2929	auto *LastMA = MAs.front();
2930
2931	isl::set AR = MA->getAccessRelation().range();
2932	isl::set LastAR = LastMA->getAccessRelation().range();
2933	bool SameAR = AR.is_equal(set2: LastAR);
2934
2935	if (!SameAR)
2936	continue;
2937	}
2938
2939	// Add MA to the list of accesses that are in this class.
2940	MAs.push_front(val: MA);
2941
2942	Consolidated = true;
2943
2944	// Unify the execution context of the class and this statement.
2945	isl::set IAClassDomainCtx = IAClass.ExecutionContext;
2946	if (!IAClassDomainCtx.is_null())
2947	IAClassDomainCtx = IAClassDomainCtx.unite(set2: MACtx).coalesce();
2948	else
2949	IAClassDomainCtx = MACtx;
2950	IAClass.ExecutionContext = IAClassDomainCtx;
2951	break;
2952	}
2953
2954	if (Consolidated)
2955	continue;
2956
2957	MACtx = MACtx.coalesce();
2958
2959	// If we did not consolidate MA, thus did not find an equivalence class
2960	// for it, we create a new one.
2961	scop->addInvariantEquivClass(
2962	InvariantEquivClass: InvariantEquivClassTy{.IdentifyingPointer: PointerSCEV, .InvariantAccesses: MemoryAccessList{MA}, .ExecutionContext: MACtx, .AccessType: Ty});
2963	}
2964	}
2965
2966	void ScopBuilder::collectCandidateReductionLoads(
2967	MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
2968	ScopStmt *Stmt = StoreMA->getStatement();
2969
2970	auto *Store = dyn_cast<StoreInst>(Val: StoreMA->getAccessInstruction());
2971	if (!Store)
2972	return;
2973
2974	// Skip if there is not one binary operator between the load and the store
2975	auto *BinOp = dyn_cast<BinaryOperator>(Val: Store->getValueOperand());
2976	if (!BinOp)
2977	return;
2978
2979	// Skip if the binary operators has multiple uses
2980	if (BinOp->getNumUses() != 1)
2981	return;
2982
2983	// Skip if the opcode of the binary operator is not commutative/associative
2984	if (!BinOp->isCommutative() || !BinOp->isAssociative())
2985	return;
2986
2987	// Skip if the binary operator is outside the current SCoP
2988	if (BinOp->getParent() != Store->getParent())
2989	return;
2990
2991	// Skip if it is a multiplicative reduction and we disabled them
2992	if (DisableMultiplicativeReductions &&
2993	(BinOp->getOpcode() == Instruction::Mul ||
2994	BinOp->getOpcode() == Instruction::FMul))
2995	return;
2996
2997	// Check the binary operator operands for a candidate load
2998	auto *PossibleLoad0 = dyn_cast<LoadInst>(Val: BinOp->getOperand(i_nocapture: 0));
2999	auto *PossibleLoad1 = dyn_cast<LoadInst>(Val: BinOp->getOperand(i_nocapture: 1));
3000	if (!PossibleLoad0 && !PossibleLoad1)
3001	return;
3002
3003	// A load is only a candidate if it cannot escape (thus has only this use)
3004	if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
3005	if (PossibleLoad0->getParent() == Store->getParent())
3006	Loads.push_back(Elt: &Stmt->getArrayAccessFor(Inst: PossibleLoad0));
3007	if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
3008	if (PossibleLoad1->getParent() == Store->getParent())
3009	Loads.push_back(Elt: &Stmt->getArrayAccessFor(Inst: PossibleLoad1));
3010	}
3011
3012	/// Find the canonical scop array info object for a set of invariant load
3013	/// hoisted loads. The canonical array is the one that corresponds to the
3014	/// first load in the list of accesses which is used as base pointer of a
3015	/// scop array.
3016	static const ScopArrayInfo *findCanonicalArray(Scop &S,
3017	MemoryAccessList &Accesses) {
3018	for (MemoryAccess *Access : Accesses) {
3019	const ScopArrayInfo *CanonicalArray = S.getScopArrayInfoOrNull(
3020	BasePtr: Access->getAccessInstruction(), Kind: MemoryKind::Array);
3021	if (CanonicalArray)
3022	return CanonicalArray;
3023	}
3024	return nullptr;
3025	}
3026
3027	/// Check if @p Array severs as base array in an invariant load.
3028	static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array) {
3029	for (InvariantEquivClassTy &EqClass2 : S.getInvariantAccesses())
3030	for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
3031	if (Access2->getScopArrayInfo() == Array)
3032	return true;
3033	return false;
3034	}
3035
3036	/// Replace the base pointer arrays in all memory accesses referencing @p Old,
3037	/// with a reference to @p New.
3038	static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old,
3039	const ScopArrayInfo *New) {
3040	for (ScopStmt &Stmt : S)
3041	for (MemoryAccess *Access : Stmt) {
3042	if (Access->getLatestScopArrayInfo() != Old)
3043	continue;
3044
3045	isl::id Id = New->getBasePtrId();
3046	isl::map Map = Access->getAccessRelation();
3047	Map = Map.set_tuple_id(type: isl::dim::out, id: Id);
3048	Access->setAccessRelation(Map);
3049	}
3050	}
3051
3052	void ScopBuilder::canonicalizeDynamicBasePtrs() {
3053	for (InvariantEquivClassTy &EqClass : scop->InvariantEquivClasses) {
3054	MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
3055
3056	const ScopArrayInfo *CanonicalBasePtrSAI =
3057	findCanonicalArray(S&: *scop, Accesses&: BasePtrAccesses);
3058
3059	if (!CanonicalBasePtrSAI)
3060	continue;
3061
3062	for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
3063	const ScopArrayInfo *BasePtrSAI = scop->getScopArrayInfoOrNull(
3064	BasePtr: BasePtrAccess->getAccessInstruction(), Kind: MemoryKind::Array);
3065	if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
3066	!BasePtrSAI->isCompatibleWith(Array: CanonicalBasePtrSAI))
3067	continue;
3068
3069	// we currently do not canonicalize arrays where some accesses are
3070	// hoisted as invariant loads. If we would, we need to update the access
3071	// function of the invariant loads as well. However, as this is not a
3072	// very common situation, we leave this for now to avoid further
3073	// complexity increases.
3074	if (isUsedForIndirectHoistedLoad(S&: *scop, Array: BasePtrSAI))
3075	continue;
3076
3077	replaceBasePtrArrays(S&: *scop, Old: BasePtrSAI, New: CanonicalBasePtrSAI);
3078	}
3079	}
3080	}
3081
3082	void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) {
3083	for (MemoryAccess *Access : Stmt.MemAccs) {
3084	Type *ElementType = Access->getElementType();
3085
3086	MemoryKind Ty;
3087	if (Access->isPHIKind())
3088	Ty = MemoryKind::PHI;
3089	else if (Access->isExitPHIKind())
3090	Ty = MemoryKind::ExitPHI;
3091	else if (Access->isValueKind())
3092	Ty = MemoryKind::Value;
3093	else
3094	Ty = MemoryKind::Array;
3095
3096	// Create isl::pw_aff for SCEVs which describe sizes. Collect all
3097	// assumptions which are taken. isl::pw_aff objects are cached internally
3098	// and they are used later by scop.
3099	for (const SCEV *Size : Access->Sizes) {
3100	if (!Size)
3101	continue;
3102	scop->getPwAff(E: Size, BB: nullptr, NonNegative: false, RecordedAssumptions: &RecordedAssumptions);
3103	}
3104	auto *SAI = scop->getOrCreateScopArrayInfo(BasePtr: Access->getOriginalBaseAddr(),
3105	ElementType, Sizes: Access->Sizes, Kind: Ty);
3106
3107	// Create isl::pw_aff for SCEVs which describe subscripts. Collect all
3108	// assumptions which are taken. isl::pw_aff objects are cached internally
3109	// and they are used later by scop.
3110	for (const SCEV *Subscript : Access->subscripts()) {
3111	if (!Access->isAffine() || !Subscript)
3112	continue;
3113	scop->getPwAff(E: Subscript, BB: Stmt.getEntryBlock(), NonNegative: false,
3114	RecordedAssumptions: &RecordedAssumptions);
3115	}
3116	Access->buildAccessRelation(SAI);
3117	scop->addAccessData(Access);
3118	}
3119	}
3120
3121	/// Add the minimal/maximal access in @p Set to @p User.
3122	///
3123	/// @return True if more accesses should be added, false if we reached the
3124	/// maximal number of run-time checks to be generated.
3125	static bool buildMinMaxAccess(isl::set Set,
3126	Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
3127	isl::pw_multi_aff MinPMA, MaxPMA;
3128	isl::pw_aff LastDimAff;
3129	isl::aff OneAff;
3130	unsigned Pos;
3131
3132	Set = Set.remove_divs();
3133	polly::simplify(Set);
3134
3135	if (unsignedFromIslSize(Size: Set.n_basic_set()) > RunTimeChecksMaxAccessDisjuncts)
3136	Set = Set.simple_hull();
3137
3138	// Restrict the number of parameters involved in the access as the lexmin/
3139	// lexmax computation will take too long if this number is high.
3140	//
3141	// Experiments with a simple test case using an i7 4800MQ:
3142	//
3143	// #Parameters involved | Time (in sec)
3144	// 6 | 0.01
3145	// 7 | 0.04
3146	// 8 | 0.12
3147	// 9 | 0.40
3148	// 10 | 1.54
3149	// 11 | 6.78
3150	// 12 | 30.38
3151	//
3152	if (isl_set_n_param(set: Set.get()) >
3153	static_cast<isl_size>(RunTimeChecksMaxParameters)) {
3154	unsigned InvolvedParams = 0;
3155	for (unsigned u = 0, e = isl_set_n_param(set: Set.get()); u < e; u++)
3156	if (Set.involves_dims(type: isl::dim::param, first: u, n: 1))
3157	InvolvedParams++;
3158
3159	if (InvolvedParams > RunTimeChecksMaxParameters)
3160	return false;
3161	}
3162
3163	MinPMA = Set.lexmin_pw_multi_aff();
3164	MaxPMA = Set.lexmax_pw_multi_aff();
3165
3166	MinPMA = MinPMA.coalesce();
3167	MaxPMA = MaxPMA.coalesce();
3168
3169	if (MaxPMA.is_null())
3170	return false;
3171
3172	unsigned MaxOutputSize = unsignedFromIslSize(Size: MaxPMA.dim(type: isl::dim::out));
3173
3174	// Adjust the last dimension of the maximal access by one as we want to
3175	// enclose the accessed memory region by MinPMA and MaxPMA. The pointer
3176	// we test during code generation might now point after the end of the
3177	// allocated array but we will never dereference it anyway.
3178	assert(MaxOutputSize >= 1 && "Assumed at least one output dimension");
3179
3180	Pos = MaxOutputSize - 1;
3181	LastDimAff = MaxPMA.at(pos: Pos);
3182	OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
3183	OneAff = OneAff.add_constant_si(v: 1);
3184	LastDimAff = LastDimAff.add(pwaff2: OneAff);
3185	MaxPMA = MaxPMA.set_pw_aff(pos: Pos, pa: LastDimAff);
3186
3187	if (MinPMA.is_null() || MaxPMA.is_null())
3188	return false;
3189
3190	MinMaxAccesses.push_back(Elt: std::make_pair(x&: MinPMA, y&: MaxPMA));
3191
3192	return true;
3193	}
3194
3195	/// Wrapper function to calculate minimal/maximal accesses to each array.
3196	bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup,
3197	Scop::MinMaxVectorTy &MinMaxAccesses) {
3198	MinMaxAccesses.reserve(N: AliasGroup.size());
3199
3200	isl::union_set Domains = scop->getDomains();
3201	isl::union_map Accesses = isl::union_map::empty(ctx: scop->getIslCtx());
3202
3203	for (MemoryAccess *MA : AliasGroup)
3204	Accesses = Accesses.unite(umap2: MA->getAccessRelation());
3205
3206	Accesses = Accesses.intersect_domain(uset: Domains);
3207	isl::union_set Locations = Accesses.range();
3208
3209	bool LimitReached = false;
3210	for (isl::set Set : Locations.get_set_list()) {
3211	LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S&: *scop);
3212	if (LimitReached)
3213	break;
3214	}
3215
3216	return !LimitReached;
3217	}
3218
3219	static isl::set getAccessDomain(MemoryAccess *MA) {
3220	isl::set Domain = MA->getStatement()->getDomain();
3221	Domain = Domain.project_out(type: isl::dim::set, first: 0,
3222	n: unsignedFromIslSize(Size: Domain.tuple_dim()));
3223	return Domain.reset_tuple_id();
3224	}
3225
3226	bool ScopBuilder::buildAliasChecks() {
3227	if (!PollyUseRuntimeAliasChecks)
3228	return true;
3229
3230	if (buildAliasGroups()) {
3231	// Aliasing assumptions do not go through addAssumption but we still want to
3232	// collect statistics so we do it here explicitly.
3233	if (scop->getAliasGroups().size())
3234	Scop::incrementNumberOfAliasingAssumptions(Step: 1);
3235	return true;
3236	}
3237
3238	// If a problem occurs while building the alias groups we need to delete
3239	// this SCoP and pretend it wasn't valid in the first place. To this end
3240	// we make the assumed context infeasible.
3241	scop->invalidate(Kind: ALIASING, Loc: DebugLoc());
3242
3243	LLVM_DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr()
3244	<< " could not be created. This SCoP has been dismissed.");
3245	return false;
3246	}
3247
3248	std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
3249	ScopBuilder::buildAliasGroupsForAccesses() {
3250	BatchAAResults BAA(AA);
3251	AliasSetTracker AST(BAA);
3252
3253	DenseMap<Value *, MemoryAccess *> PtrToAcc;
3254	DenseSet<const ScopArrayInfo *> HasWriteAccess;
3255	for (ScopStmt &Stmt : *scop) {
3256
3257	isl::set StmtDomain = Stmt.getDomain();
3258	bool StmtDomainEmpty = StmtDomain.is_empty();
3259
3260	// Statements with an empty domain will never be executed.
3261	if (StmtDomainEmpty)
3262	continue;
3263
3264	for (MemoryAccess *MA : Stmt) {
3265	if (MA->isScalarKind())
3266	continue;
3267	if (!MA->isRead())
3268	HasWriteAccess.insert(V: MA->getScopArrayInfo());
3269	MemAccInst Acc(MA->getAccessInstruction());
3270	if (MA->isRead() && isa<MemTransferInst>(Val: Acc))
3271	PtrToAcc[cast<MemTransferInst>(Val&: Acc)->getRawSource()] = MA;
3272	else
3273	PtrToAcc[Acc.getPointerOperand()] = MA;
3274	AST.add(I: Acc);
3275	}
3276	}
3277
3278	AliasGroupVectorTy AliasGroups;
3279	for (AliasSet &AS : AST) {
3280	if (AS.isMustAlias() || AS.isForwardingAliasSet())
3281	continue;
3282	AliasGroupTy AG;
3283	for (const Value *Ptr : AS.getPointers())
3284	AG.push_back(Elt: PtrToAcc[const_cast<Value *>(Ptr)]);
3285	if (AG.size() < 2)
3286	continue;
3287	AliasGroups.push_back(Elt: std::move(AG));
3288	}
3289
3290	return std::make_tuple(args&: AliasGroups, args&: HasWriteAccess);
3291	}
3292
3293	bool ScopBuilder::buildAliasGroups() {
3294	// To create sound alias checks we perform the following steps:
3295	// o) We partition each group into read only and non read only accesses.
3296	// o) For each group with more than one base pointer we then compute minimal
3297	// and maximal accesses to each array of a group in read only and non
3298	// read only partitions separately.
3299	AliasGroupVectorTy AliasGroups;
3300	DenseSet<const ScopArrayInfo *> HasWriteAccess;
3301
3302	std::tie(args&: AliasGroups, args&: HasWriteAccess) = buildAliasGroupsForAccesses();
3303
3304	splitAliasGroupsByDomain(AliasGroups);
3305
3306	for (AliasGroupTy &AG : AliasGroups) {
3307	if (!scop->hasFeasibleRuntimeContext())
3308	return false;
3309
3310	{
3311	IslMaxOperationsGuard MaxOpGuard(scop->getIslCtx().get(), OptComputeOut);
3312	bool Valid = buildAliasGroup(AliasGroup&: AG, HasWriteAccess);
3313	if (!Valid)
3314	return false;
3315	}
3316	if (isl_ctx_last_error(ctx: scop->getIslCtx().get()) == isl_error_quota) {
3317	scop->invalidate(Kind: COMPLEXITY, Loc: DebugLoc());
3318	return false;
3319	}
3320	}
3321
3322	return true;
3323	}
3324
3325	bool ScopBuilder::buildAliasGroup(
3326	AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) {
3327	AliasGroupTy ReadOnlyAccesses;
3328	AliasGroupTy ReadWriteAccesses;
3329	SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
3330	SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
3331
3332	if (AliasGroup.size() < 2)
3333	return true;
3334
3335	for (MemoryAccess *Access : AliasGroup) {
3336	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias",
3337	Access->getAccessInstruction())
3338	<< "Possibly aliasing pointer, use restrict keyword.");
3339	const ScopArrayInfo *Array = Access->getScopArrayInfo();
3340	if (HasWriteAccess.count(V: Array)) {
3341	ReadWriteArrays.insert(Ptr: Array);
3342	ReadWriteAccesses.push_back(Elt: Access);
3343	} else {
3344	ReadOnlyArrays.insert(Ptr: Array);
3345	ReadOnlyAccesses.push_back(Elt: Access);
3346	}
3347	}
3348
3349	// If there are no read-only pointers, and less than two read-write pointers,
3350	// no alias check is needed.
3351	if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
3352	return true;
3353
3354	// If there is no read-write pointer, no alias check is needed.
3355	if (ReadWriteArrays.empty())
3356	return true;
3357
3358	// For non-affine accesses, no alias check can be generated as we cannot
3359	// compute a sufficiently tight lower and upper bound: bail out.
3360	for (MemoryAccess *MA : AliasGroup) {
3361	if (!MA->isAffine()) {
3362	scop->invalidate(Kind: ALIASING, Loc: MA->getAccessInstruction()->getDebugLoc(),
3363	BB: MA->getAccessInstruction()->getParent());
3364	return false;
3365	}
3366	}
3367
3368	// Ensure that for all memory accesses for which we generate alias checks,
3369	// their base pointers are available.
3370	for (MemoryAccess *MA : AliasGroup) {
3371	if (MemoryAccess *BasePtrMA = scop->lookupBasePtrAccess(MA))
3372	scop->addRequiredInvariantLoad(
3373	LI: cast<LoadInst>(Val: BasePtrMA->getAccessInstruction()));
3374	}
3375
3376	// scop->getAliasGroups().emplace_back();
3377	// Scop::MinMaxVectorPairTy &pair = scop->getAliasGroups().back();
3378	Scop::MinMaxVectorTy MinMaxAccessesReadWrite;
3379	Scop::MinMaxVectorTy MinMaxAccessesReadOnly;
3380
3381	bool Valid;
3382
3383	Valid = calculateMinMaxAccess(AliasGroup: ReadWriteAccesses, MinMaxAccesses&: MinMaxAccessesReadWrite);
3384
3385	if (!Valid)
3386	return false;
3387
3388	// Bail out if the number of values we need to compare is too large.
3389	// This is important as the number of comparisons grows quadratically with
3390	// the number of values we need to compare.
3391	if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
3392	RunTimeChecksMaxArraysPerGroup)
3393	return false;
3394
3395	Valid = calculateMinMaxAccess(AliasGroup: ReadOnlyAccesses, MinMaxAccesses&: MinMaxAccessesReadOnly);
3396
3397	scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);
3398	if (!Valid)
3399	return false;
3400
3401	return true;
3402	}
3403
3404	void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
3405	for (unsigned u = 0; u < AliasGroups.size(); u++) {
3406	AliasGroupTy NewAG;
3407	AliasGroupTy &AG = AliasGroups[u];
3408	AliasGroupTy::iterator AGI = AG.begin();
3409	isl::set AGDomain = getAccessDomain(MA: *AGI);
3410	while (AGI != AG.end()) {
3411	MemoryAccess *MA = *AGI;
3412	isl::set MADomain = getAccessDomain(MA);
3413	if (AGDomain.is_disjoint(set2: MADomain)) {
3414	NewAG.push_back(Elt: MA);
3415	AGI = AG.erase(CI: AGI);
3416	} else {
3417	AGDomain = AGDomain.unite(set2: MADomain);
3418	AGI++;
3419	}
3420	}
3421	if (NewAG.size() > 1)
3422	AliasGroups.push_back(Elt: std::move(NewAG));
3423	}
3424	}
3425
3426	#ifndef NDEBUG
3427	static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
3428	auto PhysUse = VirtualUse::create(S, U: Op, LI: &LI, Virtual: false);
3429	auto VirtUse = VirtualUse::create(S, U: Op, LI: &LI, Virtual: true);
3430	assert(PhysUse.getKind() == VirtUse.getKind());
3431	}
3432
3433	/// Check the consistency of every statement's MemoryAccesses.
3434	///
3435	/// The check is carried out by expecting the "physical" kind of use (derived
3436	/// from the BasicBlocks instructions resides in) to be same as the "virtual"
3437	/// kind of use (derived from a statement's MemoryAccess).
3438	///
3439	/// The "physical" uses are taken by ensureValueRead to determine whether to
3440	/// create MemoryAccesses. When done, the kind of scalar access should be the
3441	/// same no matter which way it was derived.
3442	///
3443	/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
3444	/// can intentionally influence on the kind of uses (not corresponding to the
3445	/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
3446	/// to pick up the virtual uses. But here in the code generator, this has not
3447	/// happened yet, such that virtual and physical uses are equivalent.
3448	static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
3449	for (auto *BB : S->getRegion().blocks()) {
3450	for (auto &Inst : *BB) {
3451	auto *Stmt = S->getStmtFor(Inst: &Inst);
3452	if (!Stmt)
3453	continue;
3454
3455	if (isIgnoredIntrinsic(V: &Inst))
3456	continue;
3457
3458	// Branch conditions are encoded in the statement domains.
3459	if (Inst.isTerminator() && Stmt->isBlockStmt())
3460	continue;
3461
3462	// Verify all uses.
3463	for (auto &Op : Inst.operands())
3464	verifyUse(S, Op, LI);
3465
3466	// Stores do not produce values used by other statements.
3467	if (isa<StoreInst>(Val: Inst))
3468	continue;
3469
3470	// For every value defined in the block, also check that a use of that
3471	// value in the same statement would not be an inter-statement use. It can
3472	// still be synthesizable or load-hoisted, but these kind of instructions
3473	// are not directly copied in code-generation.
3474	auto VirtDef =
3475	VirtualUse::create(S, UserStmt: Stmt, UserScope: Stmt->getSurroundingLoop(), Val: &Inst, Virtual: true);
3476	assert(VirtDef.getKind() == VirtualUse::Synthesizable ||
3477	VirtDef.getKind() == VirtualUse::Intra ||
3478	VirtDef.getKind() == VirtualUse::Hoisted);
3479	}
3480	}
3481
3482	if (S->hasSingleExitEdge())
3483	return;
3484
3485	// PHINodes in the SCoP region's exit block are also uses to be checked.
3486	if (!S->getRegion().isTopLevelRegion()) {
3487	for (auto &Inst : *S->getRegion().getExit()) {
3488	if (!isa<PHINode>(Val: Inst))
3489	break;
3490
3491	for (auto &Op : Inst.operands())
3492	verifyUse(S, Op, LI);
3493	}
3494	}
3495	}
3496	#endif
3497
3498	void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
3499	scop.reset(p: new Scop(R, SE, LI, DT, *SD.getDetectionContext(R: &R), ORE,
3500	SD.getNextID()));
3501
3502	buildStmts(SR&: R);
3503
3504	// Create all invariant load instructions first. These are categorized as
3505	// 'synthesizable', therefore are not part of any ScopStmt but need to be
3506	// created somewhere.
3507	const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
3508	for (BasicBlock *BB : scop->getRegion().blocks()) {
3509	if (SD.isErrorBlock(BB&: *BB, R: scop->getRegion()))
3510	continue;
3511
3512	for (Instruction &Inst : *BB) {
3513	LoadInst *Load = dyn_cast<LoadInst>(Val: &Inst);
3514	if (!Load)
3515	continue;
3516
3517	if (!RIL.count(key: Load))
3518	continue;
3519
3520	// Invariant loads require a MemoryAccess to be created in some statement.
3521	// It is not important to which statement the MemoryAccess is added
3522	// because it will later be removed from the ScopStmt again. We chose the
3523	// first statement of the basic block the LoadInst is in.
3524	ArrayRef<ScopStmt *> List = scop->getStmtListFor(BB);
3525	assert(!List.empty());
3526	ScopStmt *RILStmt = List.front();
3527	buildMemoryAccess(Inst: Load, Stmt: RILStmt);
3528	}
3529	}
3530	buildAccessFunctions();
3531
3532	// In case the region does not have an exiting block we will later (during
3533	// code generation) split the exit block. This will move potential PHI nodes
3534	// from the current exit block into the new region exiting block. Hence, PHI
3535	// nodes that are at this point not part of the region will be.
3536	// To handle these PHI nodes later we will now model their operands as scalar
3537	// accesses. Note that we do not model anything in the exit block if we have
3538	// an exiting block in the region, as there will not be any splitting later.
3539	if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge()) {
3540	for (Instruction &Inst : *R.getExit()) {
3541	PHINode *PHI = dyn_cast<PHINode>(Val: &Inst);
3542	if (!PHI)
3543	break;
3544
3545	buildPHIAccesses(PHIStmt: nullptr, PHI, NonAffineSubRegion: nullptr, IsExitBlock: true);
3546	}
3547	}
3548
3549	// Create memory accesses for global reads since all arrays are now known.
3550	auto *AF = SE.getConstant(Ty: IntegerType::getInt64Ty(C&: SE.getContext()), V: 0);
3551	for (auto GlobalReadPair : GlobalReads) {
3552	ScopStmt *GlobalReadStmt = GlobalReadPair.first;
3553	Instruction *GlobalRead = GlobalReadPair.second;
3554	for (auto *BP : ArrayBasePointers)
3555	addArrayAccess(Stmt: GlobalReadStmt, MemAccInst: MemAccInst(GlobalRead), AccType: MemoryAccess::READ,
3556	BaseAddress: BP, ElementType: BP->getType(), IsAffine: false, Subscripts: {AF}, Sizes: {nullptr}, AccessValue: GlobalRead);
3557	}
3558
3559	buildInvariantEquivalenceClasses();
3560
3561	/// A map from basic blocks to their invalid domains.
3562	DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
3563
3564	if (!buildDomains(R: &R, InvalidDomainMap)) {
3565	LLVM_DEBUG(
3566	dbgs() << "Bailing-out because buildDomains encountered problems\n");
3567	return;
3568	}
3569
3570	addUserAssumptions(AC, InvalidDomainMap);
3571
3572	// Initialize the invalid domain.
3573	for (ScopStmt &Stmt : scop->Stmts)
3574	if (Stmt.isBlockStmt())
3575	Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()]);
3576	else
3577	Stmt.setInvalidDomain(InvalidDomainMap[getRegionNodeBasicBlock(
3578	RN: Stmt.getRegion()->getNode())]);
3579
3580	// Remove empty statements.
3581	// Exit early in case there are no executable statements left in this scop.
3582	scop->removeStmtNotInDomainMap();
3583	scop->simplifySCoP(AfterHoisting: false);
3584	if (scop->isEmpty()) {
3585	LLVM_DEBUG(dbgs() << "Bailing-out because SCoP is empty\n");
3586	return;
3587	}
3588
3589	// The ScopStmts now have enough information to initialize themselves.
3590	for (ScopStmt &Stmt : *scop) {
3591	collectSurroundingLoops(Stmt);
3592
3593	buildDomain(Stmt);
3594	buildAccessRelations(Stmt);
3595
3596	if (DetectReductions)
3597	checkForReductions(Stmt);
3598	}
3599
3600	// Check early for a feasible runtime context.
3601	if (!scop->hasFeasibleRuntimeContext()) {
3602	LLVM_DEBUG(dbgs() << "Bailing-out because of unfeasible context (early)\n");
3603	return;
3604	}
3605
3606	// Check early for profitability. Afterwards it cannot change anymore,
3607	// only the runtime context could become infeasible.
3608	if (!scop->isProfitable(ScalarsAreUnprofitable: UnprofitableScalarAccs)) {
3609	scop->invalidate(Kind: PROFITABLE, Loc: DebugLoc());
3610	LLVM_DEBUG(
3611	dbgs() << "Bailing-out because SCoP is not considered profitable\n");
3612	return;
3613	}
3614
3615	buildSchedule();
3616
3617	finalizeAccesses();
3618
3619	scop->realignParams();
3620	addUserContext();
3621
3622	// After the context was fully constructed, thus all our knowledge about
3623	// the parameters is in there, we add all recorded assumptions to the
3624	// assumed/invalid context.
3625	addRecordedAssumptions();
3626
3627	scop->simplifyContexts();
3628	if (!buildAliasChecks()) {
3629	LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
3630	return;
3631	}
3632
3633	hoistInvariantLoads();
3634	canonicalizeDynamicBasePtrs();
3635	verifyInvariantLoads();
3636	scop->simplifySCoP(AfterHoisting: true);
3637
3638	// Check late for a feasible runtime context because profitability did not
3639	// change.
3640	if (!scop->hasFeasibleRuntimeContext()) {
3641	LLVM_DEBUG(dbgs() << "Bailing-out because of unfeasible context (late)\n");
3642	return;
3643	}
3644
3645	#ifndef NDEBUG
3646	verifyUses(S: scop.get(), LI, DT);
3647	#endif
3648	}
3649
3650	ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AAResults &AA,
3651	const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
3652	ScopDetection &SD, ScalarEvolution &SE,
3653	OptimizationRemarkEmitter &ORE)
3654	: AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) {
3655	DebugLoc Beg, End;
3656	auto P = getBBPairForRegion(R);
3657	getDebugLocations(P, Begin&: Beg, End);
3658
3659	std::string Msg = "SCoP begins here.";
3660	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEntry", Beg, P.first)
3661	<< Msg);
3662
3663	buildScop(R&: *R, AC);
3664
3665	LLVM_DEBUG(dbgs() << *scop);
3666
3667	if (!scop->hasFeasibleRuntimeContext()) {
3668	InfeasibleScops++;
3669	Msg = "SCoP ends here but was dismissed.";
3670	LLVM_DEBUG(dbgs() << "SCoP detected but dismissed\n");
3671	RecordedAssumptions.clear();
3672	scop.reset();
3673	} else {
3674	Msg = "SCoP ends here.";
3675	++ScopFound;
3676	if (scop->getMaxLoopDepth() > 0)
3677	++RichScopFound;
3678	}
3679
3680	if (R->isTopLevelRegion())
3681	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.first)
3682	<< Msg);
3683	else
3684	ORE.emit(OptDiag&: OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.second)
3685	<< Msg);
3686	}
3687