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> PollyIgnoreParamBounds(
137 "polly-ignore-parameter-bounds",
138 cl::desc(
139 "Do not add parameter bounds and do no gist simplify sets accordingly"),
140 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
141
142 static cl::opt<bool> PollyPreciseFoldAccesses(
143 "polly-precise-fold-accesses",
144 cl::desc("Fold memory accesses to model more possible delinearizations "
145 "(does not scale well)"),
146 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
147
148 bool polly::UseInstructionNames;
149
150 static cl::opt<bool, true> XUseInstructionNames(
151 "polly-use-llvm-names",
152 cl::desc("Use LLVM-IR names when deriving statement names"),
153 cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
154 cl::ZeroOrMore, cl::cat(PollyCategory));
155
156 static cl::opt<bool> PollyPrintInstructions(
157 "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
158 cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
159
160 static cl::list<std::string> IslArgs("polly-isl-arg",
161 cl::value_desc("argument"),
162 cl::desc("Option passed to ISL"),
163 cl::ZeroOrMore, 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 isl::set MemoryAccess::assumeNoOutOfBound() {
666 auto *SAI = getScopArrayInfo();
667 isl::space Space = getOriginalAccessRelationSpace().range();
668 isl::set Outside = isl::set::empty(Space);
669 for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; ++i) {
670 isl::local_space LS(Space);
671 isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
672 isl::pw_aff Zero = isl::pw_aff(LS);
673
674 isl::set DimOutside = Var.lt_set(Zero);
675 isl::pw_aff SizeE = SAI->getDimensionSizePw(i);
676 SizeE = SizeE.add_dims(isl::dim::in, Space.dim(isl::dim::set));
677 SizeE = SizeE.set_tuple_id(isl::dim::in, Space.get_tuple_id(isl::dim::set));
678 DimOutside = DimOutside.unite(SizeE.le_set(Var));
679
680 Outside = Outside.unite(DimOutside);
681 }
682
683 Outside = Outside.apply(getAccessRelation().reverse());
684 Outside = Outside.intersect(Statement->getDomain());
685 Outside = Outside.params();
686
687 // Remove divs to avoid the construction of overly complicated assumptions.
688 // Doing so increases the set of parameter combinations that are assumed to
689 // not appear. This is always save, but may make the resulting run-time check
690 // bail out more often than strictly necessary.
691 Outside = Outside.remove_divs();
692 Outside = Outside.complement();
693
694 if (!PollyPreciseInbounds)
695 Outside = Outside.gist_params(Statement->getDomain().params());
696 return Outside;
697 }
698
buildMemIntrinsicAccessRelation()699 void MemoryAccess::buildMemIntrinsicAccessRelation() {
700 assert(isMemoryIntrinsic());
701 assert(Subscripts.size() == 2 && Sizes.size() == 1);
702
703 isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
704 isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);
705
706 isl::map LengthMap;
707 if (Subscripts[1] == nullptr) {
708 LengthMap = isl::map::universe(SubscriptMap.get_space());
709 } else {
710 isl::pw_aff LengthPWA = getPwAff(Subscripts[1]);
711 LengthMap = isl::map::from_pw_aff(LengthPWA);
712 isl::space RangeSpace = LengthMap.get_space().range();
713 LengthMap = LengthMap.apply_range(isl::map::lex_gt(RangeSpace));
714 }
715 LengthMap = LengthMap.lower_bound_si(isl::dim::out, 0, 0);
716 LengthMap = LengthMap.align_params(SubscriptMap.get_space());
717 SubscriptMap = SubscriptMap.align_params(LengthMap.get_space());
718 LengthMap = LengthMap.sum(SubscriptMap);
719 AccessRelation =
720 LengthMap.set_tuple_id(isl::dim::in, getStatement()->getDomainId());
721 }
722
computeBoundsOnAccessRelation(unsigned ElementSize)723 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
724 ScalarEvolution *SE = Statement->getParent()->getSE();
725
726 auto MAI = MemAccInst(getAccessInstruction());
727 if (isa<MemIntrinsic>(MAI))
728 return;
729
730 Value *Ptr = MAI.getPointerOperand();
731 if (!Ptr || !SE->isSCEVable(Ptr->getType()))
732 return;
733
734 auto *PtrSCEV = SE->getSCEV(Ptr);
735 if (isa<SCEVCouldNotCompute>(PtrSCEV))
736 return;
737
738 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
739 if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
740 PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
741
742 const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
743 if (Range.isFullSet())
744 return;
745
746 if (Range.isUpperWrapped() || Range.isSignWrappedSet())
747 return;
748
749 bool isWrapping = Range.isSignWrappedSet();
750
751 unsigned BW = Range.getBitWidth();
752 const auto One = APInt(BW, 1);
753 const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
754 const auto UB = isWrapping ? (Range.getUpper() - One) : Range.getSignedMax();
755
756 auto Min = LB.sdiv(APInt(BW, ElementSize));
757 auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;
758
759 assert(Min.sle(Max) && "Minimum expected to be less or equal than max");
760
761 isl::map Relation = AccessRelation;
762 isl::set AccessRange = Relation.range();
763 AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
764 isl::dim::set);
765 AccessRelation = Relation.intersect_range(AccessRange);
766 }
767
foldAccessRelation()768 void MemoryAccess::foldAccessRelation() {
769 if (Sizes.size() < 2 || isa<SCEVConstant>(Sizes[1]))
770 return;
771
772 int Size = Subscripts.size();
773
774 isl::map NewAccessRelation = AccessRelation;
775
776 for (int i = Size - 2; i >= 0; --i) {
777 isl::space Space;
778 isl::map MapOne, MapTwo;
779 isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);
780
781 isl::space SpaceSize = DimSize.get_space();
782 isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);
783
784 Space = AccessRelation.get_space();
785 Space = Space.range().map_from_set();
786 Space = Space.align_params(SpaceSize);
787
788 int ParamLocation = Space.find_dim_by_id(isl::dim::param, ParamId);
789
790 MapOne = isl::map::universe(Space);
791 for (int j = 0; j < Size; ++j)
792 MapOne = MapOne.equate(isl::dim::in, j, isl::dim::out, j);
793 MapOne = MapOne.lower_bound_si(isl::dim::in, i + 1, 0);
794
795 MapTwo = isl::map::universe(Space);
796 for (int j = 0; j < Size; ++j)
797 if (j < i || j > i + 1)
798 MapTwo = MapTwo.equate(isl::dim::in, j, isl::dim::out, j);
799
800 isl::local_space LS(Space);
801 isl::constraint C;
802 C = isl::constraint::alloc_equality(LS);
803 C = C.set_constant_si(-1);
804 C = C.set_coefficient_si(isl::dim::in, i, 1);
805 C = C.set_coefficient_si(isl::dim::out, i, -1);
806 MapTwo = MapTwo.add_constraint(C);
807 C = isl::constraint::alloc_equality(LS);
808 C = C.set_coefficient_si(isl::dim::in, i + 1, 1);
809 C = C.set_coefficient_si(isl::dim::out, i + 1, -1);
810 C = C.set_coefficient_si(isl::dim::param, ParamLocation, 1);
811 MapTwo = MapTwo.add_constraint(C);
812 MapTwo = MapTwo.upper_bound_si(isl::dim::in, i + 1, -1);
813
814 MapOne = MapOne.unite(MapTwo);
815 NewAccessRelation = NewAccessRelation.apply_range(MapOne);
816 }
817
818 isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();
819 isl::space Space = Statement->getDomainSpace();
820 NewAccessRelation = NewAccessRelation.set_tuple_id(
821 isl::dim::in, Space.get_tuple_id(isl::dim::set));
822 NewAccessRelation = NewAccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
823 NewAccessRelation = NewAccessRelation.gist_domain(Statement->getDomain());
824
825 // Access dimension folding might in certain cases increase the number of
826 // disjuncts in the memory access, which can possibly complicate the generated
827 // run-time checks and can lead to costly compilation.
828 if (!PollyPreciseFoldAccesses &&
829 NewAccessRelation.n_basic_map() > AccessRelation.n_basic_map()) {
830 } else {
831 AccessRelation = NewAccessRelation;
832 }
833 }
834
buildAccessRelation(const ScopArrayInfo * SAI)835 void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
836 assert(AccessRelation.is_null() && "AccessRelation already built");
837
838 // Initialize the invalid domain which describes all iterations for which the
839 // access relation is not modeled correctly.
840 isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();
841 InvalidDomain = isl::set::empty(StmtInvalidDomain.get_space());
842
843 isl::ctx Ctx = Id.get_ctx();
844 isl::id BaseAddrId = SAI->getBasePtrId();
845
846 if (getAccessInstruction() && isa<MemIntrinsic>(getAccessInstruction())) {
847 buildMemIntrinsicAccessRelation();
848 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
849 return;
850 }
851
852 if (!isAffine()) {
853 // We overapproximate non-affine accesses with a possible access to the
854 // whole array. For read accesses it does not make a difference, if an
855 // access must or may happen. However, for write accesses it is important to
856 // differentiate between writes that must happen and writes that may happen.
857 if (AccessRelation.is_null())
858 AccessRelation = createBasicAccessMap(Statement);
859
860 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
861 return;
862 }
863
864 isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);
865 AccessRelation = isl::map::universe(Space);
866
867 for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
868 isl::pw_aff Affine = getPwAff(Subscripts[i]);
869 isl::map SubscriptMap = isl::map::from_pw_aff(Affine);
870 AccessRelation = AccessRelation.flat_range_product(SubscriptMap);
871 }
872
873 Space = Statement->getDomainSpace();
874 AccessRelation = AccessRelation.set_tuple_id(
875 isl::dim::in, Space.get_tuple_id(isl::dim::set));
876 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
877
878 AccessRelation = AccessRelation.gist_domain(Statement->getDomain());
879 }
880
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)881 MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
882 AccessType AccType, Value *BaseAddress,
883 Type *ElementType, bool Affine,
884 ArrayRef<const SCEV *> Subscripts,
885 ArrayRef<const SCEV *> Sizes, Value *AccessValue,
886 MemoryKind Kind)
887 : Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(nullptr),
888 BaseAddr(BaseAddress), ElementType(ElementType),
889 Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
890 AccessValue(AccessValue), IsAffine(Affine),
891 Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
892 NewAccessRelation(nullptr), FAD(nullptr) {
893 static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
894 const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
895
896 std::string IdName = Stmt->getBaseName() + Access;
897 Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
898 }
899
MemoryAccess(ScopStmt * Stmt,AccessType AccType,isl::map AccRel)900 MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
901 : Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
902 InvalidDomain(nullptr), AccessRelation(nullptr),
903 NewAccessRelation(AccRel), FAD(nullptr) {
904 isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);
905 auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
906 Sizes.push_back(nullptr);
907 for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
908 Sizes.push_back(SAI->getDimensionSize(i));
909 ElementType = SAI->getElementType();
910 BaseAddr = SAI->getBasePtr();
911 static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
912 const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
913
914 std::string IdName = Stmt->getBaseName() + Access;
915 Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
916 }
917
918 MemoryAccess::~MemoryAccess() = default;
919
realignParams()920 void MemoryAccess::realignParams() {
921 isl::set Ctx = Statement->getParent()->getContext();
922 InvalidDomain = InvalidDomain.gist_params(Ctx);
923 AccessRelation = AccessRelation.gist_params(Ctx);
924
925 // Predictable parameter order is required for JSON imports. Ensure alignment
926 // by explicitly calling align_params.
927 isl::space CtxSpace = Ctx.get_space();
928 InvalidDomain = InvalidDomain.align_params(CtxSpace);
929 AccessRelation = AccessRelation.align_params(CtxSpace);
930 }
931
getReductionOperatorStr() const932 const std::string MemoryAccess::getReductionOperatorStr() const {
933 return MemoryAccess::getReductionOperatorStr(getReductionType());
934 }
935
getId() const936 isl::id MemoryAccess::getId() const { return Id; }
937
operator <<(raw_ostream & OS,MemoryAccess::ReductionType RT)938 raw_ostream &polly::operator<<(raw_ostream &OS,
939 MemoryAccess::ReductionType RT) {
940 if (RT == MemoryAccess::RT_NONE)
941 OS << "NONE";
942 else
943 OS << MemoryAccess::getReductionOperatorStr(RT);
944 return OS;
945 }
946
setFortranArrayDescriptor(Value * FAD)947 void MemoryAccess::setFortranArrayDescriptor(Value *FAD) { this->FAD = FAD; }
948
print(raw_ostream & OS) const949 void MemoryAccess::print(raw_ostream &OS) const {
950 switch (AccType) {
951 case READ:
952 OS.indent(12) << "ReadAccess :=\t";
953 break;
954 case MUST_WRITE:
955 OS.indent(12) << "MustWriteAccess :=\t";
956 break;
957 case MAY_WRITE:
958 OS.indent(12) << "MayWriteAccess :=\t";
959 break;
960 }
961
962 OS << "[Reduction Type: " << getReductionType() << "] ";
963
964 if (FAD) {
965 OS << "[Fortran array descriptor: " << FAD->getName();
966 OS << "] ";
967 };
968
969 OS << "[Scalar: " << isScalarKind() << "]\n";
970 OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
971 if (hasNewAccessRelation())
972 OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
973 }
974
975 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const976 LLVM_DUMP_METHOD void MemoryAccess::dump() const { print(errs()); }
977 #endif
978
getPwAff(const SCEV * E)979 isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {
980 auto *Stmt = getStatement();
981 PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());
982 isl::set StmtDom = getStatement()->getDomain();
983 StmtDom = StmtDom.reset_tuple_id();
984 isl::set NewInvalidDom = StmtDom.intersect(PWAC.second);
985 InvalidDomain = InvalidDomain.unite(NewInvalidDom);
986 return PWAC.first;
987 }
988
989 // Create a map in the size of the provided set domain, that maps from the
990 // one element of the provided set domain to another element of the provided
991 // set domain.
992 // The mapping is limited to all points that are equal in all but the last
993 // dimension and for which the last dimension of the input is strict smaller
994 // than the last dimension of the output.
995 //
996 // getEqualAndLarger(set[i0, i1, ..., iX]):
997 //
998 // set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
999 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
1000 //
getEqualAndLarger(isl::space SetDomain)1001 static isl::map getEqualAndLarger(isl::space SetDomain) {
1002 isl::space Space = SetDomain.map_from_set();
1003 isl::map Map = isl::map::universe(Space);
1004 unsigned lastDimension = Map.dim(isl::dim::in) - 1;
1005
1006 // Set all but the last dimension to be equal for the input and output
1007 //
1008 // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
1009 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
1010 for (unsigned i = 0; i < lastDimension; ++i)
1011 Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
1012
1013 // Set the last dimension of the input to be strict smaller than the
1014 // last dimension of the output.
1015 //
1016 // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
1017 Map = Map.order_lt(isl::dim::in, lastDimension, isl::dim::out, lastDimension);
1018 return Map;
1019 }
1020
getStride(isl::map Schedule) const1021 isl::set MemoryAccess::getStride(isl::map Schedule) const {
1022 isl::map AccessRelation = getAccessRelation();
1023 isl::space Space = Schedule.get_space().range();
1024 isl::map NextScatt = getEqualAndLarger(Space);
1025
1026 Schedule = Schedule.reverse();
1027 NextScatt = NextScatt.lexmin();
1028
1029 NextScatt = NextScatt.apply_range(Schedule);
1030 NextScatt = NextScatt.apply_range(AccessRelation);
1031 NextScatt = NextScatt.apply_domain(Schedule);
1032 NextScatt = NextScatt.apply_domain(AccessRelation);
1033
1034 isl::set Deltas = NextScatt.deltas();
1035 return Deltas;
1036 }
1037
isStrideX(isl::map Schedule,int StrideWidth) const1038 bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {
1039 isl::set Stride, StrideX;
1040 bool IsStrideX;
1041
1042 Stride = getStride(Schedule);
1043 StrideX = isl::set::universe(Stride.get_space());
1044 for (unsigned i = 0; i < StrideX.dim(isl::dim::set) - 1; i++)
1045 StrideX = StrideX.fix_si(isl::dim::set, i, 0);
1046 StrideX = StrideX.fix_si(isl::dim::set, StrideX.dim(isl::dim::set) - 1,
1047 StrideWidth);
1048 IsStrideX = Stride.is_subset(StrideX);
1049
1050 return IsStrideX;
1051 }
1052
isStrideZero(isl::map Schedule) const1053 bool MemoryAccess::isStrideZero(isl::map Schedule) const {
1054 return isStrideX(Schedule, 0);
1055 }
1056
isStrideOne(isl::map Schedule) const1057 bool MemoryAccess::isStrideOne(isl::map Schedule) const {
1058 return isStrideX(Schedule, 1);
1059 }
1060
setAccessRelation(isl::map NewAccess)1061 void MemoryAccess::setAccessRelation(isl::map NewAccess) {
1062 AccessRelation = NewAccess;
1063 }
1064
setNewAccessRelation(isl::map NewAccess)1065 void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {
1066 assert(NewAccess);
1067
1068 #ifndef NDEBUG
1069 // Check domain space compatibility.
1070 isl::space NewSpace = NewAccess.get_space();
1071 isl::space NewDomainSpace = NewSpace.domain();
1072 isl::space OriginalDomainSpace = getStatement()->getDomainSpace();
1073 assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace));
1074
1075 // Reads must be executed unconditionally. Writes might be executed in a
1076 // subdomain only.
1077 if (isRead()) {
1078 // Check whether there is an access for every statement instance.
1079 isl::set StmtDomain = getStatement()->getDomain();
1080 StmtDomain =
1081 StmtDomain.intersect_params(getStatement()->getParent()->getContext());
1082 isl::set NewDomain = NewAccess.domain();
1083 assert(StmtDomain.is_subset(NewDomain) &&
1084 "Partial READ accesses not supported");
1085 }
1086
1087 isl::space NewAccessSpace = NewAccess.get_space();
1088 assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&
1089 "Must specify the array that is accessed");
1090 isl::id NewArrayId = NewAccessSpace.get_tuple_id(isl::dim::set);
1091 auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());
1092 assert(SAI && "Must set a ScopArrayInfo");
1093
1094 if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
1095 InvariantEquivClassTy *EqClass =
1096 getStatement()->getParent()->lookupInvariantEquivClass(
1097 SAI->getBasePtr());
1098 assert(EqClass &&
1099 "Access functions to indirect arrays must have an invariant and "
1100 "hoisted base pointer");
1101 }
1102
1103 // Check whether access dimensions correspond to number of dimensions of the
1104 // accesses array.
1105 auto Dims = SAI->getNumberOfDimensions();
1106 assert(NewAccessSpace.dim(isl::dim::set) == Dims &&
1107 "Access dims must match array dims");
1108 #endif
1109
1110 NewAccess = NewAccess.gist_domain(getStatement()->getDomain());
1111 NewAccessRelation = NewAccess;
1112 }
1113
isLatestPartialAccess() const1114 bool MemoryAccess::isLatestPartialAccess() const {
1115 isl::set StmtDom = getStatement()->getDomain();
1116 isl::set AccDom = getLatestAccessRelation().domain();
1117
1118 return !StmtDom.is_subset(AccDom);
1119 }
1120
1121 //===----------------------------------------------------------------------===//
1122
getSchedule() const1123 isl::map ScopStmt::getSchedule() const {
1124 isl::set Domain = getDomain();
1125 if (Domain.is_empty())
1126 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1127 auto Schedule = getParent()->getSchedule();
1128 if (!Schedule)
1129 return nullptr;
1130 Schedule = Schedule.intersect_domain(isl::union_set(Domain));
1131 if (Schedule.is_empty())
1132 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1133 isl::map M = M.from_union_map(Schedule);
1134 M = M.coalesce();
1135 M = M.gist_domain(Domain);
1136 M = M.coalesce();
1137 return M;
1138 }
1139
restrictDomain(isl::set NewDomain)1140 void ScopStmt::restrictDomain(isl::set NewDomain) {
1141 assert(NewDomain.is_subset(Domain) &&
1142 "New domain is not a subset of old domain!");
1143 Domain = NewDomain;
1144 }
1145
addAccess(MemoryAccess * Access,bool Prepend)1146 void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
1147 Instruction *AccessInst = Access->getAccessInstruction();
1148
1149 if (Access->isArrayKind()) {
1150 MemoryAccessList &MAL = InstructionToAccess[AccessInst];
1151 MAL.emplace_front(Access);
1152 } else if (Access->isValueKind() && Access->isWrite()) {
1153 Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
1154 assert(!ValueWrites.lookup(AccessVal));
1155
1156 ValueWrites[AccessVal] = Access;
1157 } else if (Access->isValueKind() && Access->isRead()) {
1158 Value *AccessVal = Access->getAccessValue();
1159 assert(!ValueReads.lookup(AccessVal));
1160
1161 ValueReads[AccessVal] = Access;
1162 } else if (Access->isAnyPHIKind() && Access->isWrite()) {
1163 PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1164 assert(!PHIWrites.lookup(PHI));
1165
1166 PHIWrites[PHI] = Access;
1167 } else if (Access->isAnyPHIKind() && Access->isRead()) {
1168 PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1169 assert(!PHIReads.lookup(PHI));
1170
1171 PHIReads[PHI] = Access;
1172 }
1173
1174 if (Prepend) {
1175 MemAccs.insert(MemAccs.begin(), Access);
1176 return;
1177 }
1178 MemAccs.push_back(Access);
1179 }
1180
realignParams()1181 void ScopStmt::realignParams() {
1182 for (MemoryAccess *MA : *this)
1183 MA->realignParams();
1184
1185 isl::set Ctx = Parent.getContext();
1186 InvalidDomain = InvalidDomain.gist_params(Ctx);
1187 Domain = Domain.gist_params(Ctx);
1188
1189 // Predictable parameter order is required for JSON imports. Ensure alignment
1190 // by explicitly calling align_params.
1191 isl::space CtxSpace = Ctx.get_space();
1192 InvalidDomain = InvalidDomain.align_params(CtxSpace);
1193 Domain = Domain.align_params(CtxSpace);
1194 }
1195
ScopStmt(Scop & parent,Region & R,StringRef Name,Loop * SurroundingLoop,std::vector<Instruction * > EntryBlockInstructions)1196 ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
1197 Loop *SurroundingLoop,
1198 std::vector<Instruction *> EntryBlockInstructions)
1199 : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
1200 Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1201 Instructions(EntryBlockInstructions) {}
1202
ScopStmt(Scop & parent,BasicBlock & bb,StringRef Name,Loop * SurroundingLoop,std::vector<Instruction * > Instructions)1203 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
1204 Loop *SurroundingLoop,
1205 std::vector<Instruction *> Instructions)
1206 : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
1207 Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1208 Instructions(Instructions) {}
1209
ScopStmt(Scop & parent,isl::map SourceRel,isl::map TargetRel,isl::set NewDomain)1210 ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
1211 isl::set NewDomain)
1212 : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain),
1213 Build(nullptr) {
1214 BaseName = getIslCompatibleName("CopyStmt_", "",
1215 std::to_string(parent.getCopyStmtsNum()));
1216 isl::id Id = isl::id::alloc(getIslCtx(), getBaseName(), this);
1217 Domain = Domain.set_tuple_id(Id);
1218 TargetRel = TargetRel.set_tuple_id(isl::dim::in, Id);
1219 auto *Access =
1220 new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
1221 parent.addAccessFunction(Access);
1222 addAccess(Access);
1223 SourceRel = SourceRel.set_tuple_id(isl::dim::in, Id);
1224 Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
1225 parent.addAccessFunction(Access);
1226 addAccess(Access);
1227 }
1228
1229 ScopStmt::~ScopStmt() = default;
1230
getDomainStr() const1231 std::string ScopStmt::getDomainStr() const { return Domain.to_str(); }
1232
getScheduleStr() const1233 std::string ScopStmt::getScheduleStr() const {
1234 auto *S = getSchedule().release();
1235 if (!S)
1236 return {};
1237 auto Str = stringFromIslObj(S);
1238 isl_map_free(S);
1239 return Str;
1240 }
1241
setInvalidDomain(isl::set ID)1242 void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
1243
getEntryBlock() const1244 BasicBlock *ScopStmt::getEntryBlock() const {
1245 if (isBlockStmt())
1246 return getBasicBlock();
1247 return getRegion()->getEntry();
1248 }
1249
getNumIterators() const1250 unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
1251
getBaseName() const1252 const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1253
getLoopForDimension(unsigned Dimension) const1254 Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
1255 return NestLoops[Dimension];
1256 }
1257
getIslCtx() const1258 isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
1259
getDomain() const1260 isl::set ScopStmt::getDomain() const { return Domain; }
1261
getDomainSpace() const1262 isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }
1263
getDomainId() const1264 isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }
1265
printInstructions(raw_ostream & OS) const1266 void ScopStmt::printInstructions(raw_ostream &OS) const {
1267 OS << "Instructions {\n";
1268
1269 for (Instruction *Inst : Instructions)
1270 OS.indent(16) << *Inst << "\n";
1271
1272 OS.indent(12) << "}\n";
1273 }
1274
print(raw_ostream & OS,bool PrintInstructions) const1275 void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
1276 OS << "\t" << getBaseName() << "\n";
1277 OS.indent(12) << "Domain :=\n";
1278
1279 if (Domain) {
1280 OS.indent(16) << getDomainStr() << ";\n";
1281 } else
1282 OS.indent(16) << "n/a\n";
1283
1284 OS.indent(12) << "Schedule :=\n";
1285
1286 if (Domain) {
1287 OS.indent(16) << getScheduleStr() << ";\n";
1288 } else
1289 OS.indent(16) << "n/a\n";
1290
1291 for (MemoryAccess *Access : MemAccs)
1292 Access->print(OS);
1293
1294 if (PrintInstructions)
1295 printInstructions(OS.indent(12));
1296 }
1297
1298 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const1299 LLVM_DUMP_METHOD void ScopStmt::dump() const { print(dbgs(), true); }
1300 #endif
1301
removeAccessData(MemoryAccess * MA)1302 void ScopStmt::removeAccessData(MemoryAccess *MA) {
1303 if (MA->isRead() && MA->isOriginalValueKind()) {
1304 bool Found = ValueReads.erase(MA->getAccessValue());
1305 (void)Found;
1306 assert(Found && "Expected access data not found");
1307 }
1308 if (MA->isWrite() && MA->isOriginalValueKind()) {
1309 bool Found = ValueWrites.erase(cast<Instruction>(MA->getAccessValue()));
1310 (void)Found;
1311 assert(Found && "Expected access data not found");
1312 }
1313 if (MA->isWrite() && MA->isOriginalAnyPHIKind()) {
1314 bool Found = PHIWrites.erase(cast<PHINode>(MA->getAccessInstruction()));
1315 (void)Found;
1316 assert(Found && "Expected access data not found");
1317 }
1318 if (MA->isRead() && MA->isOriginalAnyPHIKind()) {
1319 bool Found = PHIReads.erase(cast<PHINode>(MA->getAccessInstruction()));
1320 (void)Found;
1321 assert(Found && "Expected access data not found");
1322 }
1323 }
1324
removeMemoryAccess(MemoryAccess * MA)1325 void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {
1326 // Remove the memory accesses from this statement together with all scalar
1327 // accesses that were caused by it. MemoryKind::Value READs have no access
1328 // instruction, hence would not be removed by this function. However, it is
1329 // only used for invariant LoadInst accesses, its arguments are always affine,
1330 // hence synthesizable, and therefore there are no MemoryKind::Value READ
1331 // accesses to be removed.
1332 auto Predicate = [&](MemoryAccess *Acc) {
1333 return Acc->getAccessInstruction() == MA->getAccessInstruction();
1334 };
1335 for (auto *MA : MemAccs) {
1336 if (Predicate(MA)) {
1337 removeAccessData(MA);
1338 Parent.removeAccessData(MA);
1339 }
1340 }
1341 MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
1342 MemAccs.end());
1343 InstructionToAccess.erase(MA->getAccessInstruction());
1344 }
1345
removeSingleMemoryAccess(MemoryAccess * MA,bool AfterHoisting)1346 void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
1347 if (AfterHoisting) {
1348 auto MAIt = std::find(MemAccs.begin(), MemAccs.end(), MA);
1349 assert(MAIt != MemAccs.end());
1350 MemAccs.erase(MAIt);
1351
1352 removeAccessData(MA);
1353 Parent.removeAccessData(MA);
1354 }
1355
1356 auto It = InstructionToAccess.find(MA->getAccessInstruction());
1357 if (It != InstructionToAccess.end()) {
1358 It->second.remove(MA);
1359 if (It->second.empty())
1360 InstructionToAccess.erase(MA->getAccessInstruction());
1361 }
1362 }
1363
ensureValueRead(Value * V)1364 MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
1365 MemoryAccess *Access = lookupInputAccessOf(V);
1366 if (Access)
1367 return Access;
1368
1369 ScopArrayInfo *SAI =
1370 Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
1371 Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
1372 true, {}, {}, V, MemoryKind::Value);
1373 Parent.addAccessFunction(Access);
1374 Access->buildAccessRelation(SAI);
1375 addAccess(Access);
1376 Parent.addAccessData(Access);
1377 return Access;
1378 }
1379
operator <<(raw_ostream & OS,const ScopStmt & S)1380 raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
1381 S.print(OS, PollyPrintInstructions);
1382 return OS;
1383 }
1384
1385 //===----------------------------------------------------------------------===//
1386 /// Scop class implement
1387
setContext(isl::set NewContext)1388 void Scop::setContext(isl::set NewContext) {
1389 Context = NewContext.align_params(Context.get_space());
1390 }
1391
1392 namespace {
1393
1394 /// Remap parameter values but keep AddRecs valid wrt. invariant loads.
1395 struct SCEVSensitiveParameterRewriter
1396 : public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
1397 const ValueToValueMap &VMap;
1398
1399 public:
SCEVSensitiveParameterRewriter__anon83dc98070211::SCEVSensitiveParameterRewriter1400 SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,
1401 ScalarEvolution &SE)
1402 : SCEVRewriteVisitor(SE), VMap(VMap) {}
1403
rewrite__anon83dc98070211::SCEVSensitiveParameterRewriter1404 static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,
1405 const ValueToValueMap &VMap) {
1406 SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1407 return SSPR.visit(E);
1408 }
1409
visitAddRecExpr__anon83dc98070211::SCEVSensitiveParameterRewriter1410 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
1411 auto *Start = visit(E->getStart());
1412 auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
1413 visit(E->getStepRecurrence(SE)),
1414 E->getLoop(), SCEV::FlagAnyWrap);
1415 return SE.getAddExpr(Start, AddRec);
1416 }
1417
visitUnknown__anon83dc98070211::SCEVSensitiveParameterRewriter1418 const SCEV *visitUnknown(const SCEVUnknown *E) {
1419 if (auto *NewValue = VMap.lookup(E->getValue()))
1420 return SE.getUnknown(NewValue);
1421 return E;
1422 }
1423 };
1424
1425 /// Check whether we should remap a SCEV expression.
1426 struct SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
1427 const ValueToValueMap &VMap;
1428 bool FoundInside = false;
1429 const Scop *S;
1430
1431 public:
SCEVFindInsideScop__anon83dc98070211::SCEVFindInsideScop1432 SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,
1433 const Scop *S)
1434 : SCEVTraversal(*this), VMap(VMap), S(S) {}
1435
hasVariant__anon83dc98070211::SCEVFindInsideScop1436 static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
1437 const ValueToValueMap &VMap, const Scop *S) {
1438 SCEVFindInsideScop SFIS(VMap, SE, S);
1439 SFIS.visitAll(E);
1440 return SFIS.FoundInside;
1441 }
1442
follow__anon83dc98070211::SCEVFindInsideScop1443 bool follow(const SCEV *E) {
1444 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
1445 FoundInside |= S->getRegion().contains(AddRec->getLoop());
1446 } else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
1447 if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
1448 FoundInside |= S->getRegion().contains(I) && !VMap.count(I);
1449 }
1450 return !FoundInside;
1451 }
1452
isDone__anon83dc98070211::SCEVFindInsideScop1453 bool isDone() { return FoundInside; }
1454 };
1455 } // end anonymous namespace
1456
getRepresentingInvariantLoadSCEV(const SCEV * E) const1457 const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {
1458 // Check whether it makes sense to rewrite the SCEV. (ScalarEvolution
1459 // doesn't like addition between an AddRec and an expression that
1460 // doesn't have a dominance relationship with it.)
1461 if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))
1462 return E;
1463
1464 // Rewrite SCEV.
1465 return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);
1466 }
1467
1468 // This table of function names is used to translate parameter names in more
1469 // human-readable names. This makes it easier to interpret Polly analysis
1470 // results.
1471 StringMap<std::string> KnownNames = {
1472 {"_Z13get_global_idj", "global_id"},
1473 {"_Z12get_local_idj", "local_id"},
1474 {"_Z15get_global_sizej", "global_size"},
1475 {"_Z14get_local_sizej", "local_size"},
1476 {"_Z12get_work_dimv", "work_dim"},
1477 {"_Z17get_global_offsetj", "global_offset"},
1478 {"_Z12get_group_idj", "group_id"},
1479 {"_Z14get_num_groupsj", "num_groups"},
1480 };
1481
getCallParamName(CallInst * Call)1482 static std::string getCallParamName(CallInst *Call) {
1483 std::string Result;
1484 raw_string_ostream OS(Result);
1485 std::string Name = Call->getCalledFunction()->getName().str();
1486
1487 auto Iterator = KnownNames.find(Name);
1488 if (Iterator != KnownNames.end())
1489 Name = "__" + Iterator->getValue();
1490 OS << Name;
1491 for (auto &Operand : Call->arg_operands()) {
1492 ConstantInt *Op = cast<ConstantInt>(&Operand);
1493 OS << "_" << Op->getValue();
1494 }
1495 OS.flush();
1496 return Result;
1497 }
1498
createParameterId(const SCEV * Parameter)1499 void Scop::createParameterId(const SCEV *Parameter) {
1500 assert(Parameters.count(Parameter));
1501 assert(!ParameterIds.count(Parameter));
1502
1503 std::string ParameterName = "p_" + std::to_string(getNumParams() - 1);
1504
1505 if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1506 Value *Val = ValueParameter->getValue();
1507 CallInst *Call = dyn_cast<CallInst>(Val);
1508
1509 if (Call && isConstCall(Call)) {
1510 ParameterName = getCallParamName(Call);
1511 } else if (UseInstructionNames) {
1512 // If this parameter references a specific Value and this value has a name
1513 // we use this name as it is likely to be unique and more useful than just
1514 // a number.
1515 if (Val->hasName())
1516 ParameterName = Val->getName().str();
1517 else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1518 auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1519 if (LoadOrigin->hasName()) {
1520 ParameterName += "_loaded_from_";
1521 ParameterName +=
1522 LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1523 }
1524 }
1525 }
1526
1527 ParameterName = getIslCompatibleName("", ParameterName, "");
1528 }
1529
1530 isl::id Id = isl::id::alloc(getIslCtx(), ParameterName,
1531 const_cast<void *>((const void *)Parameter));
1532 ParameterIds[Parameter] = Id;
1533 }
1534
addParams(const ParameterSetTy & NewParameters)1535 void Scop::addParams(const ParameterSetTy &NewParameters) {
1536 for (const SCEV *Parameter : NewParameters) {
1537 // Normalize the SCEV to get the representing element for an invariant load.
1538 Parameter = extractConstantFactor(Parameter, *SE).second;
1539 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1540
1541 if (Parameters.insert(Parameter))
1542 createParameterId(Parameter);
1543 }
1544 }
1545
getIdForParam(const SCEV * Parameter) const1546 isl::id Scop::getIdForParam(const SCEV *Parameter) const {
1547 // Normalize the SCEV to get the representing element for an invariant load.
1548 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1549 return ParameterIds.lookup(Parameter);
1550 }
1551
isDominatedBy(const DominatorTree & DT,BasicBlock * BB) const1552 bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
1553 return DT.dominates(BB, getEntry());
1554 }
1555
buildContext()1556 void Scop::buildContext() {
1557 isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
1558 Context = isl::set::universe(Space);
1559 InvalidContext = isl::set::empty(Space);
1560 AssumedContext = isl::set::universe(Space);
1561 }
1562
addParameterBounds()1563 void Scop::addParameterBounds() {
1564 unsigned PDim = 0;
1565 for (auto *Parameter : Parameters) {
1566 ConstantRange SRange = SE->getSignedRange(Parameter);
1567 Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);
1568 }
1569 }
1570
getFortranArrayIds(Scop::array_range Arrays)1571 static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
1572 std::vector<isl::id> OutermostSizeIds;
1573 for (auto Array : Arrays) {
1574 // To check if an array is a Fortran array, we check if it has a isl_pw_aff
1575 // for its outermost dimension. Fortran arrays will have this since the
1576 // outermost dimension size can be picked up from their runtime description.
1577 // TODO: actually need to check if it has a FAD, but for now this works.
1578 if (Array->getNumberOfDimensions() > 0) {
1579 isl::pw_aff PwAff = Array->getDimensionSizePw(0);
1580 if (!PwAff)
1581 continue;
1582
1583 isl::id Id = PwAff.get_dim_id(isl::dim::param, 0);
1584 assert(!Id.is_null() &&
1585 "Invalid Id for PwAff expression in Fortran array");
1586 OutermostSizeIds.push_back(Id);
1587 }
1588 }
1589 return OutermostSizeIds;
1590 }
1591
1592 // The FORTRAN array size parameters are known to be non-negative.
boundFortranArrayParams(isl::set Context,Scop::array_range Arrays)1593 static isl::set boundFortranArrayParams(isl::set Context,
1594 Scop::array_range Arrays) {
1595 std::vector<isl::id> OutermostSizeIds;
1596 OutermostSizeIds = getFortranArrayIds(Arrays);
1597
1598 for (isl::id Id : OutermostSizeIds) {
1599 int dim = Context.find_dim_by_id(isl::dim::param, Id);
1600 Context = Context.lower_bound_si(isl::dim::param, dim, 0);
1601 }
1602
1603 return Context;
1604 }
1605
realignParams()1606 void Scop::realignParams() {
1607 if (PollyIgnoreParamBounds)
1608 return;
1609
1610 // Add all parameters into a common model.
1611 isl::space Space = getFullParamSpace();
1612
1613 // Align the parameters of all data structures to the model.
1614 Context = Context.align_params(Space);
1615 AssumedContext = AssumedContext.align_params(Space);
1616 InvalidContext = InvalidContext.align_params(Space);
1617
1618 // Bound the size of the fortran array dimensions.
1619 Context = boundFortranArrayParams(Context, arrays());
1620
1621 // As all parameters are known add bounds to them.
1622 addParameterBounds();
1623
1624 for (ScopStmt &Stmt : *this)
1625 Stmt.realignParams();
1626 // Simplify the schedule according to the context too.
1627 Schedule = Schedule.gist_domain_params(getContext());
1628
1629 // Predictable parameter order is required for JSON imports. Ensure alignment
1630 // by explicitly calling align_params.
1631 Schedule = Schedule.align_params(Space);
1632 }
1633
simplifyAssumptionContext(isl::set AssumptionContext,const Scop & S)1634 static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
1635 const Scop &S) {
1636 // If we have modeled all blocks in the SCoP that have side effects we can
1637 // simplify the context with the constraints that are needed for anything to
1638 // be executed at all. However, if we have error blocks in the SCoP we already
1639 // assumed some parameter combinations cannot occur and removed them from the
1640 // domains, thus we cannot use the remaining domain to simplify the
1641 // assumptions.
1642 if (!S.hasErrorBlock()) {
1643 auto DomainParameters = S.getDomains().params();
1644 AssumptionContext = AssumptionContext.gist_params(DomainParameters);
1645 }
1646
1647 AssumptionContext = AssumptionContext.gist_params(S.getContext());
1648 return AssumptionContext;
1649 }
1650
simplifyContexts()1651 void Scop::simplifyContexts() {
1652 // The parameter constraints of the iteration domains give us a set of
1653 // constraints that need to hold for all cases where at least a single
1654 // statement iteration is executed in the whole scop. We now simplify the
1655 // assumed context under the assumption that such constraints hold and at
1656 // least a single statement iteration is executed. For cases where no
1657 // statement instances are executed, the assumptions we have taken about
1658 // the executed code do not matter and can be changed.
1659 //
1660 // WARNING: This only holds if the assumptions we have taken do not reduce
1661 // the set of statement instances that are executed. Otherwise we
1662 // may run into a case where the iteration domains suggest that
1663 // for a certain set of parameter constraints no code is executed,
1664 // but in the original program some computation would have been
1665 // performed. In such a case, modifying the run-time conditions and
1666 // possibly influencing the run-time check may cause certain scops
1667 // to not be executed.
1668 //
1669 // Example:
1670 //
1671 // When delinearizing the following code:
1672 //
1673 // for (long i = 0; i < 100; i++)
1674 // for (long j = 0; j < m; j++)
1675 // A[i+p][j] = 1.0;
1676 //
1677 // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
1678 // otherwise we would access out of bound data. Now, knowing that code is
1679 // only executed for the case m >= 0, it is sufficient to assume p >= 0.
1680 AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
1681 InvalidContext = InvalidContext.align_params(getParamSpace());
1682 }
1683
getDomainConditions(const ScopStmt * Stmt) const1684 isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
1685 return getDomainConditions(Stmt->getEntryBlock());
1686 }
1687
getDomainConditions(BasicBlock * BB) const1688 isl::set Scop::getDomainConditions(BasicBlock *BB) const {
1689 auto DIt = DomainMap.find(BB);
1690 if (DIt != DomainMap.end())
1691 return DIt->getSecond();
1692
1693 auto &RI = *R.getRegionInfo();
1694 auto *BBR = RI.getRegionFor(BB);
1695 while (BBR->getEntry() == BB)
1696 BBR = BBR->getParent();
1697 return getDomainConditions(BBR->getEntry());
1698 }
1699
Scop(Region & R,ScalarEvolution & ScalarEvolution,LoopInfo & LI,DominatorTree & DT,ScopDetection::DetectionContext & DC,OptimizationRemarkEmitter & ORE,int ID)1700 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
1701 DominatorTree &DT, ScopDetection::DetectionContext &DC,
1702 OptimizationRemarkEmitter &ORE, int ID)
1703 : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
1704 R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
1705 ORE(ORE), Affinator(this, LI), ID(ID) {
1706 SmallVector<char *, 8> IslArgv;
1707 IslArgv.reserve(1 + IslArgs.size());
1708
1709 // Substitute for program name.
1710 IslArgv.push_back(const_cast<char *>("-polly-isl-arg"));
1711
1712 for (std::string &Arg : IslArgs)
1713 IslArgv.push_back(const_cast<char *>(Arg.c_str()));
1714
1715 // Abort if unknown argument is passed.
1716 // Note that "-V" (print isl version) will always call exit(0), so we cannot
1717 // avoid ISL aborting the program at this point.
1718 unsigned IslParseFlags = ISL_ARG_ALL;
1719
1720 isl_ctx_parse_options(IslCtx.get(), IslArgv.size(), IslArgv.data(),
1721 IslParseFlags);
1722
1723 if (IslOnErrorAbort)
1724 isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT);
1725 buildContext();
1726 }
1727
1728 Scop::~Scop() = default;
1729
removeFromStmtMap(ScopStmt & Stmt)1730 void Scop::removeFromStmtMap(ScopStmt &Stmt) {
1731 for (Instruction *Inst : Stmt.getInstructions())
1732 InstStmtMap.erase(Inst);
1733
1734 if (Stmt.isRegionStmt()) {
1735 for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
1736 StmtMap.erase(BB);
1737 // Skip entry basic block, as its instructions are already deleted as
1738 // part of the statement's instruction list.
1739 if (BB == Stmt.getEntryBlock())
1740 continue;
1741 for (Instruction &Inst : *BB)
1742 InstStmtMap.erase(&Inst);
1743 }
1744 } else {
1745 auto StmtMapIt = StmtMap.find(Stmt.getBasicBlock());
1746 if (StmtMapIt != StmtMap.end())
1747 StmtMapIt->second.erase(std::remove(StmtMapIt->second.begin(),
1748 StmtMapIt->second.end(), &Stmt),
1749 StmtMapIt->second.end());
1750 for (Instruction *Inst : Stmt.getInstructions())
1751 InstStmtMap.erase(Inst);
1752 }
1753 }
1754
removeStmts(std::function<bool (ScopStmt &)> ShouldDelete,bool AfterHoisting)1755 void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete,
1756 bool AfterHoisting) {
1757 for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
1758 if (!ShouldDelete(*StmtIt)) {
1759 StmtIt++;
1760 continue;
1761 }
1762
1763 // Start with removing all of the statement's accesses including erasing it
1764 // from all maps that are pointing to them.
1765 // Make a temporary copy because removing MAs invalidates the iterator.
1766 SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());
1767 for (MemoryAccess *MA : MAList)
1768 StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);
1769
1770 removeFromStmtMap(*StmtIt);
1771 StmtIt = Stmts.erase(StmtIt);
1772 }
1773 }
1774
removeStmtNotInDomainMap()1775 void Scop::removeStmtNotInDomainMap() {
1776 auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
1777 isl::set Domain = DomainMap.lookup(Stmt.getEntryBlock());
1778 if (!Domain)
1779 return true;
1780 return Domain.is_empty();
1781 };
1782 removeStmts(ShouldDelete, false);
1783 }
1784
simplifySCoP(bool AfterHoisting)1785 void Scop::simplifySCoP(bool AfterHoisting) {
1786 auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
1787 // Never delete statements that contain calls to debug functions.
1788 if (hasDebugCall(&Stmt))
1789 return false;
1790
1791 bool RemoveStmt = Stmt.isEmpty();
1792
1793 // Remove read only statements only after invariant load hoisting.
1794 if (!RemoveStmt && AfterHoisting) {
1795 bool OnlyRead = true;
1796 for (MemoryAccess *MA : Stmt) {
1797 if (MA->isRead())
1798 continue;
1799
1800 OnlyRead = false;
1801 break;
1802 }
1803
1804 RemoveStmt = OnlyRead;
1805 }
1806 return RemoveStmt;
1807 };
1808
1809 removeStmts(ShouldDelete, AfterHoisting);
1810 }
1811
lookupInvariantEquivClass(Value * Val)1812 InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {
1813 LoadInst *LInst = dyn_cast<LoadInst>(Val);
1814 if (!LInst)
1815 return nullptr;
1816
1817 if (Value *Rep = InvEquivClassVMap.lookup(LInst))
1818 LInst = cast<LoadInst>(Rep);
1819
1820 Type *Ty = LInst->getType();
1821 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
1822 for (auto &IAClass : InvariantEquivClasses) {
1823 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
1824 continue;
1825
1826 auto &MAs = IAClass.InvariantAccesses;
1827 for (auto *MA : MAs)
1828 if (MA->getAccessInstruction() == Val)
1829 return &IAClass;
1830 }
1831
1832 return nullptr;
1833 }
1834
getOrCreateScopArrayInfo(Value * BasePtr,Type * ElementType,ArrayRef<const SCEV * > Sizes,MemoryKind Kind,const char * BaseName)1835 ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
1836 ArrayRef<const SCEV *> Sizes,
1837 MemoryKind Kind,
1838 const char *BaseName) {
1839 assert((BasePtr || BaseName) &&
1840 "BasePtr and BaseName can not be nullptr at the same time.");
1841 assert(!(BasePtr && BaseName) && "BaseName is redundant.");
1842 auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
1843 : ScopArrayNameMap[BaseName];
1844 if (!SAI) {
1845 auto &DL = getFunction().getParent()->getDataLayout();
1846 SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
1847 DL, this, BaseName));
1848 ScopArrayInfoSet.insert(SAI.get());
1849 } else {
1850 SAI->updateElementType(ElementType);
1851 // In case of mismatching array sizes, we bail out by setting the run-time
1852 // context to false.
1853 if (!SAI->updateSizes(Sizes))
1854 invalidate(DELINEARIZATION, DebugLoc());
1855 }
1856 return SAI.get();
1857 }
1858
createScopArrayInfo(Type * ElementType,const std::string & BaseName,const std::vector<unsigned> & Sizes)1859 ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,
1860 const std::string &BaseName,
1861 const std::vector<unsigned> &Sizes) {
1862 auto *DimSizeType = Type::getInt64Ty(getSE()->getContext());
1863 std::vector<const SCEV *> SCEVSizes;
1864
1865 for (auto size : Sizes)
1866 if (size)
1867 SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
1868 else
1869 SCEVSizes.push_back(nullptr);
1870
1871 auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
1872 MemoryKind::Array, BaseName.c_str());
1873 return SAI;
1874 }
1875
getScopArrayInfoOrNull(Value * BasePtr,MemoryKind Kind)1876 ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind) {
1877 auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
1878 return SAI;
1879 }
1880
getScopArrayInfo(Value * BasePtr,MemoryKind Kind)1881 ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
1882 auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);
1883 assert(SAI && "No ScopArrayInfo available for this base pointer");
1884 return SAI;
1885 }
1886
getContextStr() const1887 std::string Scop::getContextStr() const { return getContext().to_str(); }
1888
getAssumedContextStr() const1889 std::string Scop::getAssumedContextStr() const {
1890 assert(AssumedContext && "Assumed context not yet built");
1891 return AssumedContext.to_str();
1892 }
1893
getInvalidContextStr() const1894 std::string Scop::getInvalidContextStr() const {
1895 return InvalidContext.to_str();
1896 }
1897
getNameStr() const1898 std::string Scop::getNameStr() const {
1899 std::string ExitName, EntryName;
1900 std::tie(EntryName, ExitName) = getEntryExitStr();
1901 return EntryName + "---" + ExitName;
1902 }
1903
getEntryExitStr() const1904 std::pair<std::string, std::string> Scop::getEntryExitStr() const {
1905 std::string ExitName, EntryName;
1906 raw_string_ostream ExitStr(ExitName);
1907 raw_string_ostream EntryStr(EntryName);
1908
1909 R.getEntry()->printAsOperand(EntryStr, false);
1910 EntryStr.str();
1911
1912 if (R.getExit()) {
1913 R.getExit()->printAsOperand(ExitStr, false);
1914 ExitStr.str();
1915 } else
1916 ExitName = "FunctionExit";
1917
1918 return std::make_pair(EntryName, ExitName);
1919 }
1920
getContext() const1921 isl::set Scop::getContext() const { return Context; }
1922
getParamSpace() const1923 isl::space Scop::getParamSpace() const { return getContext().get_space(); }
1924
getFullParamSpace() const1925 isl::space Scop::getFullParamSpace() const {
1926 std::vector<isl::id> FortranIDs;
1927 FortranIDs = getFortranArrayIds(arrays());
1928
1929 isl::space Space = isl::space::params_alloc(
1930 getIslCtx(), ParameterIds.size() + FortranIDs.size());
1931
1932 unsigned PDim = 0;
1933 for (const SCEV *Parameter : Parameters) {
1934 isl::id Id = getIdForParam(Parameter);
1935 Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
1936 }
1937
1938 for (isl::id Id : FortranIDs)
1939 Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
1940
1941 return Space;
1942 }
1943
getAssumedContext() const1944 isl::set Scop::getAssumedContext() const {
1945 assert(AssumedContext && "Assumed context not yet built");
1946 return AssumedContext;
1947 }
1948
isProfitable(bool ScalarsAreUnprofitable) const1949 bool Scop::isProfitable(bool ScalarsAreUnprofitable) const {
1950 if (PollyProcessUnprofitable)
1951 return true;
1952
1953 if (isEmpty())
1954 return false;
1955
1956 unsigned OptimizableStmtsOrLoops = 0;
1957 for (auto &Stmt : *this) {
1958 if (Stmt.getNumIterators() == 0)
1959 continue;
1960
1961 bool ContainsArrayAccs = false;
1962 bool ContainsScalarAccs = false;
1963 for (auto *MA : Stmt) {
1964 if (MA->isRead())
1965 continue;
1966 ContainsArrayAccs |= MA->isLatestArrayKind();
1967 ContainsScalarAccs |= MA->isLatestScalarKind();
1968 }
1969
1970 if (!ScalarsAreUnprofitable || (ContainsArrayAccs && !ContainsScalarAccs))
1971 OptimizableStmtsOrLoops += Stmt.getNumIterators();
1972 }
1973
1974 return OptimizableStmtsOrLoops > 1;
1975 }
1976
hasFeasibleRuntimeContext() const1977 bool Scop::hasFeasibleRuntimeContext() const {
1978 auto PositiveContext = getAssumedContext();
1979 auto NegativeContext = getInvalidContext();
1980 PositiveContext = addNonEmptyDomainConstraints(PositiveContext);
1981 // addNonEmptyDomainConstraints returns null if ScopStmts have a null domain
1982 if (!PositiveContext)
1983 return false;
1984
1985 bool IsFeasible = !(PositiveContext.is_empty() ||
1986 PositiveContext.is_subset(NegativeContext));
1987 if (!IsFeasible)
1988 return false;
1989
1990 auto DomainContext = getDomains().params();
1991 IsFeasible = !DomainContext.is_subset(NegativeContext);
1992 IsFeasible &= !getContext().is_subset(NegativeContext);
1993
1994 return IsFeasible;
1995 }
1996
addNonEmptyDomainConstraints(isl::set C) const1997 isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
1998 isl::set DomainContext = getDomains().params();
1999 return C.intersect_params(DomainContext);
2000 }
2001
lookupBasePtrAccess(MemoryAccess * MA)2002 MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
2003 Value *PointerBase = MA->getOriginalBaseAddr();
2004
2005 auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
2006 if (!PointerBaseInst)
2007 return nullptr;
2008
2009 auto *BasePtrStmt = getStmtFor(PointerBaseInst);
2010 if (!BasePtrStmt)
2011 return nullptr;
2012
2013 return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
2014 }
2015
toString(AssumptionKind Kind)2016 static std::string toString(AssumptionKind Kind) {
2017 switch (Kind) {
2018 case ALIASING:
2019 return "No-aliasing";
2020 case INBOUNDS:
2021 return "Inbounds";
2022 case WRAPPING:
2023 return "No-overflows";
2024 case UNSIGNED:
2025 return "Signed-unsigned";
2026 case COMPLEXITY:
2027 return "Low complexity";
2028 case PROFITABLE:
2029 return "Profitable";
2030 case ERRORBLOCK:
2031 return "No-error";
2032 case INFINITELOOP:
2033 return "Finite loop";
2034 case INVARIANTLOAD:
2035 return "Invariant load";
2036 case DELINEARIZATION:
2037 return "Delinearization";
2038 }
2039 llvm_unreachable("Unknown AssumptionKind!");
2040 }
2041
isEffectiveAssumption(isl::set Set,AssumptionSign Sign)2042 bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {
2043 if (Sign == AS_ASSUMPTION) {
2044 if (Context.is_subset(Set))
2045 return false;
2046
2047 if (AssumedContext.is_subset(Set))
2048 return false;
2049 } else {
2050 if (Set.is_disjoint(Context))
2051 return false;
2052
2053 if (Set.is_subset(InvalidContext))
2054 return false;
2055 }
2056 return true;
2057 }
2058
trackAssumption(AssumptionKind Kind,isl::set Set,DebugLoc Loc,AssumptionSign Sign,BasicBlock * BB)2059 bool Scop::trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
2060 AssumptionSign Sign, BasicBlock *BB) {
2061 if (PollyRemarksMinimal && !isEffectiveAssumption(Set, Sign))
2062 return false;
2063
2064 // Do never emit trivial assumptions as they only clutter the output.
2065 if (!PollyRemarksMinimal) {
2066 isl::set Univ;
2067 if (Sign == AS_ASSUMPTION)
2068 Univ = isl::set::universe(Set.get_space());
2069
2070 bool IsTrivial = (Sign == AS_RESTRICTION && Set.is_empty()) ||
2071 (Sign == AS_ASSUMPTION && Univ.is_equal(Set));
2072
2073 if (IsTrivial)
2074 return false;
2075 }
2076
2077 switch (Kind) {
2078 case ALIASING:
2079 AssumptionsAliasing++;
2080 break;
2081 case INBOUNDS:
2082 AssumptionsInbounds++;
2083 break;
2084 case WRAPPING:
2085 AssumptionsWrapping++;
2086 break;
2087 case UNSIGNED:
2088 AssumptionsUnsigned++;
2089 break;
2090 case COMPLEXITY:
2091 AssumptionsComplexity++;
2092 break;
2093 case PROFITABLE:
2094 AssumptionsUnprofitable++;
2095 break;
2096 case ERRORBLOCK:
2097 AssumptionsErrorBlock++;
2098 break;
2099 case INFINITELOOP:
2100 AssumptionsInfiniteLoop++;
2101 break;
2102 case INVARIANTLOAD:
2103 AssumptionsInvariantLoad++;
2104 break;
2105 case DELINEARIZATION:
2106 AssumptionsDelinearization++;
2107 break;
2108 }
2109
2110 auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t";
2111 std::string Msg = toString(Kind) + Suffix + Set.to_str();
2112 if (BB)
2113 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc, BB)
2114 << Msg);
2115 else
2116 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc,
2117 R.getEntry())
2118 << Msg);
2119 return true;
2120 }
2121
addAssumption(AssumptionKind Kind,isl::set Set,DebugLoc Loc,AssumptionSign Sign,BasicBlock * BB)2122 void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
2123 AssumptionSign Sign, BasicBlock *BB) {
2124 // Simplify the assumptions/restrictions first.
2125 Set = Set.gist_params(getContext());
2126
2127 if (!trackAssumption(Kind, Set, Loc, Sign, BB))
2128 return;
2129
2130 if (Sign == AS_ASSUMPTION)
2131 AssumedContext = AssumedContext.intersect(Set).coalesce();
2132 else
2133 InvalidContext = InvalidContext.unite(Set).coalesce();
2134 }
2135
invalidate(AssumptionKind Kind,DebugLoc Loc,BasicBlock * BB)2136 void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
2137 LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");
2138 addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);
2139 }
2140
getInvalidContext() const2141 isl::set Scop::getInvalidContext() const { return InvalidContext; }
2142
printContext(raw_ostream & OS) const2143 void Scop::printContext(raw_ostream &OS) const {
2144 OS << "Context:\n";
2145 OS.indent(4) << Context << "\n";
2146
2147 OS.indent(4) << "Assumed Context:\n";
2148 OS.indent(4) << AssumedContext << "\n";
2149
2150 OS.indent(4) << "Invalid Context:\n";
2151 OS.indent(4) << InvalidContext << "\n";
2152
2153 unsigned Dim = 0;
2154 for (const SCEV *Parameter : Parameters)
2155 OS.indent(4) << "p" << Dim++ << ": " << *Parameter << "\n";
2156 }
2157
printAliasAssumptions(raw_ostream & OS) const2158 void Scop::printAliasAssumptions(raw_ostream &OS) const {
2159 int noOfGroups = 0;
2160 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
2161 if (Pair.second.size() == 0)
2162 noOfGroups += 1;
2163 else
2164 noOfGroups += Pair.second.size();
2165 }
2166
2167 OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";
2168 if (MinMaxAliasGroups.empty()) {
2169 OS.indent(8) << "n/a\n";
2170 return;
2171 }
2172
2173 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
2174
2175 // If the group has no read only accesses print the write accesses.
2176 if (Pair.second.empty()) {
2177 OS.indent(8) << "[[";
2178 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
2179 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2180 << ">";
2181 }
2182 OS << " ]]\n";
2183 }
2184
2185 for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
2186 OS.indent(8) << "[[";
2187 OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
2188 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
2189 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
2190 << ">";
2191 }
2192 OS << " ]]\n";
2193 }
2194 }
2195 }
2196
printStatements(raw_ostream & OS,bool PrintInstructions) const2197 void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {
2198 OS << "Statements {\n";
2199
2200 for (const ScopStmt &Stmt : *this) {
2201 OS.indent(4);
2202 Stmt.print(OS, PrintInstructions);
2203 }
2204
2205 OS.indent(4) << "}\n";
2206 }
2207
printArrayInfo(raw_ostream & OS) const2208 void Scop::printArrayInfo(raw_ostream &OS) const {
2209 OS << "Arrays {\n";
2210
2211 for (auto &Array : arrays())
2212 Array->print(OS);
2213
2214 OS.indent(4) << "}\n";
2215
2216 OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
2217
2218 for (auto &Array : arrays())
2219 Array->print(OS, /* SizeAsPwAff */ true);
2220
2221 OS.indent(4) << "}\n";
2222 }
2223
print(raw_ostream & OS,bool PrintInstructions) const2224 void Scop::print(raw_ostream &OS, bool PrintInstructions) const {
2225 OS.indent(4) << "Function: " << getFunction().getName() << "\n";
2226 OS.indent(4) << "Region: " << getNameStr() << "\n";
2227 OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
2228 OS.indent(4) << "Invariant Accesses: {\n";
2229 for (const auto &IAClass : InvariantEquivClasses) {
2230 const auto &MAs = IAClass.InvariantAccesses;
2231 if (MAs.empty()) {
2232 OS.indent(12) << "Class Pointer: " << *IAClass.IdentifyingPointer << "\n";
2233 } else {
2234 MAs.front()->print(OS);
2235 OS.indent(12) << "Execution Context: " << IAClass.ExecutionContext
2236 << "\n";
2237 }
2238 }
2239 OS.indent(4) << "}\n";
2240 printContext(OS.indent(4));
2241 printArrayInfo(OS.indent(4));
2242 printAliasAssumptions(OS);
2243 printStatements(OS.indent(4), PrintInstructions);
2244 }
2245
2246 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const2247 LLVM_DUMP_METHOD void Scop::dump() const { print(dbgs(), true); }
2248 #endif
2249
getIslCtx() const2250 isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }
2251
getPwAff(const SCEV * E,BasicBlock * BB,bool NonNegative,RecordedAssumptionsTy * RecordedAssumptions)2252 __isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
2253 bool NonNegative,
2254 RecordedAssumptionsTy *RecordedAssumptions) {
2255 // First try to use the SCEVAffinator to generate a piecewise defined
2256 // affine function from @p E in the context of @p BB. If that tasks becomes to
2257 // complex the affinator might return a nullptr. In such a case we invalidate
2258 // the SCoP and return a dummy value. This way we do not need to add error
2259 // handling code to all users of this function.
2260 auto PWAC = Affinator.getPwAff(E, BB, RecordedAssumptions);
2261 if (PWAC.first) {
2262 // TODO: We could use a heuristic and either use:
2263 // SCEVAffinator::takeNonNegativeAssumption
2264 // or
2265 // SCEVAffinator::interpretAsUnsigned
2266 // to deal with unsigned or "NonNegative" SCEVs.
2267 if (NonNegative)
2268 Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions);
2269 return PWAC;
2270 }
2271
2272 auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
2273 invalidate(COMPLEXITY, DL, BB);
2274 return Affinator.getPwAff(SE->getZero(E->getType()), BB, RecordedAssumptions);
2275 }
2276
getDomains() const2277 isl::union_set Scop::getDomains() const {
2278 isl_space *EmptySpace = isl_space_params_alloc(getIslCtx().get(), 0);
2279 isl_union_set *Domain = isl_union_set_empty(EmptySpace);
2280
2281 for (const ScopStmt &Stmt : *this)
2282 Domain = isl_union_set_add_set(Domain, Stmt.getDomain().release());
2283
2284 return isl::manage(Domain);
2285 }
2286
getPwAffOnly(const SCEV * E,BasicBlock * BB,RecordedAssumptionsTy * RecordedAssumptions)2287 isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB,
2288 RecordedAssumptionsTy *RecordedAssumptions) {
2289 PWACtx PWAC = getPwAff(E, BB, RecordedAssumptions);
2290 return PWAC.first;
2291 }
2292
2293 isl::union_map
getAccessesOfType(std::function<bool (MemoryAccess &)> Predicate)2294 Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
2295 isl::union_map Accesses = isl::union_map::empty(getParamSpace());
2296
2297 for (ScopStmt &Stmt : *this) {
2298 for (MemoryAccess *MA : Stmt) {
2299 if (!Predicate(*MA))
2300 continue;
2301
2302 isl::set Domain = Stmt.getDomain();
2303 isl::map AccessDomain = MA->getAccessRelation();
2304 AccessDomain = AccessDomain.intersect_domain(Domain);
2305 Accesses = Accesses.add_map(AccessDomain);
2306 }
2307 }
2308
2309 return Accesses.coalesce();
2310 }
2311
getMustWrites()2312 isl::union_map Scop::getMustWrites() {
2313 return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); });
2314 }
2315
getMayWrites()2316 isl::union_map Scop::getMayWrites() {
2317 return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); });
2318 }
2319
getWrites()2320 isl::union_map Scop::getWrites() {
2321 return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); });
2322 }
2323
getReads()2324 isl::union_map Scop::getReads() {
2325 return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });
2326 }
2327
getAccesses()2328 isl::union_map Scop::getAccesses() {
2329 return getAccessesOfType([](MemoryAccess &MA) { return true; });
2330 }
2331
getAccesses(ScopArrayInfo * Array)2332 isl::union_map Scop::getAccesses(ScopArrayInfo *Array) {
2333 return getAccessesOfType(
2334 [Array](MemoryAccess &MA) { return MA.getScopArrayInfo() == Array; });
2335 }
2336
getSchedule() const2337 isl::union_map Scop::getSchedule() const {
2338 auto Tree = getScheduleTree();
2339 return Tree.get_map();
2340 }
2341
getScheduleTree() const2342 isl::schedule Scop::getScheduleTree() const {
2343 return Schedule.intersect_domain(getDomains());
2344 }
2345
setSchedule(isl::union_map NewSchedule)2346 void Scop::setSchedule(isl::union_map NewSchedule) {
2347 auto S = isl::schedule::from_domain(getDomains());
2348 Schedule = S.insert_partial_schedule(
2349 isl::multi_union_pw_aff::from_union_map(NewSchedule));
2350 ScheduleModified = true;
2351 }
2352
setScheduleTree(isl::schedule NewSchedule)2353 void Scop::setScheduleTree(isl::schedule NewSchedule) {
2354 Schedule = NewSchedule;
2355 ScheduleModified = true;
2356 }
2357
restrictDomains(isl::union_set Domain)2358 bool Scop::restrictDomains(isl::union_set Domain) {
2359 bool Changed = false;
2360 for (ScopStmt &Stmt : *this) {
2361 isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());
2362 isl::union_set NewStmtDomain = StmtDomain.intersect(Domain);
2363
2364 if (StmtDomain.is_subset(NewStmtDomain))
2365 continue;
2366
2367 Changed = true;
2368
2369 NewStmtDomain = NewStmtDomain.coalesce();
2370
2371 if (NewStmtDomain.is_empty())
2372 Stmt.restrictDomain(isl::set::empty(Stmt.getDomainSpace()));
2373 else
2374 Stmt.restrictDomain(isl::set(NewStmtDomain));
2375 }
2376 return Changed;
2377 }
2378
getSE() const2379 ScalarEvolution *Scop::getSE() const { return SE; }
2380
addScopStmt(BasicBlock * BB,StringRef Name,Loop * SurroundingLoop,std::vector<Instruction * > Instructions)2381 void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
2382 std::vector<Instruction *> Instructions) {
2383 assert(BB && "Unexpected nullptr!");
2384 Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);
2385 auto *Stmt = &Stmts.back();
2386 StmtMap[BB].push_back(Stmt);
2387 for (Instruction *Inst : Instructions) {
2388 assert(!InstStmtMap.count(Inst) &&
2389 "Unexpected statement corresponding to the instruction.");
2390 InstStmtMap[Inst] = Stmt;
2391 }
2392 }
2393
addScopStmt(Region * R,StringRef Name,Loop * SurroundingLoop,std::vector<Instruction * > Instructions)2394 void Scop::addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,
2395 std::vector<Instruction *> Instructions) {
2396 assert(R && "Unexpected nullptr!");
2397 Stmts.emplace_back(*this, *R, Name, SurroundingLoop, Instructions);
2398 auto *Stmt = &Stmts.back();
2399
2400 for (Instruction *Inst : Instructions) {
2401 assert(!InstStmtMap.count(Inst) &&
2402 "Unexpected statement corresponding to the instruction.");
2403 InstStmtMap[Inst] = Stmt;
2404 }
2405
2406 for (BasicBlock *BB : R->blocks()) {
2407 StmtMap[BB].push_back(Stmt);
2408 if (BB == R->getEntry())
2409 continue;
2410 for (Instruction &Inst : *BB) {
2411 assert(!InstStmtMap.count(&Inst) &&
2412 "Unexpected statement corresponding to the instruction.");
2413 InstStmtMap[&Inst] = Stmt;
2414 }
2415 }
2416 }
2417
addScopStmt(isl::map SourceRel,isl::map TargetRel,isl::set Domain)2418 ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,
2419 isl::set Domain) {
2420 #ifndef NDEBUG
2421 isl::set SourceDomain = SourceRel.domain();
2422 isl::set TargetDomain = TargetRel.domain();
2423 assert(Domain.is_subset(TargetDomain) &&
2424 "Target access not defined for complete statement domain");
2425 assert(Domain.is_subset(SourceDomain) &&
2426 "Source access not defined for complete statement domain");
2427 #endif
2428 Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
2429 CopyStmtsNum++;
2430 return &(Stmts.back());
2431 }
2432
getStmtListFor(BasicBlock * BB) const2433 ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
2434 auto StmtMapIt = StmtMap.find(BB);
2435 if (StmtMapIt == StmtMap.end())
2436 return {};
2437 return StmtMapIt->second;
2438 }
2439
getIncomingStmtFor(const Use & U) const2440 ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {
2441 auto *PHI = cast<PHINode>(U.getUser());
2442 BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
2443
2444 // If the value is a non-synthesizable from the incoming block, use the
2445 // statement that contains it as user statement.
2446 if (auto *IncomingInst = dyn_cast<Instruction>(U.get())) {
2447 if (IncomingInst->getParent() == IncomingBB) {
2448 if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst))
2449 return IncomingStmt;
2450 }
2451 }
2452
2453 // Otherwise, use the epilogue/last statement.
2454 return getLastStmtFor(IncomingBB);
2455 }
2456
getLastStmtFor(BasicBlock * BB) const2457 ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
2458 ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
2459 if (!StmtList.empty())
2460 return StmtList.back();
2461 return nullptr;
2462 }
2463
getStmtListFor(RegionNode * RN) const2464 ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {
2465 if (RN->isSubRegion())
2466 return getStmtListFor(RN->getNodeAs<Region>());
2467 return getStmtListFor(RN->getNodeAs<BasicBlock>());
2468 }
2469
getStmtListFor(Region * R) const2470 ArrayRef<ScopStmt *> Scop::getStmtListFor(Region *R) const {
2471 return getStmtListFor(R->getEntry());
2472 }
2473
getRelativeLoopDepth(const Loop * L) const2474 int Scop::getRelativeLoopDepth(const Loop *L) const {
2475 if (!L || !R.contains(L))
2476 return -1;
2477 // outermostLoopInRegion always returns nullptr for top level regions
2478 if (R.isTopLevelRegion()) {
2479 // LoopInfo's depths start at 1, we start at 0
2480 return L->getLoopDepth() - 1;
2481 } else {
2482 Loop *OuterLoop = R.outermostLoopInRegion(const_cast<Loop *>(L));
2483 assert(OuterLoop);
2484 return L->getLoopDepth() - OuterLoop->getLoopDepth();
2485 }
2486 }
2487
getArrayInfoByName(const std::string BaseName)2488 ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
2489 for (auto &SAI : arrays()) {
2490 if (SAI->getName() == BaseName)
2491 return SAI;
2492 }
2493 return nullptr;
2494 }
2495
addAccessData(MemoryAccess * Access)2496 void Scop::addAccessData(MemoryAccess *Access) {
2497 const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo();
2498 assert(SAI && "can only use after access relations have been constructed");
2499
2500 if (Access->isOriginalValueKind() && Access->isRead())
2501 ValueUseAccs[SAI].push_back(Access);
2502 else if (Access->isOriginalAnyPHIKind() && Access->isWrite())
2503 PHIIncomingAccs[SAI].push_back(Access);
2504 }
2505
removeAccessData(MemoryAccess * Access)2506 void Scop::removeAccessData(MemoryAccess *Access) {
2507 if (Access->isOriginalValueKind() && Access->isWrite()) {
2508 ValueDefAccs.erase(Access->getAccessValue());
2509 } else if (Access->isOriginalValueKind() && Access->isRead()) {
2510 auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];
2511 auto NewEnd = std::remove(Uses.begin(), Uses.end(), Access);
2512 Uses.erase(NewEnd, Uses.end());
2513 } else if (Access->isOriginalPHIKind() && Access->isRead()) {
2514 PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());
2515 PHIReadAccs.erase(PHI);
2516 } else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) {
2517 auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];
2518 auto NewEnd = std::remove(Incomings.begin(), Incomings.end(), Access);
2519 Incomings.erase(NewEnd, Incomings.end());
2520 }
2521 }
2522
getValueDef(const ScopArrayInfo * SAI) const2523 MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {
2524 assert(SAI->isValueKind());
2525
2526 Instruction *Val = dyn_cast<Instruction>(SAI->getBasePtr());
2527 if (!Val)
2528 return nullptr;
2529
2530 return ValueDefAccs.lookup(Val);
2531 }
2532
getValueUses(const ScopArrayInfo * SAI) const2533 ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {
2534 assert(SAI->isValueKind());
2535 auto It = ValueUseAccs.find(SAI);
2536 if (It == ValueUseAccs.end())
2537 return {};
2538 return It->second;
2539 }
2540
getPHIRead(const ScopArrayInfo * SAI) const2541 MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {
2542 assert(SAI->isPHIKind() || SAI->isExitPHIKind());
2543
2544 if (SAI->isExitPHIKind())
2545 return nullptr;
2546
2547 PHINode *PHI = cast<PHINode>(SAI->getBasePtr());
2548 return PHIReadAccs.lookup(PHI);
2549 }
2550
getPHIIncomings(const ScopArrayInfo * SAI) const2551 ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {
2552 assert(SAI->isPHIKind() || SAI->isExitPHIKind());
2553 auto It = PHIIncomingAccs.find(SAI);
2554 if (It == PHIIncomingAccs.end())
2555 return {};
2556 return It->second;
2557 }
2558
isEscaping(Instruction * Inst)2559 bool Scop::isEscaping(Instruction *Inst) {
2560 assert(contains(Inst) && "The concept of escaping makes only sense for "
2561 "values defined inside the SCoP");
2562
2563 for (Use &Use : Inst->uses()) {
2564 BasicBlock *UserBB = getUseBlock(Use);
2565 if (!contains(UserBB))
2566 return true;
2567
2568 // When the SCoP region exit needs to be simplified, PHIs in the region exit
2569 // move to a new basic block such that its incoming blocks are not in the
2570 // SCoP anymore.
2571 if (hasSingleExitEdge() && isa<PHINode>(Use.getUser()) &&
2572 isExit(cast<PHINode>(Use.getUser())->getParent()))
2573 return true;
2574 }
2575 return false;
2576 }
2577
incrementNumberOfAliasingAssumptions(unsigned step)2578 void Scop::incrementNumberOfAliasingAssumptions(unsigned step) {
2579 AssumptionsAliasing += step;
2580 }
2581
getStatistics() const2582 Scop::ScopStatistics Scop::getStatistics() const {
2583 ScopStatistics Result;
2584 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2585 auto LoopStat = ScopDetection::countBeneficialLoops(&R, *SE, *getLI(), 0);
2586
2587 int NumTotalLoops = LoopStat.NumLoops;
2588 Result.NumBoxedLoops = getBoxedLoops().size();
2589 Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;
2590
2591 for (const ScopStmt &Stmt : *this) {
2592 isl::set Domain = Stmt.getDomain().intersect_params(getContext());
2593 bool IsInLoop = Stmt.getNumIterators() >= 1;
2594 for (MemoryAccess *MA : Stmt) {
2595 if (!MA->isWrite())
2596 continue;
2597
2598 if (MA->isLatestValueKind()) {
2599 Result.NumValueWrites += 1;
2600 if (IsInLoop)
2601 Result.NumValueWritesInLoops += 1;
2602 }
2603
2604 if (MA->isLatestAnyPHIKind()) {
2605 Result.NumPHIWrites += 1;
2606 if (IsInLoop)
2607 Result.NumPHIWritesInLoops += 1;
2608 }
2609
2610 isl::set AccSet =
2611 MA->getAccessRelation().intersect_domain(Domain).range();
2612 if (AccSet.is_singleton()) {
2613 Result.NumSingletonWrites += 1;
2614 if (IsInLoop)
2615 Result.NumSingletonWritesInLoops += 1;
2616 }
2617 }
2618 }
2619 #endif
2620 return Result;
2621 }
2622
operator <<(raw_ostream & OS,const Scop & scop)2623 raw_ostream &polly::operator<<(raw_ostream &OS, const Scop &scop) {
2624 scop.print(OS, PollyPrintInstructions);
2625 return OS;
2626 }
2627
2628 //===----------------------------------------------------------------------===//
getAnalysisUsage(AnalysisUsage & AU) const2629 void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
2630 AU.addRequired<LoopInfoWrapperPass>();
2631 AU.addRequired<RegionInfoPass>();
2632 AU.addRequired<DominatorTreeWrapperPass>();
2633 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2634 AU.addRequiredTransitive<ScopDetectionWrapperPass>();
2635 AU.addRequired<AAResultsWrapperPass>();
2636 AU.addRequired<AssumptionCacheTracker>();
2637 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2638 AU.setPreservesAll();
2639 }
2640
updateLoopCountStatistic(ScopDetection::LoopStats Stats,Scop::ScopStatistics ScopStats)2641 void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
2642 Scop::ScopStatistics ScopStats) {
2643 assert(Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops);
2644
2645 NumScops++;
2646 NumLoopsInScop += Stats.NumLoops;
2647 MaxNumLoopsInScop =
2648 std::max(MaxNumLoopsInScop.getValue(), (unsigned)Stats.NumLoops);
2649
2650 if (Stats.MaxDepth == 0)
2651 NumScopsDepthZero++;
2652 else if (Stats.MaxDepth == 1)
2653 NumScopsDepthOne++;
2654 else if (Stats.MaxDepth == 2)
2655 NumScopsDepthTwo++;
2656 else if (Stats.MaxDepth == 3)
2657 NumScopsDepthThree++;
2658 else if (Stats.MaxDepth == 4)
2659 NumScopsDepthFour++;
2660 else if (Stats.MaxDepth == 5)
2661 NumScopsDepthFive++;
2662 else
2663 NumScopsDepthLarger++;
2664
2665 NumAffineLoops += ScopStats.NumAffineLoops;
2666 NumBoxedLoops += ScopStats.NumBoxedLoops;
2667
2668 NumValueWrites += ScopStats.NumValueWrites;
2669 NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
2670 NumPHIWrites += ScopStats.NumPHIWrites;
2671 NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
2672 NumSingletonWrites += ScopStats.NumSingletonWrites;
2673 NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
2674 }
2675
runOnRegion(Region * R,RGPassManager & RGM)2676 bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
2677 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2678
2679 if (!SD.isMaxRegionInScop(*R))
2680 return false;
2681
2682 Function *F = R->getEntry()->getParent();
2683 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2684 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2685 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2686 auto const &DL = F->getParent()->getDataLayout();
2687 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2688 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
2689 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2690
2691 ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
2692 S = SB.getScop(); // take ownership of scop object
2693
2694 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2695 if (S) {
2696 ScopDetection::LoopStats Stats =
2697 ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
2698 updateLoopCountStatistic(Stats, S->getStatistics());
2699 }
2700 #endif
2701
2702 return false;
2703 }
2704
print(raw_ostream & OS,const Module *) const2705 void ScopInfoRegionPass::print(raw_ostream &OS, const Module *) const {
2706 if (S)
2707 S->print(OS, PollyPrintInstructions);
2708 else
2709 OS << "Invalid Scop!\n";
2710 }
2711
2712 char ScopInfoRegionPass::ID = 0;
2713
createScopInfoRegionPassPass()2714 Pass *polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
2715
2716 INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",
2717 "Polly - Create polyhedral description of Scops", false,
2718 false);
2719 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
2720 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
2721 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
2722 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
2723 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
2724 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
2725 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
2726 INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
2727 "Polly - Create polyhedral description of Scops", false,
2728 false)
2729
2730 //===----------------------------------------------------------------------===//
ScopInfo(const DataLayout & DL,ScopDetection & SD,ScalarEvolution & SE,LoopInfo & LI,AliasAnalysis & AA,DominatorTree & DT,AssumptionCache & AC,OptimizationRemarkEmitter & ORE)2731 ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
2732 LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
2733 AssumptionCache &AC, OptimizationRemarkEmitter &ORE)
2734 : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {
2735 recompute();
2736 }
2737
recompute()2738 void ScopInfo::recompute() {
2739 RegionToScopMap.clear();
2740 /// Create polyhedral description of scops for all the valid regions of a
2741 /// function.
2742 for (auto &It : SD) {
2743 Region *R = const_cast<Region *>(It);
2744 if (!SD.isMaxRegionInScop(*R))
2745 continue;
2746
2747 ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
2748 std::unique_ptr<Scop> S = SB.getScop();
2749 if (!S)
2750 continue;
2751 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2752 ScopDetection::LoopStats Stats =
2753 ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
2754 updateLoopCountStatistic(Stats, S->getStatistics());
2755 #endif
2756 bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second;
2757 assert(Inserted && "Building Scop for the same region twice!");
2758 (void)Inserted;
2759 }
2760 }
2761
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator & Inv)2762 bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
2763 FunctionAnalysisManager::Invalidator &Inv) {
2764 // Check whether the analysis, all analyses on functions have been preserved
2765 // or anything we're holding references to is being invalidated
2766 auto PAC = PA.getChecker<ScopInfoAnalysis>();
2767 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2768 Inv.invalidate<ScopAnalysis>(F, PA) ||
2769 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
2770 Inv.invalidate<LoopAnalysis>(F, PA) ||
2771 Inv.invalidate<AAManager>(F, PA) ||
2772 Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
2773 Inv.invalidate<AssumptionAnalysis>(F, PA);
2774 }
2775
2776 AnalysisKey ScopInfoAnalysis::Key;
2777
run(Function & F,FunctionAnalysisManager & FAM)2778 ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
2779 FunctionAnalysisManager &FAM) {
2780 auto &SD = FAM.getResult<ScopAnalysis>(F);
2781 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
2782 auto &LI = FAM.getResult<LoopAnalysis>(F);
2783 auto &AA = FAM.getResult<AAManager>(F);
2784 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2785 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
2786 auto &DL = F.getParent()->getDataLayout();
2787 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2788 return {DL, SD, SE, LI, AA, DT, AC, ORE};
2789 }
2790
run(Function & F,FunctionAnalysisManager & FAM)2791 PreservedAnalyses ScopInfoPrinterPass::run(Function &F,
2792 FunctionAnalysisManager &FAM) {
2793 auto &SI = FAM.getResult<ScopInfoAnalysis>(F);
2794 // Since the legacy PM processes Scops in bottom up, we print them in reverse
2795 // order here to keep the output persistent
2796 for (auto &It : reverse(SI)) {
2797 if (It.second)
2798 It.second->print(Stream, PollyPrintInstructions);
2799 else
2800 Stream << "Invalid Scop!\n";
2801 }
2802 return PreservedAnalyses::all();
2803 }
2804
getAnalysisUsage(AnalysisUsage & AU) const2805 void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2806 AU.addRequired<LoopInfoWrapperPass>();
2807 AU.addRequired<RegionInfoPass>();
2808 AU.addRequired<DominatorTreeWrapperPass>();
2809 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2810 AU.addRequiredTransitive<ScopDetectionWrapperPass>();
2811 AU.addRequired<AAResultsWrapperPass>();
2812 AU.addRequired<AssumptionCacheTracker>();
2813 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2814 AU.setPreservesAll();
2815 }
2816
runOnFunction(Function & F)2817 bool ScopInfoWrapperPass::runOnFunction(Function &F) {
2818 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2819 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2820 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2821 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2822 auto const &DL = F.getParent()->getDataLayout();
2823 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2824 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2825 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2826
2827 Result.reset(new ScopInfo{DL, SD, SE, LI, AA, DT, AC, ORE});
2828 return false;
2829 }
2830
print(raw_ostream & OS,const Module *) const2831 void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
2832 for (auto &It : *Result) {
2833 if (It.second)
2834 It.second->print(OS, PollyPrintInstructions);
2835 else
2836 OS << "Invalid Scop!\n";
2837 }
2838 }
2839
2840 char ScopInfoWrapperPass::ID = 0;
2841
createScopInfoWrapperPassPass()2842 Pass *polly::createScopInfoWrapperPassPass() {
2843 return new ScopInfoWrapperPass();
2844 }
2845
2846 INITIALIZE_PASS_BEGIN(
2847 ScopInfoWrapperPass, "polly-function-scops",
2848 "Polly - Create polyhedral description of all Scops of a function", false,
2849 false);
2850 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
2851 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
2852 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
2853 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
2854 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
2855 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
2856 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
2857 INITIALIZE_PASS_END(
2858 ScopInfoWrapperPass, "polly-function-scops",
2859 "Polly - Create polyhedral description of all Scops of a function", false,
2860 false)
2861