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