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