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

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of polly/lib/Analysis/ScopBuilder.cpp