Coverage Report

Created: 2019-04-25 15:07

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Analysis/ScopInfo.cpp
Line
Count
Source (jump to first uncovered line)
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/Support/Compiler.h"
59
#include "llvm/Support/Debug.h"
60
#include "llvm/Support/ErrorHandling.h"
61
#include "llvm/Support/raw_ostream.h"
62
#include "isl/aff.h"
63
#include "isl/local_space.h"
64
#include "isl/map.h"
65
#include "isl/options.h"
66
#include "isl/set.h"
67
#include <cassert>
68
69
using namespace llvm;
70
using namespace polly;
71
72
2.04k
#define DEBUG_TYPE "polly-scops"
73
74
STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.");
75
STATISTIC(AssumptionsInbounds, "Number of inbounds assumptions taken.");
76
STATISTIC(AssumptionsWrapping, "Number of wrapping assumptions taken.");
77
STATISTIC(AssumptionsUnsigned, "Number of unsigned assumptions taken.");
78
STATISTIC(AssumptionsComplexity, "Number of too complex SCoPs.");
79
STATISTIC(AssumptionsUnprofitable, "Number of unprofitable SCoPs.");
80
STATISTIC(AssumptionsErrorBlock, "Number of error block assumptions taken.");
81
STATISTIC(AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.");
82
STATISTIC(AssumptionsInvariantLoad,
83
          "Number of invariant loads assumptions taken.");
84
STATISTIC(AssumptionsDelinearization,
85
          "Number of delinearization assumptions taken.");
86
87
STATISTIC(NumScops, "Number of feasible SCoPs after ScopInfo");
88
STATISTIC(NumLoopsInScop, "Number of loops in scops");
89
STATISTIC(NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo");
90
STATISTIC(NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo");
91
92
STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");
93
STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
94
STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
95
STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
96
STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
97
STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
98
STATISTIC(NumScopsDepthLarger,
99
          "Number of scops with maximal loop depth 6 and larger");
100
STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");
101
102
STATISTIC(NumValueWrites, "Number of scalar value writes after ScopInfo");
103
STATISTIC(
104
    NumValueWritesInLoops,
105
    "Number of scalar value writes nested in affine loops after ScopInfo");
106
STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo");
107
STATISTIC(NumPHIWritesInLoops,
108
          "Number of scalar phi writes nested in affine loops after ScopInfo");
109
STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo");
110
STATISTIC(NumSingletonWritesInLoops,
111
          "Number of singleton writes nested in affine loops after ScopInfo");
112
113
// The maximal number of basic sets we allow during domain construction to
114
// be created. More complex scops will result in very high compile time and
115
// are also unlikely to result in good code
116
static int const MaxDisjunctsInDomain = 20;
117
118
// The number of disjunct in the context after which we stop to add more
119
// disjuncts. This parameter is there to avoid exponential growth in the
120
// number of disjunct when adding non-convex sets to the context.
121
static int const MaxDisjunctsInContext = 4;
122
123
// The maximal number of dimensions we allow during invariant load construction.
124
// More complex access ranges will result in very high compile time and are also
125
// unlikely to result in good code. This value is very high and should only
126
// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
127
static int const MaxDimensionsInAccessRange = 9;
128
129
static cl::opt<int>
130
    OptComputeOut("polly-analysis-computeout",
131
                  cl::desc("Bound the scop analysis by a maximal amount of "
132
                           "computational steps (0 means no bound)"),
133
                  cl::Hidden, cl::init(800000), cl::ZeroOrMore,
134
                  cl::cat(PollyCategory));
135
136
static cl::opt<bool> PollyRemarksMinimal(
137
    "polly-remarks-minimal",
138
    cl::desc("Do not emit remarks about assumptions that are known"),
139
    cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
140
141
static cl::opt<int> RunTimeChecksMaxAccessDisjuncts(
142
    "polly-rtc-max-array-disjuncts",
143
    cl::desc("The maximal number of disjunts allowed in memory accesses to "
144
             "to build RTCs."),
145
    cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
146
147
static cl::opt<unsigned> RunTimeChecksMaxParameters(
148
    "polly-rtc-max-parameters",
149
    cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
150
    cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
151
152
static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
153
    "polly-rtc-max-arrays-per-group",
154
    cl::desc("The maximal number of arrays to compare in each alias group."),
155
    cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
156
157
static cl::opt<std::string> UserContextStr(
158
    "polly-context", cl::value_desc("isl parameter set"),
159
    cl::desc("Provide additional constraints on the context parameters"),
160
    cl::init(""), cl::cat(PollyCategory));
161
162
static cl::opt<bool>
163
    IslOnErrorAbort("polly-on-isl-error-abort",
164
                    cl::desc("Abort if an isl error is encountered"),
165
                    cl::init(true), cl::cat(PollyCategory));
166
167
static cl::opt<bool> PollyPreciseInbounds(
168
    "polly-precise-inbounds",
169
    cl::desc("Take more precise inbounds assumptions (do not scale well)"),
170
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
171
172
static cl::opt<bool>
173
    PollyIgnoreInbounds("polly-ignore-inbounds",
174
                        cl::desc("Do not take inbounds assumptions at all"),
175
                        cl::Hidden, cl::init(false), cl::cat(PollyCategory));
176
177
static cl::opt<bool> PollyIgnoreParamBounds(
178
    "polly-ignore-parameter-bounds",
179
    cl::desc(
180
        "Do not add parameter bounds and do no gist simplify sets accordingly"),
181
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
182
183
static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
184
    "polly-allow-dereference-of-all-function-parameters",
185
    cl::desc(
186
        "Treat all parameters to functions that are pointers as dereferencible."
187
        " This is useful for invariant load hoisting, since we can generate"
188
        " less runtime checks. This is only valid if all pointers to functions"
189
        " are always initialized, so that Polly can choose to hoist"
190
        " their loads. "),
191
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
192
193
static cl::opt<bool> PollyPreciseFoldAccesses(
194
    "polly-precise-fold-accesses",
195
    cl::desc("Fold memory accesses to model more possible delinearizations "
196
             "(does not scale well)"),
197
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
198
199
bool polly::UseInstructionNames;
200
201
static cl::opt<bool, true> XUseInstructionNames(
202
    "polly-use-llvm-names",
203
    cl::desc("Use LLVM-IR names when deriving statement names"),
204
    cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
205
    cl::ZeroOrMore, cl::cat(PollyCategory));
206
207
static cl::opt<bool> PollyPrintInstructions(
208
    "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
209
    cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
210
211
//===----------------------------------------------------------------------===//
212
213
// Create a sequence of two schedules. Either argument may be null and is
214
// interpreted as the empty schedule. Can also return null if both schedules are
215
// empty.
216
3.92k
static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
217
3.92k
  if (!Prev)
218
2.78k
    return Succ;
219
1.14k
  if (!Succ)
220
0
    return Prev;
221
1.14k
222
1.14k
  return Prev.sequence(Succ);
223
1.14k
}
224
225
static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,
226
1.21k
                                    int dim, isl::dim type) {
227
1.21k
  isl::val V;
228
1.21k
  isl::ctx Ctx = S.get_ctx();
229
1.21k
230
1.21k
  // The upper and lower bound for a parameter value is derived either from
231
1.21k
  // the data type of the parameter or from the - possibly more restrictive -
232
1.21k
  // range metadata.
233
1.21k
  V = valFromAPInt(Ctx.get(), Range.getSignedMin(), true);
234
1.21k
  S = S.lower_bound_val(type, dim, V);
235
1.21k
  V = valFromAPInt(Ctx.get(), Range.getSignedMax(), true);
236
1.21k
  S = S.upper_bound_val(type, dim, V);
237
1.21k
238
1.21k
  if (Range.isFullSet())
239
1.14k
    return S;
240
77
241
77
  if (S.n_basic_set() > MaxDisjunctsInContext)
242
13
    return S;
243
64
244
64
  // In case of signed wrapping, we can refine the set of valid values by
245
64
  // excluding the part not covered by the wrapping range.
246
64
  if (Range.isSignWrappedSet()) {
247
7
    V = valFromAPInt(Ctx.get(), Range.getLower(), true);
248
7
    isl::set SLB = S.lower_bound_val(type, dim, V);
249
7
250
7
    V = valFromAPInt(Ctx.get(), Range.getUpper(), true);
251
7
    V = V.sub_ui(1);
252
7
    isl::set SUB = S.upper_bound_val(type, dim, V);
253
7
    S = SLB.unite(SUB);
254
7
  }
255
64
256
64
  return S;
257
64
}
258
259
1.83k
static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
260
1.83k
  LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
261
1.83k
  if (!BasePtrLI)
262
1.67k
    return nullptr;
263
155
264
155
  if (!S->contains(BasePtrLI))
265
62
    return nullptr;
266
93
267
93
  ScalarEvolution &SE = *S->getSE();
268
93
269
93
  auto *OriginBaseSCEV =
270
93
      SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
271
93
  if (!OriginBaseSCEV)
272
0
    return nullptr;
273
93
274
93
  auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
275
93
  if (!OriginBaseSCEVUnknown)
276
0
    return nullptr;
277
93
278
93
  return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
279
93
                             MemoryKind::Array);
280
93
}
281
282
ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,
283
                             ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
284
                             const DataLayout &DL, Scop *S,
285
                             const char *BaseName)
286
2.56k
    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
287
2.56k
  std::string BasePtrName =
288
2.56k
      BaseName ? 
BaseName85
289
2.56k
               : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
290
2.47k
                                      Kind == MemoryKind::PHI ? 
"__phi"228
:
""2.24k
,
291
2.47k
                                      UseInstructionNames);
292
2.56k
  Id = isl::id::alloc(Ctx, BasePtrName, this);
293
2.56k
294
2.56k
  updateSizes(Sizes);
295
2.56k
296
2.56k
  if (!BasePtr || 
Kind != MemoryKind::Array2.47k
) {
297
730
    BasePtrOriginSAI = nullptr;
298
730
    return;
299
730
  }
300
1.83k
301
1.83k
  BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
302
1.83k
  if (BasePtrOriginSAI)
303
93
    const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
304
1.83k
}
305
306
2.53k
ScopArrayInfo::~ScopArrayInfo() = default;
307
308
5.28k
isl::space ScopArrayInfo::getSpace() const {
309
5.28k
  auto Space = isl::space(Id.get_ctx(), 0, getNumberOfDimensions());
310
5.28k
  Space = Space.set_tuple_id(isl::dim::set, Id);
311
5.28k
  return Space;
312
5.28k
}
313
314
0
bool ScopArrayInfo::isReadOnly() {
315
0
  isl::union_set WriteSet = S.getWrites().range();
316
0
  isl::space Space = getSpace();
317
0
  WriteSet = WriteSet.extract_set(Space);
318
0
319
0
  return bool(WriteSet.is_empty());
320
0
}
321
322
14
bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {
323
14
  if (Array->getElementType() != getElementType())
324
1
    return false;
325
13
326
13
  if (Array->getNumberOfDimensions() != getNumberOfDimensions())
327
1
    return false;
328
12
329
24
  
for (unsigned i = 0; 12
i < getNumberOfDimensions();
i++12
)
330
13
    if (Array->getDimensionSize(i) != getDimensionSize(i))
331
1
      return false;
332
12
333
12
  
return true11
;
334
12
}
335
336
5.37k
void ScopArrayInfo::updateElementType(Type *NewElementType) {
337
5.37k
  if (NewElementType == ElementType)
338
4.19k
    return;
339
1.17k
340
1.17k
  auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType);
341
1.17k
  auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType);
342
1.17k
343
1.17k
  if (NewElementSize == OldElementSize || 
NewElementSize == 056
)
344
1.12k
    return;
345
56
346
56
  if (NewElementSize % OldElementSize == 0 && 
NewElementSize < OldElementSize28
) {
347
0
    ElementType = NewElementType;
348
56
  } else {
349
56
    auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize);
350
56
    ElementType = IntegerType::get(ElementType->getContext(), GCD);
351
56
  }
352
56
}
353
354
/// Make the ScopArrayInfo model a Fortran Array
355
10
void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
356
10
  assert(FAD && "got invalid Fortran array descriptor");
357
10
  if (this->FAD) {
358
3
    assert(this->FAD == FAD &&
359
3
           "receiving different array descriptors for same array");
360
3
    return;
361
3
  }
362
7
363
7
  assert(DimensionSizesPw.size() > 0 && !DimensionSizesPw[0]);
364
7
  assert(!this->FAD);
365
7
  this->FAD = FAD;
366
7
367
7
  isl::space Space(S.getIslCtx(), 1, 0);
368
7
369
7
  std::string param_name = getName();
370
7
  param_name += "_fortranarr_size";
371
7
  isl::id IdPwAff = isl::id::alloc(S.getIslCtx(), param_name, this);
372
7
373
7
  Space = Space.set_dim_id(isl::dim::param, 0, IdPwAff);
374
7
  isl::pw_aff PwAff =
375
7
      isl::aff::var_on_domain(isl::local_space(Space), isl::dim::param, 0);
376
7
377
7
  DimensionSizesPw[0] = PwAff;
378
7
}
379
380
bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
381
4.98k
                                bool CheckConsistency) {
382
4.98k
  int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
383
4.98k
  int ExtraDimsNew = NewSizes.size() - SharedDims;
384
4.98k
  int ExtraDimsOld = DimensionSizes.size() - SharedDims;
385
4.98k
386
4.98k
  if (CheckConsistency) {
387
6.74k
    for (int i = 0; i < SharedDims; 
i++1.76k
) {
388
1.76k
      auto *NewSize = NewSizes[i + ExtraDimsNew];
389
1.76k
      auto *KnownSize = DimensionSizes[i + ExtraDimsOld];
390
1.76k
      if (NewSize && 
KnownSize181
&&
NewSize != KnownSize175
)
391
0
        return false;
392
1.76k
    }
393
4.98k
394
4.98k
    if (DimensionSizes.size() >= NewSizes.size())
395
3.05k
      return true;
396
1.92k
  }
397
1.92k
398
1.92k
  DimensionSizes.clear();
399
1.92k
  DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
400
1.92k
                        NewSizes.end());
401
1.92k
  DimensionSizesPw.clear();
402
2.38k
  for (const SCEV *Expr : DimensionSizes) {
403
2.38k
    if (!Expr) {
404
1.84k
      DimensionSizesPw.push_back(nullptr);
405
1.84k
      continue;
406
1.84k
    }
407
539
    isl::pw_aff Size = S.getPwAffOnly(Expr);
408
539
    DimensionSizesPw.push_back(Size);
409
539
  }
410
1.92k
  return true;
411
1.92k
}
412
413
3.42k
std::string ScopArrayInfo::getName() const { return Id.get_name(); }
414
415
9.87k
int ScopArrayInfo::getElemSizeInBytes() const {
416
9.87k
  return DL.getTypeAllocSize(ElementType);
417
9.87k
}
418
419
5.31k
isl::id ScopArrayInfo::getBasePtrId() const { return Id; }
420
421
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
422
LLVM_DUMP_METHOD void ScopArrayInfo::dump() const { print(errs()); }
423
#endif
424
425
2.15k
void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
426
2.15k
  OS.indent(8) << *getElementType() << " " << getName();
427
2.15k
  unsigned u = 0;
428
2.15k
  // If this is a Fortran array, then we can print the outermost dimension
429
2.15k
  // as a isl_pw_aff even though there is no SCEV information.
430
2.15k
  bool IsOutermostSizeKnown = SizeAsPwAff && 
FAD1.07k
;
431
2.15k
432
2.15k
  if (!IsOutermostSizeKnown && 
getNumberOfDimensions() > 02.14k
&&
433
2.15k
      
!getDimensionSize(0)1.65k
) {
434
1.54k
    OS << "[*]";
435
1.54k
    u++;
436
1.54k
  }
437
2.79k
  for (; u < getNumberOfDimensions(); 
u++647
) {
438
647
    OS << "[";
439
647
440
647
    if (SizeAsPwAff) {
441
326
      isl::pw_aff Size = getDimensionSizePw(u);
442
326
      OS << " " << Size << " ";
443
326
    } else {
444
321
      OS << *getDimensionSize(u);
445
321
    }
446
647
447
647
    OS << "]";
448
647
  }
449
2.15k
450
2.15k
  OS << ";";
451
2.15k
452
2.15k
  if (BasePtrOriginSAI)
453
92
    OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
454
2.15k
455
2.15k
  OS << " // Element size " << getElemSizeInBytes() << "\n";
456
2.15k
}
457
458
const ScopArrayInfo *
459
0
ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA) {
460
0
  isl::id Id = PMA.get_tuple_id(isl::dim::out);
461
0
  assert(!Id.is_null() && "Output dimension didn't have an ID");
462
0
  return getFromId(Id);
463
0
}
464
465
1.39k
const ScopArrayInfo *ScopArrayInfo::getFromId(isl::id Id) {
466
1.39k
  void *User = Id.get_user();
467
1.39k
  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
468
1.39k
  return SAI;
469
1.39k
}
470
471
13
void MemoryAccess::wrapConstantDimensions() {
472
13
  auto *SAI = getScopArrayInfo();
473
13
  isl::space ArraySpace = SAI->getSpace();
474
13
  isl::ctx Ctx = ArraySpace.get_ctx();
475
13
  unsigned DimsArray = SAI->getNumberOfDimensions();
476
13
477
13
  isl::multi_aff DivModAff = isl::multi_aff::identity(
478
13
      ArraySpace.map_from_domain_and_range(ArraySpace));
479
13
  isl::local_space LArraySpace = isl::local_space(ArraySpace);
480
13
481
13
  // Begin with last dimension, to iteratively carry into higher dimensions.
482
30
  for (int i = DimsArray - 1; i > 0; 
i--17
) {
483
17
    auto *DimSize = SAI->getDimensionSize(i);
484
17
    auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
485
17
486
17
    // This transformation is not applicable to dimensions with dynamic size.
487
17
    if (!DimSizeCst)
488
0
      continue;
489
17
490
17
    // This transformation is not applicable to dimensions of size zero.
491
17
    if (DimSize->isZero())
492
0
      continue;
493
17
494
17
    isl::val DimSizeVal =
495
17
        valFromAPInt(Ctx.get(), DimSizeCst->getAPInt(), false);
496
17
    isl::aff Var = isl::aff::var_on_domain(LArraySpace, isl::dim::set, i);
497
17
    isl::aff PrevVar =
498
17
        isl::aff::var_on_domain(LArraySpace, isl::dim::set, i - 1);
499
17
500
17
    // Compute: index % size
501
17
    // Modulo must apply in the divide of the previous iteration, if any.
502
17
    isl::aff Modulo = Var.mod(DimSizeVal);
503
17
    Modulo = Modulo.pullback(DivModAff);
504
17
505
17
    // Compute: floor(index / size)
506
17
    isl::aff Divide = Var.div(isl::aff(LArraySpace, DimSizeVal));
507
17
    Divide = Divide.floor();
508
17
    Divide = Divide.add(PrevVar);
509
17
    Divide = Divide.pullback(DivModAff);
510
17
511
17
    // Apply Modulo and Divide.
512
17
    DivModAff = DivModAff.set_aff(i, Modulo);
513
17
    DivModAff = DivModAff.set_aff(i - 1, Divide);
514
17
  }
515
13
516
13
  // Apply all modulo/divides on the accesses.
517
13
  isl::map Relation = AccessRelation;
518
13
  Relation = Relation.apply_range(isl::map::from_multi_aff(DivModAff));
519
13
  Relation = Relation.detect_equalities();
520
13
  AccessRelation = Relation;
521
13
}
522
523
4.70k
void MemoryAccess::updateDimensionality() {
524
4.70k
  auto *SAI = getScopArrayInfo();
525
4.70k
  isl::space ArraySpace = SAI->getSpace();
526
4.70k
  isl::space AccessSpace = AccessRelation.get_space().range();
527
4.70k
  isl::ctx Ctx = ArraySpace.get_ctx();
528
4.70k
529
4.70k
  auto DimsArray = ArraySpace.dim(isl::dim::set);
530
4.70k
  auto DimsAccess = AccessSpace.dim(isl::dim::set);
531
4.70k
  auto DimsMissing = DimsArray - DimsAccess;
532
4.70k
533
4.70k
  auto *BB = getStatement()->getEntryBlock();
534
4.70k
  auto &DL = BB->getModule()->getDataLayout();
535
4.70k
  unsigned ArrayElemSize = SAI->getElemSizeInBytes();
536
4.70k
  unsigned ElemBytes = DL.getTypeAllocSize(getElementType());
537
4.70k
538
4.70k
  isl::map Map = isl::map::from_domain_and_range(
539
4.70k
      isl::set::universe(AccessSpace), isl::set::universe(ArraySpace));
540
4.70k
541
4.72k
  for (unsigned i = 0; i < DimsMissing; 
i++17
)
542
17
    Map = Map.fix_si(isl::dim::out, i, 0);
543
4.70k
544
8.63k
  for (unsigned i = DimsMissing; i < DimsArray; 
i++3.93k
)
545
3.93k
    Map = Map.equate(isl::dim::in, i - DimsMissing, isl::dim::out, i);
546
4.70k
547
4.70k
  AccessRelation = AccessRelation.apply_range(Map);
548
4.70k
549
4.70k
  // For the non delinearized arrays, divide the access function of the last
550
4.70k
  // subscript by the size of the elements in the array.
551
4.70k
  //
552
4.70k
  // A stride one array access in C expressed as A[i] is expressed in
553
4.70k
  // LLVM-IR as something like A[i * elementsize]. This hides the fact that
554
4.70k
  // two subsequent values of 'i' index two values that are stored next to
555
4.70k
  // each other in memory. By this division we make this characteristic
556
4.70k
  // obvious again. If the base pointer was accessed with offsets not divisible
557
4.70k
  // by the accesses element size, we will have chosen a smaller ArrayElemSize
558
4.70k
  // that divides the offsets of all accesses to this base pointer.
559
4.70k
  if (DimsAccess == 1) {
560
2.96k
    isl::val V = isl::val(Ctx, ArrayElemSize);
561
2.96k
    AccessRelation = AccessRelation.floordiv_val(V);
562
2.96k
  }
563
4.70k
564
4.70k
  // We currently do this only if we added at least one dimension, which means
565
4.70k
  // some dimension's indices have not been specified, an indicator that some
566
4.70k
  // index values have been added together.
567
4.70k
  // TODO: Investigate general usefulness; Effect on unit tests is to make index
568
4.70k
  // expressions more complicated.
569
4.70k
  if (DimsMissing)
570
13
    wrapConstantDimensions();
571
4.70k
572
4.70k
  if (!isAffine())
573
59
    computeBoundsOnAccessRelation(ArrayElemSize);
574
4.70k
575
4.70k
  // Introduce multi-element accesses in case the type loaded by this memory
576
4.70k
  // access is larger than the canonical element type of the array.
577
4.70k
  //
578
4.70k
  // An access ((float *)A)[i] to an array char *A is modeled as
579
4.70k
  // {[i] -> A[o] : 4 i <= o <= 4 i + 3
580
4.70k
  if (ElemBytes > ArrayElemSize) {
581
55
    assert(ElemBytes % ArrayElemSize == 0 &&
582
55
           "Loaded element size should be multiple of canonical element size");
583
55
    isl::map Map = isl::map::from_domain_and_range(
584
55
        isl::set::universe(ArraySpace), isl::set::universe(ArraySpace));
585
59
    for (unsigned i = 0; i < DimsArray - 1; 
i++4
)
586
4
      Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
587
55
588
55
    isl::constraint C;
589
55
    isl::local_space LS;
590
55
591
55
    LS = isl::local_space(Map.get_space());
592
55
    int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();
593
55
594
55
    C = isl::constraint::alloc_inequality(LS);
595
55
    C = C.set_constant_val(isl::val(Ctx, Num - 1));
596
55
    C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, 1);
597
55
    C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, -1);
598
55
    Map = Map.add_constraint(C);
599
55
600
55
    C = isl::constraint::alloc_inequality(LS);
601
55
    C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, -1);
602
55
    C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, 1);
603
55
    C = C.set_constant_val(isl::val(Ctx, 0));
604
55
    Map = Map.add_constraint(C);
605
55
    AccessRelation = AccessRelation.apply_range(Map);
606
55
  }
607
4.70k
}
608
609
const std::string
610
293
MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
611
293
  switch (RT) {
612
293
  case MemoryAccess::RT_NONE:
613
0
    llvm_unreachable("Requested a reduction operator string for a memory "
614
293
                     "access which isn't a reduction");
615
293
  case MemoryAccess::RT_ADD:
616
275
    return "+";
617
293
  case MemoryAccess::RT_MUL:
618
14
    return "*";
619
293
  case MemoryAccess::RT_BOR:
620
1
    return "|";
621
293
  case MemoryAccess::RT_BXOR:
622
2
    return "^";
623
293
  case MemoryAccess::RT_BAND:
624
1
    return "&";
625
0
  }
626
0
  llvm_unreachable("Unknown reduction type");
627
0
}
628
629
23.4k
const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const {
630
23.4k
  isl::id ArrayId = getArrayId();
631
23.4k
  void *User = ArrayId.get_user();
632
23.4k
  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
633
23.4k
  return SAI;
634
23.4k
}
635
636
3.04k
const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {
637
3.04k
  isl::id ArrayId = getLatestArrayId();
638
3.04k
  void *User = ArrayId.get_user();
639
3.04k
  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
640
3.04k
  return SAI;
641
3.04k
}
642
643
26.4k
isl::id MemoryAccess::getOriginalArrayId() const {
644
26.4k
  return AccessRelation.get_tuple_id(isl::dim::out);
645
26.4k
}
646
647
3.04k
isl::id MemoryAccess::getLatestArrayId() const {
648
3.04k
  if (!hasNewAccessRelation())
649
2.74k
    return getOriginalArrayId();
650
294
  return NewAccessRelation.get_tuple_id(isl::dim::out);
651
294
}
652
653
336
isl::map MemoryAccess::getAddressFunction() const {
654
336
  return getAccessRelation().lexmin();
655
336
}
656
657
isl::pw_multi_aff
658
228
MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule) const {
659
228
  isl::map Schedule, ScheduledAccRel;
660
228
  isl::union_set UDomain;
661
228
662
228
  UDomain = getStatement()->getDomain();
663
228
  USchedule = USchedule.intersect_domain(UDomain);
664
228
  Schedule = isl::map::from_union_map(USchedule);
665
228
  ScheduledAccRel = getAddressFunction().apply_domain(Schedule);
666
228
  return isl::pw_multi_aff::from_map(ScheduledAccRel);
667
228
}
668
669
17.2k
isl::map MemoryAccess::getOriginalAccessRelation() const {
670
17.2k
  return AccessRelation;
671
17.2k
}
672
673
2.33k
std::string MemoryAccess::getOriginalAccessRelationStr() const {
674
2.33k
  return AccessRelation.to_str();
675
2.33k
}
676
677
4.61k
isl::space MemoryAccess::getOriginalAccessRelationSpace() const {
678
4.61k
  return AccessRelation.get_space();
679
4.61k
}
680
681
535
isl::map MemoryAccess::getNewAccessRelation() const {
682
535
  return NewAccessRelation;
683
535
}
684
685
428
std::string MemoryAccess::getNewAccessRelationStr() const {
686
428
  return NewAccessRelation.to_str();
687
428
}
688
689
0
std::string MemoryAccess::getAccessRelationStr() const {
690
0
  return getAccessRelation().to_str();
691
0
}
692
693
60
isl::basic_map MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
694
60
  isl::space Space = isl::space(Statement->getIslCtx(), 0, 1);
695
60
  Space = Space.align_params(Statement->getDomainSpace());
696
60
697
60
  return isl::basic_map::from_domain_and_range(
698
60
      isl::basic_set::universe(Statement->getDomainSpace()),
699
60
      isl::basic_set::universe(Space));
700
60
}
701
702
// Formalize no out-of-bound access assumption
703
//
704
// When delinearizing array accesses we optimistically assume that the
705
// delinearized accesses do not access out of bound locations (the subscript
706
// expression of each array evaluates for each statement instance that is
707
// executed to a value that is larger than zero and strictly smaller than the
708
// size of the corresponding dimension). The only exception is the outermost
709
// dimension for which we do not need to assume any upper bound.  At this point
710
// we formalize this assumption to ensure that at code generation time the
711
// relevant run-time checks can be generated.
712
//
713
// To find the set of constraints necessary to avoid out of bound accesses, we
714
// first build the set of data locations that are not within array bounds. We
715
// then apply the reverse access relation to obtain the set of iterations that
716
// may contain invalid accesses and reduce this set of iterations to the ones
717
// that are actually executed by intersecting them with the domain of the
718
// statement. If we now project out all loop dimensions, we obtain a set of
719
// parameters that may cause statement instances to be executed that may
720
// possibly yield out of bound memory accesses. The complement of these
721
// constraints is the set of constraints that needs to be assumed to ensure such
722
// statement instances are never executed.
723
4.70k
void MemoryAccess::assumeNoOutOfBound() {
724
4.70k
  if (PollyIgnoreInbounds)
725
93
    return;
726
4.61k
  auto *SAI = getScopArrayInfo();
727
4.61k
  isl::space Space = getOriginalAccessRelationSpace().range();
728
4.61k
  isl::set Outside = isl::set::empty(Space);
729
5.17k
  for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; 
++i555
) {
730
555
    isl::local_space LS(Space);
731
555
    isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
732
555
    isl::pw_aff Zero = isl::pw_aff(LS);
733
555
734
555
    isl::set DimOutside = Var.lt_set(Zero);
735
555
    isl::pw_aff SizeE = SAI->getDimensionSizePw(i);
736
555
    SizeE = SizeE.add_dims(isl::dim::in, Space.dim(isl::dim::set));
737
555
    SizeE = SizeE.set_tuple_id(isl::dim::in, Space.get_tuple_id(isl::dim::set));
738
555
    DimOutside = DimOutside.unite(SizeE.le_set(Var));
739
555
740
555
    Outside = Outside.unite(DimOutside);
741
555
  }
742
4.61k
743
4.61k
  Outside = Outside.apply(getAccessRelation().reverse());
744
4.61k
  Outside = Outside.intersect(Statement->getDomain());
745
4.61k
  Outside = Outside.params();
746
4.61k
747
4.61k
  // Remove divs to avoid the construction of overly complicated assumptions.
748
4.61k
  // Doing so increases the set of parameter combinations that are assumed to
749
4.61k
  // not appear. This is always save, but may make the resulting run-time check
750
4.61k
  // bail out more often than strictly necessary.
751
4.61k
  Outside = Outside.remove_divs();
752
4.61k
  Outside = Outside.complement();
753
4.61k
  const auto &Loc = getAccessInstruction()
754
4.61k
                        ? 
getAccessInstruction()->getDebugLoc()4.26k
755
4.61k
                        : 
DebugLoc()348
;
756
4.61k
  if (!PollyPreciseInbounds)
757
4.60k
    Outside = Outside.gist_params(Statement->getDomain().params());
758
4.61k
  Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
759
4.61k
                                           AS_ASSUMPTION);
760
4.61k
}
761
762
24
void MemoryAccess::buildMemIntrinsicAccessRelation() {
763
24
  assert(isMemoryIntrinsic());
764
24
  assert(Subscripts.size() == 2 && Sizes.size() == 1);
765
24
766
24
  isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
767
24
  isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);
768
24
769
24
  isl::map LengthMap;
770
24
  if (Subscripts[1] == nullptr) {
771
0
    LengthMap = isl::map::universe(SubscriptMap.get_space());
772
24
  } else {
773
24
    isl::pw_aff LengthPWA = getPwAff(Subscripts[1]);
774
24
    LengthMap = isl::map::from_pw_aff(LengthPWA);
775
24
    isl::space RangeSpace = LengthMap.get_space().range();
776
24
    LengthMap = LengthMap.apply_range(isl::map::lex_gt(RangeSpace));
777
24
  }
778
24
  LengthMap = LengthMap.lower_bound_si(isl::dim::out, 0, 0);
779
24
  LengthMap = LengthMap.align_params(SubscriptMap.get_space());
780
24
  SubscriptMap = SubscriptMap.align_params(LengthMap.get_space());
781
24
  LengthMap = LengthMap.sum(SubscriptMap);
782
24
  AccessRelation =
783
24
      LengthMap.set_tuple_id(isl::dim::in, getStatement()->getDomainId());
784
24
}
785
786
59
void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
787
59
  ScalarEvolution *SE = Statement->getParent()->getSE();
788
59
789
59
  auto MAI = MemAccInst(getAccessInstruction());
790
59
  if (isa<MemIntrinsic>(MAI))
791
0
    return;
792
59
793
59
  Value *Ptr = MAI.getPointerOperand();
794
59
  if (!Ptr || 
!SE->isSCEVable(Ptr->getType())37
)
795
22
    return;
796
37
797
37
  auto *PtrSCEV = SE->getSCEV(Ptr);
798
37
  if (isa<SCEVCouldNotCompute>(PtrSCEV))
799
0
    return;
800
37
801
37
  auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
802
37
  if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
803
37
    PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
804
37
805
37
  const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
806
37
  if (Range.isFullSet())
807
0
    return;
808
37
809
37
  if (Range.isUpperWrapped() || 
Range.isSignWrappedSet()13
)
810
26
    return;
811
11
812
11
  bool isWrapping = Range.isSignWrappedSet();
813
11
814
11
  unsigned BW = Range.getBitWidth();
815
11
  const auto One = APInt(BW, 1);
816
11
  const auto LB = isWrapping ? 
Range.getLower()0
: Range.getSignedMin();
817
11
  const auto UB = isWrapping ? 
(Range.getUpper() - One)0
: Range.getSignedMax();
818
11
819
11
  auto Min = LB.sdiv(APInt(BW, ElementSize));
820
11
  auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;
821
11
822
11
  assert(Min.sle(Max) && "Minimum expected to be less or equal than max");
823
11
824
11
  isl::map Relation = AccessRelation;
825
11
  isl::set AccessRange = Relation.range();
826
11
  AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
827
11
                                    isl::dim::set);
828
11
  AccessRelation = Relation.intersect_range(AccessRange);
829
11
}
830
831
4.70k
void MemoryAccess::foldAccessRelation() {
832
4.70k
  if (Sizes.size() < 2 || 
isa<SCEVConstant>(Sizes[1])423
)
833
4.53k
    return;
834
177
835
177
  int Size = Subscripts.size();
836
177
837
177
  isl::map NewAccessRelation = AccessRelation;
838
177
839
450
  for (int i = Size - 2; i >= 0; 
--i273
) {
840
273
    isl::space Space;
841
273
    isl::map MapOne, MapTwo;
842
273
    isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);
843
273
844
273
    isl::space SpaceSize = DimSize.get_space();
845
273
    isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);
846
273
847
273
    Space = AccessRelation.get_space();
848
273
    Space = Space.range().map_from_set();
849
273
    Space = Space.align_params(SpaceSize);
850
273
851
273
    int ParamLocation = Space.find_dim_by_id(isl::dim::param, ParamId);
852
273
853
273
    MapOne = isl::map::universe(Space);
854
1.04k
    for (int j = 0; j < Size; 
++j774
)
855
774
      MapOne = MapOne.equate(isl::dim::in, j, isl::dim::out, j);
856
273
    MapOne = MapOne.lower_bound_si(isl::dim::in, i + 1, 0);
857
273
858
273
    MapTwo = isl::map::universe(Space);
859
1.04k
    for (int j = 0; j < Size; 
++j774
)
860
774
      if (j < i || 
j > i + 1660
)
861
228
        MapTwo = MapTwo.equate(isl::dim::in, j, isl::dim::out, j);
862
273
863
273
    isl::local_space LS(Space);
864
273
    isl::constraint C;
865
273
    C = isl::constraint::alloc_equality(LS);
866
273
    C = C.set_constant_si(-1);
867
273
    C = C.set_coefficient_si(isl::dim::in, i, 1);
868
273
    C = C.set_coefficient_si(isl::dim::out, i, -1);
869
273
    MapTwo = MapTwo.add_constraint(C);
870
273
    C = isl::constraint::alloc_equality(LS);
871
273
    C = C.set_coefficient_si(isl::dim::in, i + 1, 1);
872
273
    C = C.set_coefficient_si(isl::dim::out, i + 1, -1);
873
273
    C = C.set_coefficient_si(isl::dim::param, ParamLocation, 1);
874
273
    MapTwo = MapTwo.add_constraint(C);
875
273
    MapTwo = MapTwo.upper_bound_si(isl::dim::in, i + 1, -1);
876
273
877
273
    MapOne = MapOne.unite(MapTwo);
878
273
    NewAccessRelation = NewAccessRelation.apply_range(MapOne);
879
273
  }
880
177
881
177
  isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();
882
177
  isl::space Space = Statement->getDomainSpace();
883
177
  NewAccessRelation = NewAccessRelation.set_tuple_id(
884
177
      isl::dim::in, Space.get_tuple_id(isl::dim::set));
885
177
  NewAccessRelation = NewAccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
886
177
  NewAccessRelation = NewAccessRelation.gist_domain(Statement->getDomain());
887
177
888
177
  // Access dimension folding might in certain cases increase the number of
889
177
  // disjuncts in the memory access, which can possibly complicate the generated
890
177
  // run-time checks and can lead to costly compilation.
891
177
  if (!PollyPreciseFoldAccesses &&
892
177
      
NewAccessRelation.n_basic_map() > AccessRelation.n_basic_map()170
) {
893
171
  } else {
894
171
    AccessRelation = NewAccessRelation;
895
171
  }
896
177
}
897
898
/// Check if @p Expr is divisible by @p Size.
899
6.73k
static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
900
6.73k
  assert(Size != 0);
901
6.73k
  if (Size == 1)
902
141
    return true;
903
6.59k
904
6.59k
  // Only one factor needs to be divisible.
905
6.59k
  if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
906
394
    for (auto *FactorExpr : MulExpr->operands())
907
394
      if (isDivisible(FactorExpr, Size, SE))
908
394
        return true;
909
394
    
return false0
;
910
6.19k
  }
911
6.19k
912
6.19k
  // For other n-ary expressions (Add, AddRec, Max,...) all operands need
913
6.19k
  // to be divisible.
914
6.19k
  if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
915
1.68k
    for (auto *OpExpr : NAryExpr->operands())
916
3.38k
      if (!isDivisible(OpExpr, Size, SE))
917
0
        return false;
918
1.68k
    return true;
919
4.51k
  }
920
4.51k
921
4.51k
  auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
922
4.51k
  auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
923
4.51k
  auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
924
4.51k
  return MulSCEV == Expr;
925
4.51k
}
926
927
4.75k
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
928
4.75k
  assert(AccessRelation.is_null() && "AccessRelation already built");
929
4.75k
930
4.75k
  // Initialize the invalid domain which describes all iterations for which the
931
4.75k
  // access relation is not modeled correctly.
932
4.75k
  isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();
933
4.75k
  InvalidDomain = isl::set::empty(StmtInvalidDomain.get_space());
934
4.75k
935
4.75k
  isl::ctx Ctx = Id.get_ctx();
936
4.75k
  isl::id BaseAddrId = SAI->getBasePtrId();
937
4.75k
938
4.75k
  if (getAccessInstruction() && 
isa<MemIntrinsic>(getAccessInstruction())4.40k
) {
939
24
    buildMemIntrinsicAccessRelation();
940
24
    AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
941
24
    return;
942
24
  }
943
4.73k
944
4.73k
  if (!isAffine()) {
945
60
    // We overapproximate non-affine accesses with a possible access to the
946
60
    // whole array. For read accesses it does not make a difference, if an
947
60
    // access must or may happen. However, for write accesses it is important to
948
60
    // differentiate between writes that must happen and writes that may happen.
949
60
    if (AccessRelation.is_null())
950
60
      AccessRelation = createBasicAccessMap(Statement);
951
60
952
60
    AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
953
60
    return;
954
60
  }
955
4.67k
956
4.67k
  isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);
957
4.67k
  AccessRelation = isl::map::universe(Space);
958
4.67k
959
8.55k
  for (int i = 0, Size = Subscripts.size(); i < Size; 
++i3.88k
) {
960
3.88k
    isl::pw_aff Affine = getPwAff(Subscripts[i]);
961
3.88k
    isl::map SubscriptMap = isl::map::from_pw_aff(Affine);
962
3.88k
    AccessRelation = AccessRelation.flat_range_product(SubscriptMap);
963
3.88k
  }
964
4.67k
965
4.67k
  Space = Statement->getDomainSpace();
966
4.67k
  AccessRelation = AccessRelation.set_tuple_id(
967
4.67k
      isl::dim::in, Space.get_tuple_id(isl::dim::set));
968
4.67k
  AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
969
4.67k
970
4.67k
  AccessRelation = AccessRelation.gist_domain(Statement->getDomain());
971
4.67k
}
972
973
MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
974
                           AccessType AccType, Value *BaseAddress,
975
                           Type *ElementType, bool Affine,
976
                           ArrayRef<const SCEV *> Subscripts,
977
                           ArrayRef<const SCEV *> Sizes, Value *AccessValue,
978
                           MemoryKind Kind)
979
    : Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(nullptr),
980
      BaseAddr(BaseAddress), ElementType(ElementType),
981
      Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
982
      AccessValue(AccessValue), IsAffine(Affine),
983
      Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
984
5.08k
      NewAccessRelation(nullptr), FAD(nullptr) {
985
5.08k
  static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
986
5.08k
  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
987
5.08k
988
5.08k
  std::string IdName = Stmt->getBaseName() + Access;
989
5.08k
  Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
990
5.08k
}
991
992
MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
993
    : Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
994
      InvalidDomain(nullptr), AccessRelation(nullptr),
995
48
      NewAccessRelation(AccRel), FAD(nullptr) {
996
48
  isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);
997
48
  auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
998
48
  Sizes.push_back(nullptr);
999
120
  for (unsigned i = 1; i < SAI->getNumberOfDimensions(); 
i++72
)
1000
72
    Sizes.push_back(SAI->getDimensionSize(i));
1001
48
  ElementType = SAI->getElementType();
1002
48
  BaseAddr = SAI->getBasePtr();
1003
48
  static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
1004
48
  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
1005
48
1006
48
  std::string IdName = Stmt->getBaseName() + Access;
1007
48
  Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
1008
48
}
1009
1010
5.06k
MemoryAccess::~MemoryAccess() = default;
1011
1012
4.70k
void MemoryAccess::realignParams() {
1013
4.70k
  isl::set Ctx = Statement->getParent()->getContext();
1014
4.70k
  InvalidDomain = InvalidDomain.gist_params(Ctx);
1015
4.70k
  AccessRelation = AccessRelation.gist_params(Ctx);
1016
4.70k
}
1017
1018
0
const std::string MemoryAccess::getReductionOperatorStr() const {
1019
0
  return MemoryAccess::getReductionOperatorStr(getReductionType());
1020
0
}
1021
1022
1.89k
isl::id MemoryAccess::getId() const { return Id; }
1023
1024
raw_ostream &polly::operator<<(raw_ostream &OS,
1025
2.33k
                               MemoryAccess::ReductionType RT) {
1026
2.33k
  if (RT == MemoryAccess::RT_NONE)
1027
2.06k
    OS << "NONE";
1028
264
  else
1029
264
    OS << MemoryAccess::getReductionOperatorStr(RT);
1030
2.33k
  return OS;
1031
2.33k
}
1032
1033
10
void MemoryAccess::setFortranArrayDescriptor(Value *FAD) { this->FAD = FAD; }
1034
1035
2.33k
void MemoryAccess::print(raw_ostream &OS) const {
1036
2.33k
  switch (AccType) {
1037
2.33k
  case READ:
1038
1.07k
    OS.indent(12) << "ReadAccess :=\t";
1039
1.07k
    break;
1040
2.33k
  case MUST_WRITE:
1041
1.21k
    OS.indent(12) << "MustWriteAccess :=\t";
1042
1.21k
    break;
1043
2.33k
  case MAY_WRITE:
1044
43
    OS.indent(12) << "MayWriteAccess :=\t";
1045
43
    break;
1046
2.33k
  }
1047
2.33k
1048
2.33k
  OS << "[Reduction Type: " << getReductionType() << "] ";
1049
2.33k
1050
2.33k
  if (FAD) {
1051
8
    OS << "[Fortran array descriptor: " << FAD->getName();
1052
8
    OS << "] ";
1053
8
  };
1054
2.33k
1055
2.33k
  OS << "[Scalar: " << isScalarKind() << "]\n";
1056
2.33k
  OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
1057
2.33k
  if (hasNewAccessRelation())
1058
428
    OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
1059
2.33k
}
1060
1061
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1062
LLVM_DUMP_METHOD void MemoryAccess::dump() const { print(errs()); }
1063
#endif
1064
1065
4.20k
isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {
1066
4.20k
  auto *Stmt = getStatement();
1067
4.20k
  PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());
1068
4.20k
  isl::set StmtDom = getStatement()->getDomain();
1069
4.20k
  StmtDom = StmtDom.reset_tuple_id();
1070
4.20k
  isl::set NewInvalidDom = StmtDom.intersect(PWAC.second);
1071
4.20k
  InvalidDomain = InvalidDomain.unite(NewInvalidDom);
1072
4.20k
  return PWAC.first;
1073
4.20k
}
1074
1075
// Create a map in the size of the provided set domain, that maps from the
1076
// one element of the provided set domain to another element of the provided
1077
// set domain.
1078
// The mapping is limited to all points that are equal in all but the last
1079
// dimension and for which the last dimension of the input is strict smaller
1080
// than the last dimension of the output.
1081
//
1082
//   getEqualAndLarger(set[i0, i1, ..., iX]):
1083
//
1084
//   set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
1085
//     : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
1086
//
1087
47
static isl::map getEqualAndLarger(isl::space SetDomain) {
1088
47
  isl::space Space = SetDomain.map_from_set();
1089
47
  isl::map Map = isl::map::universe(Space);
1090
47
  unsigned lastDimension = Map.dim(isl::dim::in) - 1;
1091
47
1092
47
  // Set all but the last dimension to be equal for the input and output
1093
47
  //
1094
47
  //   input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
1095
47
  //     : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
1096
75
  for (unsigned i = 0; i < lastDimension; 
++i28
)
1097
28
    Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
1098
47
1099
47
  // Set the last dimension of the input to be strict smaller than the
1100
47
  // last dimension of the output.
1101
47
  //
1102
47
  //   input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
1103
47
  Map = Map.order_lt(isl::dim::in, lastDimension, isl::dim::out, lastDimension);
1104
47
  return Map;
1105
47
}
1106
1107
47
isl::set MemoryAccess::getStride(isl::map Schedule) const {
1108
47
  isl::map AccessRelation = getAccessRelation();
1109
47
  isl::space Space = Schedule.get_space().range();
1110
47
  isl::map NextScatt = getEqualAndLarger(Space);
1111
47
1112
47
  Schedule = Schedule.reverse();
1113
47
  NextScatt = NextScatt.lexmin();
1114
47
1115
47
  NextScatt = NextScatt.apply_range(Schedule);
1116
47
  NextScatt = NextScatt.apply_range(AccessRelation);
1117
47
  NextScatt = NextScatt.apply_domain(Schedule);
1118
47
  NextScatt = NextScatt.apply_domain(AccessRelation);
1119
47
1120
47
  isl::set Deltas = NextScatt.deltas();
1121
47
  return Deltas;
1122
47
}
1123
1124
47
bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {
1125
47
  isl::set Stride, StrideX;
1126
47
  bool IsStrideX;
1127
47
1128
47
  Stride = getStride(Schedule);
1129
47
  StrideX = isl::set::universe(Stride.get_space());
1130
57
  for (unsigned i = 0; i < StrideX.dim(isl::dim::set) - 1; 
i++10
)
1131
10
    StrideX = StrideX.fix_si(isl::dim::set, i, 0);
1132
47
  StrideX = StrideX.fix_si(isl::dim::set, StrideX.dim(isl::dim::set) - 1,
1133
47
                           StrideWidth);
1134
47
  IsStrideX = Stride.is_subset(StrideX);
1135
47
1136
47
  return IsStrideX;
1137
47
}
1138
1139
15
bool MemoryAccess::isStrideZero(isl::map Schedule) const {
1140
15
  return isStrideX(Schedule, 0);
1141
15
}
1142
1143
28
bool MemoryAccess::isStrideOne(isl::map Schedule) const {
1144
28
  return isStrideX(Schedule, 1);
1145
28
}
1146
1147
21
void MemoryAccess::setAccessRelation(isl::map NewAccess) {
1148
21
  AccessRelation = NewAccess;
1149
21
}
1150
1151
512
void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {
1152
512
  assert(NewAccess);
1153
512
1154
#ifndef NDEBUG
1155
  // Check domain space compatibility.
1156
  isl::space NewSpace = NewAccess.get_space();
1157
  isl::space NewDomainSpace = NewSpace.domain();
1158
  isl::space OriginalDomainSpace = getStatement()->getDomainSpace();
1159
  assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace));
1160
1161
  // Reads must be executed unconditionally. Writes might be executed in a
1162
  // subdomain only.
1163
  if (isRead()) {
1164
    // Check whether there is an access for every statement instance.
1165
    isl::set StmtDomain = getStatement()->getDomain();
1166
    StmtDomain =
1167
        StmtDomain.intersect_params(getStatement()->getParent()->getContext());
1168
    isl::set NewDomain = NewAccess.domain();
1169
    assert(StmtDomain.is_subset(NewDomain) &&
1170
           "Partial READ accesses not supported");
1171
  }
1172
1173
  isl::space NewAccessSpace = NewAccess.get_space();
1174
  assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&
1175
         "Must specify the array that is accessed");
1176
  isl::id NewArrayId = NewAccessSpace.get_tuple_id(isl::dim::set);
1177
  auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());
1178
  assert(SAI && "Must set a ScopArrayInfo");
1179
1180
  if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
1181
    InvariantEquivClassTy *EqClass =
1182
        getStatement()->getParent()->lookupInvariantEquivClass(
1183
            SAI->getBasePtr());
1184
    assert(EqClass &&
1185
           "Access functions to indirect arrays must have an invariant and "
1186
           "hoisted base pointer");
1187
  }
1188
1189
  // Check whether access dimensions correspond to number of dimensions of the
1190
  // accesses array.
1191
  auto Dims = SAI->getNumberOfDimensions();
1192
  assert(NewAccessSpace.dim(isl::dim::set) == Dims &&
1193
         "Access dims must match array dims");
1194
#endif
1195
1196
512
  NewAccess = NewAccess.gist_domain(getStatement()->getDomain());
1197
512
  NewAccessRelation = NewAccess;
1198
512
}
1199
1200
27
bool MemoryAccess::isLatestPartialAccess() const {
1201
27
  isl::set StmtDom = getStatement()->getDomain();
1202
27
  isl::set AccDom = getLatestAccessRelation().domain();
1203
27
1204
27
  return !StmtDom.is_subset(AccDom);
1205
27
}
1206
1207
//===----------------------------------------------------------------------===//
1208
1209
1.25k
isl::map ScopStmt::getSchedule() const {
1210
1.25k
  isl::set Domain = getDomain();
1211
1.25k
  if (Domain.is_empty())
1212
4
    return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1213
1.25k
  auto Schedule = getParent()->getSchedule();
1214
1.25k
  if (!Schedule)
1215
4
    return nullptr;
1216
1.25k
  Schedule = Schedule.intersect_domain(isl::union_set(Domain));
1217
1.25k
  if (Schedule.is_empty())
1218
0
    return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1219
1.25k
  isl::map M = M.from_union_map(Schedule);
1220
1.25k
  M = M.coalesce();
1221
1.25k
  M = M.gist_domain(Domain);
1222
1.25k
  M = M.coalesce();
1223
1.25k
  return M;
1224
1.25k
}
1225
1226
8
void ScopStmt::restrictDomain(isl::set NewDomain) {
1227
8
  assert(NewDomain.is_subset(Domain) &&
1228
8
         "New domain is not a subset of old domain!");
1229
8
  Domain = NewDomain;
1230
8
}
1231
1232
5.13k
void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
1233
5.13k
  Instruction *AccessInst = Access->getAccessInstruction();
1234
5.13k
1235
5.13k
  if (Access->isArrayKind()) {
1236
3.73k
    MemoryAccessList &MAL = InstructionToAccess[AccessInst];
1237
3.73k
    MAL.emplace_front(Access);
1238
3.73k
  } else 
if (1.39k
Access->isValueKind()1.39k
&&
Access->isWrite()707
) {
1239
342
    Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
1240
342
    assert(!ValueWrites.lookup(AccessVal));
1241
342
1242
342
    ValueWrites[AccessVal] = Access;
1243
1.05k
  } else if (Access->isValueKind() && 
Access->isRead()365
) {
1244
365
    Value *AccessVal = Access->getAccessValue();
1245
365
    assert(!ValueReads.lookup(AccessVal));
1246
365
1247
365
    ValueReads[AccessVal] = Access;
1248
691
  } else if (Access->isAnyPHIKind() && Access->isWrite()) {
1249
456
    PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1250
456
    assert(!PHIWrites.lookup(PHI));
1251
456
1252
456
    PHIWrites[PHI] = Access;
1253
456
  } else 
if (235
Access->isAnyPHIKind()235
&&
Access->isRead()235
) {
1254
235
    PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1255
235
    assert(!PHIReads.lookup(PHI));
1256
235
1257
235
    PHIReads[PHI] = Access;
1258
235
  }
1259
5.13k
1260
5.13k
  if (Prepend) {
1261
16
    MemAccs.insert(MemAccs.begin(), Access);
1262
16
    return;
1263
16
  }
1264
5.12k
  MemAccs.push_back(Access);
1265
5.12k
}
1266
1267
2.30k
void ScopStmt::realignParams() {
1268
2.30k
  for (MemoryAccess *MA : *this)
1269
4.70k
    MA->realignParams();
1270
2.30k
1271
2.30k
  isl::set Ctx = Parent.getContext();
1272
2.30k
  InvalidDomain = InvalidDomain.gist_params(Ctx);
1273
2.30k
  Domain = Domain.gist_params(Ctx);
1274
2.30k
}
1275
1276
/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
1277
1.69k
static isl::set collectBoundedParts(isl::set S) {
1278
1.69k
  isl::set BoundedParts = isl::set::empty(S.get_space());
1279
1.69k
  for (isl::basic_set BSet : S.get_basic_set_list())
1280
2.32k
    if (BSet.is_bounded())
1281
2.09k
      BoundedParts = BoundedParts.unite(isl::set(BSet));
1282
1.69k
  return BoundedParts;
1283
1.69k
}
1284
1285
/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
1286
///
1287
/// @returns A separation of @p S into first an unbounded then a bounded subset,
1288
///          both with regards to the dimension @p Dim.
1289
static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
1290
1.69k
                                                       unsigned Dim) {
1291
3.95k
  for (unsigned u = 0, e = S.n_dim(); u < e; 
u++2.26k
)
1292
2.26k
    S = S.lower_bound_si(isl::dim::set, u, 0);
1293
1.69k
1294
1.69k
  unsigned NumDimsS = S.n_dim();
1295
1.69k
  isl::set OnlyDimS = S;
1296
1.69k
1297
1.69k
  // Remove dimensions that are greater than Dim as they are not interesting.
1298
1.69k
  assert(NumDimsS >= Dim + 1);
1299
1.69k
  OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
1300
1.69k
1301
1.69k
  // Create artificial parametric upper bounds for dimensions smaller than Dim
1302
1.69k
  // as we are not interested in them.
1303
1.69k
  OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
1304
1.69k
1305
2.26k
  for (unsigned u = 0; u < Dim; 
u++571
) {
1306
571
    isl::constraint C = isl::constraint::alloc_inequality(
1307
571
        isl::local_space(OnlyDimS.get_space()));
1308
571
    C = C.set_coefficient_si(isl::dim::param, u, 1);
1309
571
    C = C.set_coefficient_si(isl::dim::set, u, -1);
1310
571
    OnlyDimS = OnlyDimS.add_constraint(C);
1311
571
  }
1312
1.69k
1313
1.69k
  // Collect all bounded parts of OnlyDimS.
1314
1.69k
  isl::set BoundedParts = collectBoundedParts(OnlyDimS);
1315
1.69k
1316
1.69k
  // Create the dimensions greater than Dim again.
1317
1.69k
  BoundedParts =
1318
1.69k
      BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
1319
1.69k
1320
1.69k
  // Remove the artificial upper bound parameters again.
1321
1.69k
  BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
1322
1.69k
1323
1.69k
  isl::set UnboundedParts = S.subtract(BoundedParts);
1324
1.69k
  return std::make_pair(UnboundedParts, BoundedParts);
1325
1.69k
}
1326
1327
/// Create the conditions under which @p L @p Pred @p R is true.
1328
static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
1329
2.73k
                                  isl::pw_aff R) {
1330
2.73k
  switch (Pred) {
1331
2.73k
  case ICmpInst::ICMP_EQ:
1332
733
    return L.eq_set(R);
1333
2.73k
  case ICmpInst::ICMP_NE:
1334
1.08k
    return L.ne_set(R);
1335
2.73k
  case ICmpInst::ICMP_SLT:
1336
726
    return L.lt_set(R);
1337
2.73k
  case ICmpInst::ICMP_SLE:
1338
58
    return L.le_set(R);
1339
2.73k
  case ICmpInst::ICMP_SGT:
1340
117
    return L.gt_set(R);
1341
2.73k
  case ICmpInst::ICMP_SGE:
1342
13
    return L.ge_set(R);
1343
2.73k
  case ICmpInst::ICMP_ULT:
1344
0
    return L.lt_set(R);
1345
2.73k
  case ICmpInst::ICMP_UGT:
1346
0
    return L.gt_set(R);
1347
2.73k
  case ICmpInst::ICMP_ULE:
1348
0
    return L.le_set(R);
1349
2.73k
  case ICmpInst::ICMP_UGE:
1350
0
    return L.ge_set(R);
1351
2.73k
  default:
1352
0
    llvm_unreachable("Non integer predicate not supported");
1353
2.73k
  }
1354
2.73k
}
1355
1356
/// Compute the isl representation for the SCEV @p E in this BB.
1357
///
1358
/// @param S                The Scop in which @p BB resides in.
1359
/// @param BB               The BB for which isl representation is to be
1360
/// computed.
1361
/// @param InvalidDomainMap A map of BB to their invalid domains.
1362
/// @param E                The SCEV that should be translated.
1363
/// @param NonNegative      Flag to indicate the @p E has to be non-negative.
1364
///
1365
/// Note that this function will also adjust the invalid context accordingly.
1366
1367
__isl_give isl_pw_aff *
1368
getPwAff(Scop &S, BasicBlock *BB,
1369
         DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E,
1370
5.51k
         bool NonNegative = false) {
1371
5.51k
  PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
1372
5.51k
  InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
1373
5.51k
  return PWAC.first.release();
1374
5.51k
}
1375
1376
/// Build the conditions sets for the switch @p SI in the @p Domain.
1377
///
1378
/// This will fill @p ConditionSets with the conditions under which control
1379
/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
1380
/// have as many elements as @p SI has successors.
1381
bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
1382
                        __isl_keep isl_set *Domain,
1383
                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1384
17
                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1385
17
  Value *Condition = getConditionFromTerminator(SI);
1386
17
  assert(Condition && "No condition for switch");
1387
17
1388
17
  ScalarEvolution &SE = *S.getSE();
1389
17
  isl_pw_aff *LHS, *RHS;
1390
17
  LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
1391
17
1392
17
  unsigned NumSuccessors = SI->getNumSuccessors();
1393
17
  ConditionSets.resize(NumSuccessors);
1394
54
  for (auto &Case : SI->cases()) {
1395
54
    unsigned Idx = Case.getSuccessorIndex();
1396
54
    ConstantInt *CaseValue = Case.getCaseValue();
1397
54
1398
54
    RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
1399
54
    isl_set *CaseConditionSet =
1400
54
        buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
1401
54
                          isl::manage(RHS))
1402
54
            .release();
1403
54
    ConditionSets[Idx] = isl_set_coalesce(
1404
54
        isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
1405
54
  }
1406
17
1407
17
  assert(ConditionSets[0] == nullptr && "Default condition set was set");
1408
17
  isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
1409
54
  for (unsigned u = 2; u < NumSuccessors; 
u++37
)
1410
37
    ConditionSetUnion =
1411
37
        isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
1412
17
  ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
1413
17
1414
17
  isl_pw_aff_free(LHS);
1415
17
1416
17
  return true;
1417
17
}
1418
1419
/// Build condition sets for unsigned ICmpInst(s).
1420
/// Special handling is required for unsigned operands to ensure that if
1421
/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
1422
/// it should wrap around.
1423
///
1424
/// @param IsStrictUpperBound holds information on the predicate relation
1425
/// between TestVal and UpperBound, i.e,
1426
/// TestVal < UpperBound  OR  TestVal <= UpperBound
1427
__isl_give isl_set *
1428
buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
1429
                           __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
1430
                           const SCEV *SCEV_UpperBound,
1431
                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1432
43
                           bool IsStrictUpperBound) {
1433
43
  // Do not take NonNeg assumption on TestVal
1434
43
  // as it might have MSB (Sign bit) set.
1435
43
  isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
1436
43
  // Take NonNeg assumption on UpperBound.
1437
43
  isl_pw_aff *UpperBound =
1438
43
      getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
1439
43
1440
43
  // 0 <= TestVal
1441
43
  isl_set *First =
1442
43
      isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
1443
43
                            isl_pw_aff_get_domain_space(TestVal))),
1444
43
                        isl_pw_aff_copy(TestVal));
1445
43
1446
43
  isl_set *Second;
1447
43
  if (IsStrictUpperBound)
1448
35
    // TestVal < UpperBound
1449
35
    Second = isl_pw_aff_lt_set(TestVal, UpperBound);
1450
8
  else
1451
8
    // TestVal <= UpperBound
1452
8
    Second = isl_pw_aff_le_set(TestVal, UpperBound);
1453
43
1454
43
  isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
1455
43
  return ConsequenceCondSet;
1456
43
}
1457
1458
/// Build the conditions sets for the branch condition @p Condition in
1459
/// the @p Domain.
1460
///
1461
/// This will fill @p ConditionSets with the conditions under which control
1462
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1463
/// have as many elements as @p TI has successors. If @p TI is nullptr the
1464
/// context under which @p Condition is true/false will be returned as the
1465
/// new elements of @p ConditionSets.
1466
bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
1467
                        Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
1468
                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1469
2.96k
                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1470
2.96k
  ScalarEvolution &SE = *S.getSE();
1471
2.96k
  isl_set *ConsequenceCondSet = nullptr;
1472
2.96k
1473
2.96k
  if (auto Load = dyn_cast<LoadInst>(Condition)) {
1474
1
    const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
1475
1
    const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
1476
1
    bool NonNeg = false;
1477
1
    isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
1478
1
    isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg);
1479
1
    ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
1480
1
                                           isl::manage(RHS))
1481
1
                             .release();
1482
2.95k
  } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
1483
1
    auto *Unique = dyn_cast<ConstantInt>(
1484
1
        getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT()));
1485
1
1486
1
    if (Unique->isZero())
1487
0
      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1488
1
    else
1489
1
      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1490
2.95k
  } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
1491
197
    if (CCond->isZero())
1492
164
      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1493
33
    else
1494
33
      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1495
2.76k
  } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
1496
42
    auto Opcode = BinOp->getOpcode();
1497
42
    assert(Opcode == Instruction::And || Opcode == Instruction::Or);
1498
42
1499
42
    bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
1500
42
                                    InvalidDomainMap, ConditionSets) &&
1501
42
                 buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
1502
23
                                    InvalidDomainMap, ConditionSets);
1503
42
    if (!Valid) {
1504
22
      while (!ConditionSets.empty())
1505
2
        isl_set_free(ConditionSets.pop_back_val());
1506
20
      return false;
1507
20
    }
1508
22
1509
22
    isl_set_free(ConditionSets.pop_back_val());
1510
22
    isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
1511
22
    isl_set_free(ConditionSets.pop_back_val());
1512
22
    isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
1513
22
1514
22
    if (Opcode == Instruction::And)
1515
10
      ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
1516
12
    else
1517
12
      ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
1518
2.71k
  } else {
1519
2.71k
    auto *ICond = dyn_cast<ICmpInst>(Condition);
1520
2.71k
    assert(ICond &&
1521
2.71k
           "Condition of exiting branch was neither constant nor ICmp!");
1522
2.71k
1523
2.71k
    LoopInfo &LI = *S.getLI();
1524
2.71k
    DominatorTree &DT = *S.getDT();
1525
2.71k
    Region &R = S.getRegion();
1526
2.71k
1527
2.71k
    isl_pw_aff *LHS, *RHS;
1528
2.71k
    // For unsigned comparisons we assumed the signed bit of neither operand
1529
2.71k
    // to be set. The comparison is equal to a signed comparison under this
1530
2.71k
    // assumption.
1531
2.71k
    bool NonNeg = ICond->isUnsigned();
1532
2.71k
    const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
1533
2.71k
               *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
1534
2.71k
1535
2.71k
    LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
1536
2.71k
    RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
1537
2.71k
1538
2.71k
    switch (ICond->getPredicate()) {
1539
2.71k
    case ICmpInst::ICMP_ULT:
1540
30
      ConsequenceCondSet =
1541
30
          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
1542
30
                                     RightOperand, InvalidDomainMap, true);
1543
30
      break;
1544
2.71k
    case ICmpInst::ICMP_ULE:
1545
3
      ConsequenceCondSet =
1546
3
          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
1547
3
                                     RightOperand, InvalidDomainMap, false);
1548
3
      break;
1549
2.71k
    case ICmpInst::ICMP_UGT:
1550
5
      ConsequenceCondSet =
1551
5
          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
1552
5
                                     LeftOperand, InvalidDomainMap, true);
1553
5
      break;
1554
2.71k
    case ICmpInst::ICMP_UGE:
1555
5
      ConsequenceCondSet =
1556
5
          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
1557
5
                                     LeftOperand, InvalidDomainMap, false);
1558
5
      break;
1559
2.71k
    default:
1560
2.67k
      LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
1561
2.67k
      RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
1562
2.67k
      ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
1563
2.67k
                                             isl::manage(LHS), isl::manage(RHS))
1564
2.67k
                               .release();
1565
2.67k
      break;
1566
2.94k
    }
1567
2.94k
  }
1568
2.94k
1569
2.94k
  // If no terminator was given we are only looking for parameter constraints
1570
2.94k
  // under which @p Condition is true/false.
1571
2.94k
  if (!TI)
1572
25
    ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
1573
2.94k
  assert(ConsequenceCondSet);
1574
2.94k
  ConsequenceCondSet = isl_set_coalesce(
1575
2.94k
      isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
1576
2.94k
1577
2.94k
  isl_set *AlternativeCondSet = nullptr;
1578
2.94k
  bool TooComplex =
1579
2.94k
      isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
1580
2.94k
1581
2.94k
  if (!TooComplex) {
1582
2.93k
    AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
1583
2.93k
                                          isl_set_copy(ConsequenceCondSet));
1584
2.93k
    TooComplex =
1585
2.93k
        isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
1586
2.93k
  }
1587
2.94k
1588
2.94k
  if (TooComplex) {
1589
5
    S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : 
DebugLoc()0
,
1590
5
                 TI ? TI->getParent() : 
nullptr0
/* BasicBlock */);
1591
5
    isl_set_free(AlternativeCondSet);
1592
5
    isl_set_free(ConsequenceCondSet);
1593
5
    return false;
1594
5
  }
1595
2.93k
1596
2.93k
  ConditionSets.push_back(ConsequenceCondSet);
1597
2.93k
  ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
1598
2.93k
1599
2.93k
  return true;
1600
2.93k
}
1601
1602
/// Build the conditions sets for the terminator @p TI in the @p Domain.
1603
///
1604
/// This will fill @p ConditionSets with the conditions under which control
1605
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1606
/// have as many elements as @p TI has successors.
1607
bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
1608
                        __isl_keep isl_set *Domain,
1609
                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1610
6.03k
                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1611
6.03k
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
1612
17
    return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
1613
17
                              ConditionSets);
1614
6.02k
1615
6.02k
  assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
1616
6.02k
1617
6.02k
  if (TI->getNumSuccessors() == 1) {
1618
3.14k
    ConditionSets.push_back(isl_set_copy(Domain));
1619
3.14k
    return true;
1620
3.14k
  }
1621
2.87k
1622
2.87k
  Value *Condition = getConditionFromTerminator(TI);
1623
2.87k
  assert(Condition && "No condition for Terminator");
1624
2.87k
1625
2.87k
  return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
1626
2.87k
                            ConditionSets);
1627
2.87k
}
1628
1629
ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
1630
                   Loop *SurroundingLoop,
1631
                   std::vector<Instruction *> EntryBlockInstructions)
1632
    : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
1633
      Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1634
121
      Instructions(EntryBlockInstructions) {}
1635
1636
ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
1637
                   Loop *SurroundingLoop,
1638
                   std::vector<Instruction *> Instructions)
1639
    : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
1640
      Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1641
9.12k
      Instructions(Instructions) {}
1642
1643
ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
1644
                   isl::set NewDomain)
1645
    : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain),
1646
24
      Build(nullptr) {
1647
24
  BaseName = getIslCompatibleName("CopyStmt_", "",
1648
24
                                  std::to_string(parent.getCopyStmtsNum()));
1649
24
  isl::id Id = isl::id::alloc(getIslCtx(), getBaseName(), this);
1650
24
  Domain = Domain.set_tuple_id(Id);
1651
24
  TargetRel = TargetRel.set_tuple_id(isl::dim::in, Id);
1652
24
  auto *Access =
1653
24
      new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
1654
24
  parent.addAccessFunction(Access);
1655
24
  addAccess(Access);
1656
24
  SourceRel = SourceRel.set_tuple_id(isl::dim::in, Id);
1657
24
  Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
1658
24
  parent.addAccessFunction(Access);
1659
24
  addAccess(Access);
1660
24
}
1661
1662
9.23k
ScopStmt::~ScopStmt() = default;
1663
1664
850
std::string ScopStmt::getDomainStr() const { return Domain.to_str(); }
1665
1666
850
std::string ScopStmt::getScheduleStr() const {
1667
850
  auto *S = getSchedule().release();
1668
850
  if (!S)
1669
4
    return {};
1670
846
  auto Str = stringFromIslObj(S);
1671
846
  isl_map_free(S);
1672
846
  return Str;
1673
846
}
1674
1675
9.10k
void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
1676
1677
46.0k
BasicBlock *ScopStmt::getEntryBlock() const {
1678
46.0k
  if (isBlockStmt())
1679
43.9k
    return getBasicBlock();
1680
2.17k
  return getRegion()->getEntry();
1681
2.17k
}
1682
1683
5.27k
unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
1684
1685
8.55k
const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1686
1687
727
Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
1688
727
  return NestLoops[Dimension];
1689
727
}
1690
1691
84
isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
1692
1693
67.4k
isl::set ScopStmt::getDomain() const { return Domain; }
1694
1695
5.42k
isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }
1696
1697
81
isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }
1698
1699
94
void ScopStmt::printInstructions(raw_ostream &OS) const {
1700
94
  OS << "Instructions {\n";
1701
94
1702
94
  for (Instruction *Inst : Instructions)
1703
177
    OS.indent(16) << *Inst << "\n";
1704
94
1705
94
  OS.indent(12) << "}\n";
1706
94
}
1707
1708
850
void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
1709
850
  OS << "\t" << getBaseName() << "\n";
1710
850
  OS.indent(12) << "Domain :=\n";
1711
850
1712
850
  if (Domain) {
1713
850
    OS.indent(16) << getDomainStr() << ";\n";
1714
850
  } else
1715
0
    OS.indent(16) << "n/a\n";
1716
850
1717
850
  OS.indent(12) << "Schedule :=\n";
1718
850
1719
850
  if (Domain) {
1720
850
    OS.indent(16) << getScheduleStr() << ";\n";
1721
850
  } else
1722
0
    OS.indent(16) << "n/a\n";
1723
850
1724
850
  for (MemoryAccess *Access : MemAccs)
1725
1.73k
    Access->print(OS);
1726
850
1727
850
  if (PrintInstructions)
1728
32
    printInstructions(OS.indent(12));
1729
850
}
1730
1731
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1732
LLVM_DUMP_METHOD void ScopStmt::dump() const { print(dbgs(), true); }
1733
#endif
1734
1735
525
void ScopStmt::removeAccessData(MemoryAccess *MA) {
1736
525
  if (MA->isRead() && 
MA->isOriginalValueKind()472
) {
1737
44
    bool Found = ValueReads.erase(MA->getAccessValue());
1738
44
    (void)Found;
1739
44
    assert(Found && "Expected access data not found");
1740
44
  }
1741
525
  if (MA->isWrite() && 
MA->isOriginalValueKind()53
) {
1742
27
    bool Found = ValueWrites.erase(cast<Instruction>(MA->getAccessValue()));
1743
27
    (void)Found;
1744
27
    assert(Found && "Expected access data not found");
1745
27
  }
1746
525
  if (MA->isWrite() && 
MA->isOriginalAnyPHIKind()53
) {
1747
7
    bool Found = PHIWrites.erase(cast<PHINode>(MA->getAccessInstruction()));
1748
7
    (void)Found;
1749
7
    assert(Found && "Expected access data not found");
1750
7
  }
1751
525
  if (MA->isRead() && 
MA->isOriginalAnyPHIKind()472
) {
1752
14
    bool Found = PHIReads.erase(cast<PHINode>(MA->getAccessInstruction()));
1753
14
    (void)Found;
1754
14
    assert(Found && "Expected access data not found");
1755
14
  }
1756
525
}
1757
1758
362
void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {
1759
362
  // Remove the memory accesses from this statement together with all scalar
1760
362
  // accesses that were caused by it. MemoryKind::Value READs have no access
1761
362
  // instruction, hence would not be removed by this function. However, it is
1762
362
  // only used for invariant LoadInst accesses, its arguments are always affine,
1763
362
  // hence synthesizable, and therefore there are no MemoryKind::Value READ
1764
362
  // accesses to be removed.
1765
3.82k
  auto Predicate = [&](MemoryAccess *Acc) {
1766
3.82k
    return Acc->getAccessInstruction() == MA->getAccessInstruction();
1767
3.82k
  };
1768
1.91k
  for (auto *MA : MemAccs) {
1769
1.91k
    if (Predicate(MA)) {
1770
381
      removeAccessData(MA);
1771
381
      Parent.removeAccessData(MA);
1772
381
    }
1773
1.91k
  }
1774
362
  MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
1775
362
                MemAccs.end());
1776
362
  InstructionToAccess.erase(MA->getAccessInstruction());
1777
362
}
1778
1779
273
void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
1780
273
  if (AfterHoisting) {
1781
144
    auto MAIt = std::find(MemAccs.begin(), MemAccs.end(), MA);
1782
144
    assert(MAIt != MemAccs.end());
1783
144
    MemAccs.erase(MAIt);
1784
144
1785
144
    removeAccessData(MA);
1786
144
    Parent.removeAccessData(MA);
1787
144
  }
1788
273
1789
273
  auto It = InstructionToAccess.find(MA->getAccessInstruction());
1790
273
  if (It != InstructionToAccess.end()) {
1791
159
    It->second.remove(MA);
1792
159
    if (It->second.empty())
1793
155
      InstructionToAccess.erase(MA->getAccessInstruction());
1794
159
  }
1795
273
}
1796
1797
1
MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
1798
1
  MemoryAccess *Access = lookupInputAccessOf(V);
1799
1
  if (Access)
1800
0
    return Access;
1801
1
1802
1
  ScopArrayInfo *SAI =
1803
1
      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
1804
1
  Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
1805
1
                            true, {}, {}, V, MemoryKind::Value);
1806
1
  Parent.addAccessFunction(Access);
1807
1
  Access->buildAccessRelation(SAI);
1808
1
  addAccess(Access);
1809
1
  Parent.addAccessData(Access);
1810
1
  return Access;
1811
1
}
1812
1813
0
raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
1814
0
  S.print(OS, PollyPrintInstructions);
1815
0
  return OS;
1816
0
}
1817
1818
//===----------------------------------------------------------------------===//
1819
/// Scop class implement
1820
1821
94
void Scop::setContext(isl::set NewContext) {
1822
94
  Context = NewContext.align_params(Context.get_space());
1823
94
}
1824
1825
namespace {
1826
1827
/// Remap parameter values but keep AddRecs valid wrt. invariant loads.
1828
struct SCEVSensitiveParameterRewriter
1829
    : public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
1830
  const ValueToValueMap &VMap;
1831
1832
public:
1833
  SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,
1834
                                 ScalarEvolution &SE)
1835
11.7k
      : SCEVRewriteVisitor(SE), VMap(VMap) {}
1836
1837
  static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,
1838
11.7k
                             const ValueToValueMap &VMap) {
1839
11.7k
    SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1840
11.7k
    return SSPR.visit(E);
1841
11.7k
  }
1842
1843
316
  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
1844
316
    auto *Start = visit(E->getStart());
1845
316
    auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
1846
316
                                    visit(E->getStepRecurrence(SE)),
1847
316
                                    E->getLoop(), SCEV::FlagAnyWrap);
1848
316
    return SE.getAddExpr(Start, AddRec);
1849
316
  }
1850
1851
6.29k
  const SCEV *visitUnknown(const SCEVUnknown *E) {
1852
6.29k
    if (auto *NewValue = VMap.lookup(E->getValue()))
1853
53
      return SE.getUnknown(NewValue);
1854
6.24k
    return E;
1855
6.24k
  }
1856
};
1857
1858
/// Check whether we should remap a SCEV expression.
1859
struct SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
1860
  const ValueToValueMap &VMap;
1861
  bool FoundInside = false;
1862
  const Scop *S;
1863
1864
public:
1865
  SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,
1866
                     const Scop *S)
1867
17.4k
      : SCEVTraversal(*this), VMap(VMap), S(S) {}
1868
1869
  static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
1870
17.4k
                         const ValueToValueMap &VMap, const Scop *S) {
1871
17.4k
    SCEVFindInsideScop SFIS(VMap, SE, S);
1872
17.4k
    SFIS.visitAll(E);
1873
17.4k
    return SFIS.FoundInside;
1874
17.4k
  }
1875
1876
20.8k
  bool follow(const SCEV *E) {
1877
20.8k
    if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
1878
4.69k
      FoundInside |= S->getRegion().contains(AddRec->getLoop());
1879
16.1k
    } else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
1880
7.70k
      if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
1881
2.74k
        FoundInside |= S->getRegion().contains(I) && 
!VMap.count(I)1.35k
;
1882
7.70k
    }
1883
20.8k
    return !FoundInside;
1884
20.8k
  }
1885
1886
15.1k
  bool isDone() { return FoundInside; }
1887
};
1888
} // end anonymous namespace
1889
1890
17.4k
const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {
1891
17.4k
  // Check whether it makes sense to rewrite the SCEV.  (ScalarEvolution
1892
17.4k
  // doesn't like addition between an AddRec and an expression that
1893
17.4k
  // doesn't have a dominance relationship with it.)
1894
17.4k
  if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))
1895
5.64k
    return E;
1896
11.7k
1897
11.7k
  // Rewrite SCEV.
1898
11.7k
  return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);
1899
11.7k
}
1900
1901
// This table of function names is used to translate parameter names in more
1902
// human-readable names. This makes it easier to interpret Polly analysis
1903
// results.
1904
StringMap<std::string> KnownNames = {
1905
    {"_Z13get_global_idj", "global_id"},
1906
    {"_Z12get_local_idj", "local_id"},
1907
    {"_Z15get_global_sizej", "global_size"},
1908
    {"_Z14get_local_sizej", "local_size"},
1909
    {"_Z12get_work_dimv", "work_dim"},
1910
    {"_Z17get_global_offsetj", "global_offset"},
1911
    {"_Z12get_group_idj", "group_id"},
1912
    {"_Z14get_num_groupsj", "num_groups"},
1913
};
1914
1915
4
static std::string getCallParamName(CallInst *Call) {
1916
4
  std::string Result;
1917
4
  raw_string_ostream OS(Result);
1918
4
  std::string Name = Call->getCalledFunction()->getName();
1919
4
1920
4
  auto Iterator = KnownNames.find(Name);
1921
4
  if (Iterator != KnownNames.end())
1922
3
    Name = "__" + Iterator->getValue();
1923
4
  OS << Name;
1924
4
  for (auto &Operand : Call->arg_operands()) {
1925
3
    ConstantInt *Op = cast<ConstantInt>(&Operand);
1926
3
    OS << "_" << Op->getValue();
1927
3
  }
1928
4
  OS.flush();
1929
4
  return Result;
1930
4
}
1931
1932
1.27k
void Scop::createParameterId(const SCEV *Parameter) {
1933
1.27k
  assert(Parameters.count(Parameter));
1934
1.27k
  assert(!ParameterIds.count(Parameter));
1935
1.27k
1936
1.27k
  std::string ParameterName = "p_" + std::to_string(getNumParams() - 1);
1937
1.27k
1938
1.27k
  if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1939
1.19k
    Value *Val = ValueParameter->getValue();
1940
1.19k
    CallInst *Call = dyn_cast<CallInst>(Val);
1941
1.19k
1942
1.19k
    if (Call && 
isConstCall(Call)6
) {
1943
4
      ParameterName = getCallParamName(Call);
1944
1.19k
    } else if (UseInstructionNames) {
1945
1.18k
      // If this parameter references a specific Value and this value has a name
1946
1.18k
      // we use this name as it is likely to be unique and more useful than just
1947
1.18k
      // a number.
1948
1.18k
      if (Val->hasName())
1949
1.13k
        ParameterName = Val->getName();
1950
50
      else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1951
50
        auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1952
50
        if (LoadOrigin->hasName()) {
1953
43
          ParameterName += "_loaded_from_";
1954
43
          ParameterName +=
1955
43
              LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1956
43
        }
1957
50
      }
1958
1.18k
    }
1959
1.19k
1960
1.19k
    ParameterName = getIslCompatibleName("", ParameterName, "");
1961
1.19k
  }
1962
1.27k
1963
1.27k
  isl::id Id = isl::id::alloc(getIslCtx(), ParameterName,
1964
1.27k
                              const_cast<void *>((const void *)Parameter));
1965
1.27k
  ParameterIds[Parameter] = Id;
1966
1.27k
}
1967
1968
12.5k
void Scop::addParams(const ParameterSetTy &NewParameters) {
1969
12.5k
  for (const SCEV *Parameter : NewParameters) {
1970
3.22k
    // Normalize the SCEV to get the representing element for an invariant load.
1971
3.22k
    Parameter = extractConstantFactor(Parameter, *SE).second;
1972
3.22k
    Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1973
3.22k
1974
3.22k
    if (Parameters.insert(Parameter))
1975
1.27k
      createParameterId(Parameter);
1976
3.22k
  }
1977
12.5k
}
1978
1979
14.1k
isl::id Scop::getIdForParam(const SCEV *Parameter) const {
1980
14.1k
  // Normalize the SCEV to get the representing element for an invariant load.
1981
14.1k
  Parameter = getRepresentingInvariantLoadSCEV(Parameter);
1982
14.1k
  return ParameterIds.lookup(Parameter);
1983
14.1k
}
1984
1985
3.88k
isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
1986
3.88k
  isl::set DomainContext = getDomains().params();
1987
3.88k
  return C.intersect_params(DomainContext);
1988
3.88k
}
1989
1990
13
bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
1991
13
  return DT.dominates(BB, getEntry());
1992
13
}
1993
1994
void Scop::addUserAssumptions(
1995
    AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
1996
1.19k
    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1997
1.19k
  for (auto &Assumption : AC.assumptions()) {
1998
21
    auto *CI = dyn_cast_or_null<CallInst>(Assumption);
1999
21
    if (!CI || CI->getNumArgOperands() != 1)
2000
0
      continue;
2001
21
2002
21
    bool InScop = contains(CI);
2003
21
    if (!InScop && 
!isDominatedBy(DT, CI->getParent())13
)
2004
0
      continue;
2005
21
2006
21
    auto *L = LI.getLoopFor(CI->getParent());
2007
21
    auto *Val = CI->getArgOperand(0);
2008
21
    ParameterSetTy DetectedParams;
2009
21
    if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
2010
0
      ORE.emit(
2011
0
          OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
2012
0
          << "Non-affine user assumption ignored.");
2013
0
      continue;
2014
0
    }
2015
21
2016
21
    // Collect all newly introduced parameters.
2017
21
    ParameterSetTy NewParams;
2018
22
    for (auto *Param : DetectedParams) {
2019
22
      Param = extractConstantFactor(Param, *SE).second;
2020
22
      Param = getRepresentingInvariantLoadSCEV(Param);
2021
22
      if (Parameters.count(Param))
2022
18
        continue;
2023
4
      NewParams.insert(Param);
2024
4
    }
2025
21
2026
21
    SmallVector<isl_set *, 2> ConditionSets;
2027
21
    auto *TI = InScop ? 
CI->getParent()->getTerminator()8
:
nullptr13
;
2028
21
    BasicBlock *BB = InScop ? 
CI->getParent()8
:
getRegion().getEntry()13
;
2029
21
    auto *Dom = InScop ? 
DomainMap[BB].copy()8
:
Context.copy()13
;
2030
21
    assert(Dom && "Cannot propagate a nullptr.");
2031
21
    bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom,
2032
21
                                    InvalidDomainMap, ConditionSets);
2033
21
    isl_set_free(Dom);
2034
21
2035
21
    if (!Valid)
2036
0
      continue;
2037
21
2038
21
    isl_set *AssumptionCtx = nullptr;
2039
21
    if (InScop) {
2040
8
      AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
2041
8
      isl_set_free(ConditionSets[0]);
2042
13
    } else {
2043
13
      AssumptionCtx = isl_set_complement(ConditionSets[1]);
2044
13
      AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
2045
13
    }
2046
21
2047
21
    // Project out newly introduced parameters as they are not otherwise useful.
2048
21
    if (!NewParams.empty()) {
2049
10
      for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); 
u++6
) {
2050
6
        auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
2051
6
        auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
2052
6
        isl_id_free(Id);
2053
6
2054
6
        if (!NewParams.count(Param))
2055
2
          continue;
2056
4
2057
4
        AssumptionCtx =
2058
4
            isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
2059
4
      }
2060
4
    }
2061
21
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
2062
21
             << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
2063
21
    Context = Context.intersect(isl::manage(AssumptionCtx));
2064
21
  }
2065
1.19k
}
2066
2067
1.15k
void Scop::addUserContext() {
2068
1.15k
  if (UserContextStr.empty())
2069
1.15k
    return;
2070
3
2071
3
  isl::set UserContext = isl::set(getIslCtx(), UserContextStr.c_str());
2072
3
  isl::space Space = getParamSpace();
2073
3
  if (Space.dim(isl::dim::param) != UserContext.dim(isl::dim::param)) {
2074
2
    std::string SpaceStr = Space.to_str();
2075
2
    errs() << "Error: the context provided in -polly-context has not the same "
2076
2
           << "number of dimensions than the computed context. Due to this "
2077
2
           << "mismatch, the -polly-context option is ignored. Please provide "
2078
2
           << "the context in the parameter space: " << SpaceStr << ".\n";
2079
2
    return;
2080
2
  }
2081
1
2082
2
  
for (unsigned i = 0; 1
i < Space.dim(isl::dim::param);
i++1
) {
2083
1
    std::string NameContext = Context.get_dim_name(isl::dim::param, i);
2084
1
    std::string NameUserContext = UserContext.get_dim_name(isl::dim::param, i);
2085
1
2086
1
    if (NameContext != NameUserContext) {
2087
0
      std::string SpaceStr = Space.to_str();
2088
0
      errs() << "Error: the name of dimension " << i
2089
0
             << " provided in -polly-context "
2090
0
             << "is '" << NameUserContext << "', but the name in the computed "
2091
0
             << "context is '" << NameContext
2092
0
             << "'. Due to this name mismatch, "
2093
0
             << "the -polly-context option is ignored. Please provide "
2094
0
             << "the context in the parameter space: " << SpaceStr << ".\n";
2095
0
      return;
2096
0
    }
2097
1
2098
1
    UserContext = UserContext.set_dim_id(isl::dim::param, i,
2099
1
                                         Space.get_dim_id(isl::dim::param, i));
2100
1
  }
2101
1
2102
1
  Context = Context.intersect(UserContext);
2103
1
}
2104
2105
1.20k
void Scop::buildInvariantEquivalenceClasses() {
2106
1.20k
  DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
2107
1.20k
2108
1.20k
  const InvariantLoadsSetTy &RIL = getRequiredInvariantLoads();
2109
1.20k
  for (LoadInst *LInst : RIL) {
2110
290
    const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
2111
290
2112
290
    Type *Ty = LInst->getType();
2113
290
    LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
2114
290
    if (ClassRep) {
2115
36
      InvEquivClassVMap[LInst] = ClassRep;
2116
36
      continue;
2117
36
    }
2118
254
2119
254
    ClassRep = LInst;
2120
254
    InvariantEquivClasses.emplace_back(
2121
254
        InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), nullptr, Ty});
2122
254
  }
2123
1.20k
}
2124
2125
1.20k
void Scop::buildContext() {
2126
1.20k
  isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
2127
1.20k
  Context = isl::set::universe(Space);
2128
1.20k
  InvalidContext = isl::set::empty(Space);
2129
1.20k
  AssumedContext = isl::set::universe(Space);
2130
1.20k
}
2131
2132
1.15k
void Scop::addParameterBounds() {
2133
1.15k
  unsigned PDim = 0;
2134
1.20k
  for (auto *Parameter : Parameters) {
2135
1.20k
    ConstantRange SRange = SE->getSignedRange(Parameter);
2136
1.20k
    Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);
2137
1.20k
  }
2138
1.15k
}
2139
2140
2.31k
static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
2141
2.31k
  std::vector<isl::id> OutermostSizeIds;
2142
4.91k
  for (auto Array : Arrays) {
2143
4.91k
    // To check if an array is a Fortran array, we check if it has a isl_pw_aff
2144
4.91k
    // for its outermost dimension. Fortran arrays will have this since the
2145
4.91k
    // outermost dimension size can be picked up from their runtime description.
2146
4.91k
    // TODO: actually need to check if it has a FAD, but for now this works.
2147
4.91k
    if (Array->getNumberOfDimensions() > 0) {
2148
3.64k
      isl::pw_aff PwAff = Array->getDimensionSizePw(0);
2149
3.64k
      if (!PwAff)
2150
3.63k
        continue;
2151
14
2152
14
      isl::id Id = PwAff.get_dim_id(isl::dim::param, 0);
2153
14
      assert(!Id.is_null() &&
2154
14
             "Invalid Id for PwAff expression in Fortran array");
2155
14
      OutermostSizeIds.push_back(Id);
2156
14
    }
2157
4.91k
  }
2158
2.31k
  return OutermostSizeIds;
2159
2.31k
}
2160
2161
// The FORTRAN array size parameters are known to be non-negative.
2162
static isl::set boundFortranArrayParams(isl::set Context,
2163
1.15k
                                        Scop::array_range Arrays) {
2164
1.15k
  std::vector<isl::id> OutermostSizeIds;
2165
1.15k
  OutermostSizeIds = getFortranArrayIds(Arrays);
2166
1.15k
2167
1.15k
  for (isl::id Id : OutermostSizeIds) {
2168
7
    int dim = Context.find_dim_by_id(isl::dim::param, Id);
2169
7
    Context = Context.lower_bound_si(isl::dim::param, dim, 0);
2170
7
  }
2171
1.15k
2172
1.15k
  return Context;
2173
1.15k
}
2174
2175
1.15k
void Scop::realignParams() {
2176
1.15k
  if (PollyIgnoreParamBounds)
2177
1
    return;
2178
1.15k
2179
1.15k
  // Add all parameters into a common model.
2180
1.15k
  isl::space Space = getFullParamSpace();
2181
1.15k
2182
1.15k
  // Align the parameters of all data structures to the model.
2183
1.15k
  Context = Context.align_params(Space);
2184
1.15k
2185
1.15k
  // Bound the size of the fortran array dimensions.
2186
1.15k
  Context = boundFortranArrayParams(Context, arrays());
2187
1.15k
2188
1.15k
  // As all parameters are known add bounds to them.
2189
1.15k
  addParameterBounds();
2190
1.15k
2191
1.15k
  for (ScopStmt &Stmt : *this)
2192
2.30k
    Stmt.realignParams();
2193
1.15k
  // Simplify the schedule according to the context too.
2194
1.15k
  Schedule = Schedule.gist_domain_params(getContext());
2195
1.15k
}
2196
2197
static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
2198
1.15k
                                          const Scop &S) {
2199
1.15k
  // If we have modeled all blocks in the SCoP that have side effects we can
2200
1.15k
  // simplify the context with the constraints that are needed for anything to
2201
1.15k
  // be executed at all. However, if we have error blocks in the SCoP we already
2202
1.15k
  // assumed some parameter combinations cannot occur and removed them from the
2203
1.15k
  // domains, thus we cannot use the remaining domain to simplify the
2204
1.15k
  // assumptions.
2205
1.15k
  if (!S.hasErrorBlock()) {
2206
1.13k
    auto DomainParameters = S.getDomains().params();
2207
1.13k
    AssumptionContext = AssumptionContext.gist_params(DomainParameters);
2208
1.13k
  }
2209
1.15k
2210
1.15k
  AssumptionContext = AssumptionContext.gist_params(S.getContext());
2211
1.15k
  return AssumptionContext;
2212
1.15k
}
2213
2214
1.15k
void Scop::simplifyContexts() {
2215
1.15k
  // The parameter constraints of the iteration domains give us a set of
2216
1.15k
  // constraints that need to hold for all cases where at least a single
2217
1.15k
  // statement iteration is executed in the whole scop. We now simplify the
2218
1.15k
  // assumed context under the assumption that such constraints hold and at
2219
1.15k
  // least a single statement iteration is executed. For cases where no
2220
1.15k
  // statement instances are executed, the assumptions we have taken about
2221
1.15k
  // the executed code do not matter and can be changed.
2222
1.15k
  //
2223
1.15k
  // WARNING: This only holds if the assumptions we have taken do not reduce
2224
1.15k
  //          the set of statement instances that are executed. Otherwise we
2225
1.15k
  //          may run into a case where the iteration domains suggest that
2226
1.15k
  //          for a certain set of parameter constraints no code is executed,
2227
1.15k
  //          but in the original program some computation would have been
2228
1.15k
  //          performed. In such a case, modifying the run-time conditions and
2229
1.15k
  //          possibly influencing the run-time check may cause certain scops
2230
1.15k
  //          to not be executed.
2231
1.15k
  //
2232
1.15k
  // Example:
2233
1.15k
  //
2234
1.15k
  //   When delinearizing the following code:
2235
1.15k
  //
2236
1.15k
  //     for (long i = 0; i < 100; i++)
2237
1.15k
  //       for (long j = 0; j < m; j++)
2238
1.15k
  //         A[i+p][j] = 1.0;
2239
1.15k
  //
2240
1.15k
  //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
2241
1.15k
  //   otherwise we would access out of bound data. Now, knowing that code is
2242
1.15k
  //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
2243
1.15k
  AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
2244
1.15k
  InvalidContext = InvalidContext.align_params(getParamSpace());
2245
1.15k
}
2246
2247
/// Add the minimal/maximal access in @p Set to @p User.
2248
///
2249
/// @return True if more accesses should be added, false if we reached the
2250
///         maximal number of run-time checks to be generated.
2251
static bool buildMinMaxAccess(isl::set Set,
2252
548
                              Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
2253
548
  isl::pw_multi_aff MinPMA, MaxPMA;
2254
548
  isl::pw_aff LastDimAff;
2255
548
  isl::aff OneAff;
2256
548
  unsigned Pos;
2257
548
2258
548
  Set = Set.remove_divs();
2259
548
  polly::simplify(Set);
2260
548
2261
548
  if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
2262
4
    Set = Set.simple_hull();
2263
548
2264
548
  // Restrict the number of parameters involved in the access as the lexmin/
2265
548
  // lexmax computation will take too long if this number is high.
2266
548
  //
2267
548
  // Experiments with a simple test case using an i7 4800MQ:
2268
548
  //
2269
548
  //  #Parameters involved | Time (in sec)
2270
548
  //            6          |     0.01
2271
548
  //            7          |     0.04
2272
548
  //            8          |     0.12
2273
548
  //            9          |     0.40
2274
548
  //           10          |     1.54
2275
548
  //           11          |     6.78
2276
548
  //           12          |    30.38
2277
548
  //
2278
548
  if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
2279
7
    unsigned InvolvedParams = 0;
2280
81
    for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; 
u++74
)
2281
74
      if (Set.involves_dims(isl::dim::param, u, 1))
2282
23
        InvolvedParams++;
2283
7
2284
7
    if (InvolvedParams > RunTimeChecksMaxParameters)
2285
1
      return false;
2286
547
  }
2287
547
2288
547
  MinPMA = Set.lexmin_pw_multi_aff();
2289
547
  MaxPMA = Set.lexmax_pw_multi_aff();
2290
547
2291
547
  MinPMA = MinPMA.coalesce();
2292
547
  MaxPMA = MaxPMA.coalesce();
2293
547
2294
547
  // Adjust the last dimension of the maximal access by one as we want to
2295
547
  // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
2296
547
  // we test during code generation might now point after the end of the
2297
547
  // allocated array but we will never dereference it anyway.
2298
547
  assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&
2299
547
         "Assumed at least one output dimension");
2300
547
2301
547
  Pos = MaxPMA.dim(isl::dim::out) - 1;
2302
547
  LastDimAff = MaxPMA.get_pw_aff(Pos);
2303
547
  OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
2304
547
  OneAff = OneAff.add_constant_si(1);
2305
547
  LastDimAff = LastDimAff.add(OneAff);
2306
547
  MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
2307
547
2308
547
  if (!MinPMA || 
!MaxPMA544
)
2309
3
    return false;
2310
544
2311
544
  MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
2312
544
2313
544
  return true;
2314
544
}
2315
2316
1.76k
static isl::set getAccessDomain(MemoryAccess *MA) {
2317
1.76k
  isl::set Domain = MA->getStatement()->getDomain();
2318
1.76k
  Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
2319
1.76k
  return Domain.reset_tuple_id();
2320
1.76k
}
2321
2322
/// Wrapper function to calculate minimal/maximal accesses to each array.
2323
static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
2324
427
                                  Scop::MinMaxVectorTy &MinMaxAccesses) {
2325
427
  MinMaxAccesses.reserve(AliasGroup.size());
2326
427
2327
427
  isl::union_set Domains = S.getDomains();
2328
427
  isl::union_map Accesses = isl::union_map::empty(S.getParamSpace());
2329
427
2330
427
  for (MemoryAccess *MA : AliasGroup)
2331
846
    Accesses = Accesses.add_map(MA->getAccessRelation());
2332
427
2333
427
  Accesses = Accesses.intersect_domain(Domains);
2334
427
  isl::union_set Locations = Accesses.range();
2335
427
2336
427
  bool LimitReached = false;
2337
548
  for (isl::set Set : Locations.get_set_list()) {
2338
548
    LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S);
2339
548
    if (LimitReached)
2340
4
      break;
2341
548
  }
2342
427
2343
427
  return !LimitReached;
2344
427
}
2345
2346
/// Helper to treat non-affine regions and basic blocks the same.
2347
///
2348
///{
2349
2350
/// Return the block that is the representing block for @p RN.
2351
16.9k
static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
2352
16.9k
  return RN->isSubRegion() ? 
RN->getNodeAs<Region>()->getEntry()297
2353
16.9k
                           : 
RN->getNodeAs<BasicBlock>()16.6k
;
2354
16.9k
}
2355
2356
/// Return the @p idx'th block that is executed after @p RN.
2357
static inline BasicBlock *
2358
8.76k
getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
2359
8.76k
  if (RN->isSubRegion()) {
2360
106
    assert(idx == 0);
2361
106
    return RN->getNodeAs<Region>()->getExit();
2362
106
  }
2363
8.65k
  return TI->getSuccessor(idx);
2364
8.65k
}
2365
2366
/// Return the smallest loop surrounding @p RN.
2367
18.9k
static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
2368
18.9k
  if (!RN->isSubRegion()) {
2369
17.4k
    BasicBlock *BB = RN->getNodeAs<BasicBlock>();
2370
17.4k
    Loop *L = LI.getLoopFor(BB);
2371
17.4k
2372
17.4k
    // Unreachable statements are not considered to belong to a LLVM loop, as
2373
17.4k
    // they are not part of an actual loop in the control flow graph.
2374
17.4k
    // Nevertheless, we handle certain unreachable statements that are common
2375
17.4k
    // when modeling run-time bounds checks as being part of the loop to be
2376
17.4k
    // able to model them and to later eliminate the run-time bounds checks.
2377
17.4k
    //
2378
17.4k
    // Specifically, for basic blocks that terminate in an unreachable and
2379
17.4k
    // where the immediate predecessor is part of a loop, we assume these
2380
17.4k
    // basic blocks belong to the loop the predecessor belongs to. This
2381
17.4k
    // allows us to model the following code.
2382
17.4k
    //
2383
17.4k
    // for (i = 0; i < N; i++) {
2384
17.4k
    //   if (i > 1024)
2385
17.4k
    //     abort();            <- this abort might be translated to an
2386
17.4k
    //                            unreachable
2387
17.4k
    //
2388
17.4k
    //   A[i] = ...
2389
17.4k
    // }
2390
17.4k
    if (!L && 
isa<UnreachableInst>(BB->getTerminator())2.34k
&&
BB->getPrevNode()0
)
2391
0
      L = LI.getLoopFor(BB->getPrevNode());
2392
17.4k
    return L;
2393
17.4k
  }
2394
1.53k
2395
1.53k
  Region *NonAffineSubRegion = RN->getNodeAs<Region>();
2396
1.53k
  Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
2397
2.51k
  while (L && 
NonAffineSubRegion->contains(L)1.86k
)
2398
983
    L = L->getParentLoop();
2399
1.53k
  return L;
2400
1.53k
}
2401
2402
/// Get the number of blocks in @p L.
2403
///
2404
/// The number of blocks in a loop are the number of basic blocks actually
2405
/// belonging to the loop, as well as all single basic blocks that the loop
2406
/// exits to and which terminate in an unreachable instruction. We do not
2407
/// allow such basic blocks in the exit of a scop, hence they belong to the
2408
/// scop and represent run-time conditions which we want to model and
2409
/// subsequently speculate away.
2410
///
2411
/// @see getRegionNodeLoop for additional details.
2412
5.28k
unsigned getNumBlocksInLoop(Loop *L) {
2413
5.28k
  unsigned NumBlocks = L->getNumBlocks();
2414
5.28k
  SmallVector<BasicBlock *, 4> ExitBlocks;
2415
5.28k
  L->getExitBlocks(ExitBlocks);
2416
5.28k
2417
5.30k
  for (auto ExitBlock : ExitBlocks) {
2418
5.30k
    if (isa<UnreachableInst>(ExitBlock->getTerminator()))
2419
62
      NumBlocks++;
2420
5.30k
  }
2421
5.28k
  return NumBlocks;
2422
5.28k
}
2423
2424
5.53k
static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
2425
5.53k
  if (!RN->isSubRegion())
2426
5.43k
    return 1;
2427
105
2428
105
  Region *R = RN->getNodeAs<Region>();
2429
105
  return std::distance(R->block_begin(), R->block_end());
2430
105
}
2431
2432
static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
2433
11.3k
                               const DominatorTree &DT) {
2434
11.3k
  if (!RN->isSubRegion())
2435
11.1k
    return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
2436
216
  for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
2437
588
    if (isErrorBlock(*BB, R, LI, DT))
2438
15
      return true;
2439
216
  
return false201
;
2440
216
}
2441
2442
///}
2443
2444
2.31k
isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
2445
2.31k
  return getDomainConditions(Stmt->getEntryBlock());
2446
2.31k
}
2447
2448
19.4k
isl::set Scop::getDomainConditions(BasicBlock *BB) const {
2449
19.4k
  auto DIt = DomainMap.find(BB);
2450
19.4k
  if (DIt != DomainMap.end())
2451
19.4k
    return DIt->getSecond();
2452
16
2453
16
  auto &RI = *R.getRegionInfo();
2454
16
  auto *BBR = RI.getRegionFor(BB);
2455
32
  while (BBR->getEntry() == BB)
2456
16
    BBR = BBR->getParent();
2457
16
  return getDomainConditions(BBR->getEntry());
2458
16
}
2459
2460
bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
2461
1.20k
                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2462
1.20k
  bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
2463
1.20k
  auto *EntryBB = R->getEntry();
2464
1.20k
  auto *L = IsOnlyNonAffineRegion ? 
nullptr18
:
LI.getLoopFor(EntryBB)1.18k
;
2465
1.20k
  int LD = getRelativeLoopDepth(L);
2466
1.20k
  auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1));
2467
1.20k
2468
2.21k
  while (LD-- >= 0) {
2469
1.01k
    L = L->getParentLoop();
2470
1.01k
  }
2471
1.20k
2472
1.20k
  InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
2473
1.20k
  DomainMap[EntryBB] = isl::manage(S);
2474
1.20k
2475
1.20k
  if (IsOnlyNonAffineRegion)
2476
18
    return !containsErrorBlock(R->getNode(), *R, LI, DT);
2477
1.18k
2478
1.18k
  if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
2479
5
    return false;
2480
1.17k
2481
1.17k
  if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
2482
0
    return false;
2483
1.17k
2484
1.17k
  // Error blocks and blocks dominated by them have been assumed to never be
2485
1.17k
  // executed. Representing them in the Scop does not add any value. In fact,
2486
1.17k
  // it is likely to cause issues during construction of the ScopStmts. The
2487
1.17k
  // contents of error blocks have not been verified to be expressible and
2488
1.17k
  // will cause problems when building up a ScopStmt for them.
2489
1.17k
  // Furthermore, basic blocks dominated by error blocks may reference
2490
1.17k
  // instructions in the error block which, if the error block is not modeled,
2491
1.17k
  // can themselves not be constructed properly. To this end we will replace
2492
1.17k
  // the domains of error blocks and those only reachable via error blocks
2493
1.17k
  // with an empty set. Additionally, we will record for each block under which
2494
1.17k
  // parameter combination it would be reached via an error block in its
2495
1.17k
  // InvalidDomain. This information is needed during load hoisting.
2496
1.17k
  if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
2497
0
    return false;
2498
1.17k
2499
1.17k
  return true;
2500
1.17k
}
2501
2502
/// Adjust the dimensions of @p Dom that was constructed for @p OldL
2503
///        to be compatible to domains constructed for loop @p NewL.
2504
///
2505
/// This function assumes @p NewL and @p OldL are equal or there is a CFG
2506
/// edge from @p OldL to @p NewL.
2507
static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL,
2508
9.83k
                                       Loop *NewL) {
2509
9.83k
  // If the loops are the same there is nothing to do.
2510
9.83k
  if (NewL == OldL)
2511
6.56k
    return Dom;
2512
3.27k
2513
3.27k
  int OldDepth = S.getRelativeLoopDepth(OldL);
2514
3.27k
  int NewDepth = S.getRelativeLoopDepth(NewL);
2515
3.27k
  // If both loops are non-affine loops there is nothing to do.
2516
3.27k
  if (OldDepth == -1 && 
NewDepth == -1473
)
2517
0
    return Dom;
2518
3.27k
2519
3.27k
  // Distinguish three cases:
2520
3.27k
  //   1) The depth is the same but the loops are not.
2521
3.27k
  //      => One loop was left one was entered.
2522
3.27k
  //   2) The depth increased from OldL to NewL.
2523
3.27k
  //      => One loop was entered, none was left.
2524
3.27k
  //   3) The depth decreased from OldL to NewL.
2525
3.27k
  //      => Loops were left were difference of the depths defines how many.
2526
3.27k
  if (OldDepth == NewDepth) {
2527
12
    assert(OldL->getParentLoop() == NewL->getParentLoop());
2528
12
    Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
2529
12
    Dom = Dom.add_dims(isl::dim::set, 1);
2530
3.25k
  } else if (OldDepth < NewDepth) {
2531
1.41k
    assert(OldDepth + 1 == NewDepth);
2532
1.41k
    auto &R = S.getRegion();
2533
1.41k
    (void)R;
2534
1.41k
    assert(NewL->getParentLoop() == OldL ||
2535
1.41k
           ((!OldL || !R.contains(OldL)) && R.contains(NewL)));
2536
1.41k
    Dom = Dom.add_dims(isl::dim::set, 1);
2537
1.84k
  } else {
2538
1.84k
    assert(OldDepth > NewDepth);
2539
1.84k
    int Diff = OldDepth - NewDepth;
2540
1.84k
    int NumDim = Dom.n_dim();
2541
1.84k
    assert(NumDim >= Diff);
2542
1.84k
    Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
2543
1.84k
  }
2544
3.27k
2545
3.27k
  return Dom;
2546
3.27k
}
2547
2548
bool Scop::propagateInvalidStmtDomains(
2549
    Region *R, DominatorTree &DT, LoopInfo &LI,
2550
2.43k
    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2551
2.43k
  ReversePostOrderTraversal<Region *> RTraversal(R);
2552
6.90k
  for (auto *RN : RTraversal) {
2553
6.90k
2554
6.90k
    // Recurse for affine subregions but go on for basic blocks and non-affine
2555
6.90k
    // subregions.
2556
6.90k
    if (RN->isSubRegion()) {
2557
1.35k
      Region *SubRegion = RN->getNodeAs<Region>();
2558
1.35k
      if (!isNonAffineSubRegion(SubRegion)) {
2559
1.25k
        propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
2560
1.25k
        continue;
2561
1.25k
      }
2562
5.65k
    }
2563
5.65k
2564
5.65k
    bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
2565
5.65k
    BasicBlock *BB = getRegionNodeBasicBlock(RN);
2566
5.65k
    isl::set &Domain = DomainMap[BB];
2567
5.65k
    assert(Domain && "Cannot propagate a nullptr");
2568
5.65k
2569
5.65k
    isl::set InvalidDomain = InvalidDomainMap[BB];
2570
5.65k
2571
5.65k
    bool IsInvalidBlock = ContainsErrorBlock || 
Domain.is_subset(InvalidDomain)5.61k
;
2572
5.65k
2573
5.65k
    if (!IsInvalidBlock) {
2574
5.49k
      InvalidDomain = InvalidDomain.intersect(Domain);
2575
5.49k
    } else {
2576
156
      InvalidDomain = Domain;
2577
156
      isl::set DomPar = Domain.params();
2578
156
      recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
2579
156
                       AS_RESTRICTION);
2580
156
      Domain = isl::set::empty(Domain.get_space());
2581
156
    }
2582
5.65k
2583
5.65k
    if (InvalidDomain.is_empty()) {
2584
4.78k
      InvalidDomainMap[BB] = InvalidDomain;
2585
4.78k
      continue;
2586
4.78k
    }
2587
864
2588
864
    auto *BBLoop = getRegionNodeLoop(RN, LI);
2589
864
    auto *TI = BB->getTerminator();
2590
864
    unsigned NumSuccs = RN->isSubRegion() ? 
17
:
TI->getNumSuccessors()857
;
2591
2.08k
    for (unsigned u = 0; u < NumSuccs; 
u++1.22k
) {
2592
1.22k
      auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
2593
1.22k
2594
1.22k
      // Skip successors outside the SCoP.
2595
1.22k
      if (!contains(SuccBB))
2596
208
        continue;
2597
1.01k
2598
1.01k
      // Skip backedges.
2599
1.01k
      if (DT.dominates(SuccBB, BB))
2600
275
        continue;
2601
742
2602
742
      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
2603
742
2604
742
      auto AdjustedInvalidDomain =
2605
742
          adjustDomainDimensions(*this, InvalidDomain, BBLoop, SuccBBLoop);
2606
742
2607
742
      isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
2608
742
      SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
2609
742
      SuccInvalidDomain = SuccInvalidDomain.coalesce();
2610
742
      unsigned NumConjucts = SuccInvalidDomain.n_basic_set();
2611
742
2612
742
      InvalidDomainMap[SuccBB] = SuccInvalidDomain;
2613
742
2614
742
      // Check if the maximal number of domain disjunctions was reached.
2615
742
      // In case this happens we will bail.
2616
742
      if (NumConjucts < MaxDisjunctsInDomain)
2617
742
        continue;
2618
0
2619
0
      InvalidDomainMap.erase(BB);
2620
0
      invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
2621
0
      return false;
2622
0
    }
2623
864
2624
864
    InvalidDomainMap[BB] = InvalidDomain;
2625
864
  }
2626
2.43k
2627
2.43k
  return true;
2628
2.43k
}
2629
2630
void Scop::propagateDomainConstraintsToRegionExit(
2631
    BasicBlock *BB, Loop *BBLoop,
2632
    SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
2633
5.68k
    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2634
5.68k
  // Check if the block @p BB is the entry of a region. If so we propagate it's
2635
5.68k
  // domain to the exit block of the region. Otherwise we are done.
2636
5.68k
  auto *RI = R.getRegionInfo();
2637
5.68k
  auto *BBReg = RI ? RI->getRegionFor(BB) : 
nullptr0
;
2638
5.68k
  auto *ExitBB = BBReg ? BBReg->getExit() : 
nullptr0
;
2639
5.68k
  if (!BBReg || BBReg->getEntry() != BB || 
!contains(ExitBB)2.14k
)
2640
4.52k
    return;
2641
1.16k
2642
1.16k
  // Do not propagate the domain if there is a loop backedge inside the region
2643
1.16k
  // that would prevent the exit block from being executed.
2644
1.16k
  auto *L = BBLoop;
2645
1.87k
  while (L && 
contains(L)1.29k
) {
2646
1.26k
    SmallVector<BasicBlock *, 4> LatchBBs;
2647
1.26k
    BBLoop->getLoopLatches(LatchBBs);
2648
1.26k
    for (auto *LatchBB : LatchBBs)
2649
1.26k
      if (BB != LatchBB && 
BBReg->contains(LatchBB)830
)
2650
554
        return;
2651
1.26k
    L = L->getParentLoop();
2652
711
  }
2653
1.16k
2654
1.16k
  isl::set Domain = DomainMap[BB];
2655
607
  assert(Domain && "Cannot propagate a nullptr");
2656
607
2657
607
  Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops());
2658
607
2659
607
  // Since the dimensions of @p BB and @p ExitBB might be different we have to
2660
607
  // adjust the domain before we can propagate it.
2661
607
  isl::set AdjustedDomain =
2662
607
      adjustDomainDimensions(*this, Domain, BBLoop, ExitBBLoop);
2663
607
  isl::set &ExitDomain = DomainMap[ExitBB];
2664
607
2665
607
  // If the exit domain is not yet created we set it otherwise we "add" the
2666
607
  // current domain.
2667
607
  ExitDomain = ExitDomain ? 
AdjustedDomain.unite(ExitDomain)30
:
AdjustedDomain577
;
2668
607
2669
607
  // Initialize the invalid domain.
2670
607
  InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());
2671
607
2672
607
  FinishedExitBlocks.insert(ExitBB);
2673
607
}
2674
2675
bool Scop::buildDomainsWithBranchConstraints(
2676
    Region *R, DominatorTree &DT, LoopInfo &LI,
2677
2.45k
    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2678
2.45k
  // To create the domain for each block in R we iterate over all blocks and
2679
2.45k
  // subregions in R and propagate the conditions under which the current region
2680
2.45k
  // element is executed. To this end we iterate in reverse post order over R as
2681
2.45k
  // it ensures that we first visit all predecessors of a region node (either a
2682
2.45k
  // basic block or a subregion) before we visit the region node itself.
2683
2.45k
  // Initially, only the domain for the SCoP region entry block is set and from
2684
2.45k
  // there we propagate the current domain to all successors, however we add the
2685
2.45k
  // condition that the successor is actually executed next.
2686
2.45k
  // As we are only interested in non-loop carried constraints here we can
2687
2.45k
  // simply skip loop back edges.
2688
2.45k
2689
2.45k
  SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
2690
2.45k
  ReversePostOrderTraversal<Region *> RTraversal(R);
2691
6.95k
  for (auto *RN : RTraversal) {
2692
6.95k
    // Recurse for affine subregions but go on for basic blocks and non-affine
2693
6.95k
    // subregions.
2694
6.95k
    if (RN->isSubRegion()) {
2695
1.36k
      Region *SubRegion = RN->getNodeAs<Region>();
2696
1.36k
      if (!isNonAffineSubRegion(SubRegion)) {
2697
1.27k
        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
2698
1.27k
                                               InvalidDomainMap))
2699
5
          return false;
2700
1.26k
        continue;
2701
1.26k
      }
2702
1.36k
    }
2703
5.68k
2704
5.68k
    if (containsErrorBlock(RN, getRegion(), LI, DT))
2705
37
      HasErrorBlock = true;
2706
5.68k
2707
5.68k
    BasicBlock *BB = getRegionNodeBasicBlock(RN);
2708
5.68k
    Instruction *TI = BB->getTerminator();
2709
5.68k
2710
5.68k
    if (isa<UnreachableInst>(TI))
2711
0
      continue;
2712
5.68k
2713
5.68k
    isl::set Domain = DomainMap.lookup(BB);
2714
5.68k
    if (!Domain)
2715
0
      continue;
2716
5.68k
    MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain.get()));
2717
5.68k
2718
5.68k
    auto *BBLoop = getRegionNodeLoop(RN, LI);
2719
5.68k
    // Propagate the domain from BB directly to blocks that have a superset
2720
5.68k
    // domain, at the moment only region exit nodes of regions that start in BB.
2721
5.68k
    propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
2722
5.68k
                                           InvalidDomainMap);
2723
5.68k
2724
5.68k
    // If all successors of BB have been set a domain through the propagation
2725
5.68k
    // above we do not need to build condition sets but can just skip this
2726
5.68k
    // block. However, it is important to note that this is a local property
2727
5.68k
    // with regards to the region @p R. To this end FinishedExitBlocks is a
2728
5.68k
    // local variable.
2729
5.85k
    auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
2730
5.85k
      return FinishedExitBlocks.count(SuccBB);
2731
5.85k
    };
2732
5.68k
    if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
2733
306
      continue;
2734
5.37k
2735
5.37k
    // Build the condition sets for the successor nodes of the current region
2736
5.37k
    // node. If it is a non-affine subregion we will always execute the single
2737
5.37k
    // exit node, hence the single entry node domain is the condition set. For
2738
5.37k
    // basic blocks we use the helper function buildConditionSets.
2739
5.37k
    SmallVector<isl_set *, 8> ConditionSets;
2740
5.37k
    if (RN->isSubRegion())
2741
99
      ConditionSets.push_back(Domain.copy());
2742
5.27k
    else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain.get(),
2743
5.27k
                                 InvalidDomainMap, ConditionSets))
2744
5
      return false;
2745
5.37k
2746
5.37k
    // Now iterate over the successors and set their initial domain based on
2747
5.37k
    // their condition set. We skip back edges here and have to be careful when
2748
5.37k
    // we leave a loop not to keep constraints over a dimension that doesn't
2749
5.37k
    // exist anymore.
2750
5.37k
    assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
2751
12.9k
    for (unsigned u = 0, e = ConditionSets.size(); u < e; 
u++7.53k
) {
2752
7.53k
      isl::set CondSet = isl::manage(ConditionSets[u]);
2753
7.53k
      BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
2754
7.53k
2755
7.53k
      // Skip blocks outside the region.
2756
7.53k
      if (!contains(SuccBB))
2757
1.34k
        continue;
2758
6.19k
2759
6.19k
      // If we propagate the domain of some block to "SuccBB" we do not have to
2760
6.19k
      // adjust the domain.
2761
6.19k
      if (FinishedExitBlocks.count(SuccBB))
2762
537
        continue;
2763
5.65k
2764
5.65k
      // Skip back edges.
2765
5.65k
      if (DT.dominates(SuccBB, BB))
2766
1.69k
        continue;
2767
3.95k
2768
3.95k
      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
2769
3.95k
2770
3.95k
      CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop);
2771
3.95k
2772
3.95k
      // Set the domain for the successor or merge it with an existing domain in
2773
3.95k
      // case there are multiple paths (without loop back edges) to the
2774
3.95k
      // successor block.
2775
3.95k
      isl::set &SuccDomain = DomainMap[SuccBB];
2776
3.95k
2777
3.95k
      if (SuccDomain) {
2778
27
        SuccDomain = SuccDomain.unite(CondSet).coalesce();
2779
3.93k
      } else {
2780
3.93k
        // Initialize the invalid domain.
2781
3.93k
        InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
2782
3.93k
        SuccDomain = CondSet;
2783
3.93k
      }
2784
3.95k
2785
3.95k
      SuccDomain = SuccDomain.detect_equalities();
2786
3.95k
2787
3.95k
      // Check if the maximal number of domain disjunctions was reached.
2788
3.95k
      // In case this happens we will clean up and bail.
2789
3.95k
      if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
2790
3.95k
        continue;
2791
0
2792
0
      invalidate(COMPLEXITY, DebugLoc());
2793
0
      while (++u < ConditionSets.size())
2794
0
        isl_set_free(ConditionSets[u]);
2795
0
      return false;
2796
0
    }
2797
5.37k
  }
2798
2.45k
2799
2.45k
  
return true2.44k
;
2800
2.45k
}
2801
2802
isl::set Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain,
2803
                                               DominatorTree &DT,
2804
5.65k
                                               LoopInfo &LI) {
2805
5.65k
  // If @p BB is the ScopEntry we are done
2806
5.65k
  if (R.getEntry() == BB)
2807
1.17k
    return isl::set::universe(Domain.get_space());
2808
4.47k
2809
4.47k
  // The region info of this function.
2810
4.47k
  auto &RI = *R.getRegionInfo();
2811
4.47k
2812
4.47k
  Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops());
2813
4.47k
2814
4.47k
  // A domain to collect all predecessor domains, thus all conditions under
2815
4.47k
  // which the block is executed. To this end we start with the empty domain.
2816
4.47k
  isl::set PredDom = isl::set::empty(Domain.get_space());
2817
4.47k
2818
4.47k
  // Set of regions of which the entry block domain has been propagated to BB.
2819
4.47k
  // all predecessors inside any of the regions can be skipped.
2820
4.47k
  SmallSet<Region *, 8> PropagatedRegions;
2821
4.47k
2822
5.54k
  for (auto *PredBB : predecessors(BB)) {
2823
5.54k
    // Skip backedges.
2824
5.54k
    if (DT.dominates(BB, PredBB))
2825
694
      continue;
2826
4.84k
2827
4.84k
    // If the predecessor is in a region we used for propagation we can skip it.
2828
4.84k
    auto PredBBInRegion = [PredBB](Region *PR) 
{ return PR->contains(PredBB); }370
;
2829
4.84k
    if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(),
2830
4.84k
                    PredBBInRegion)) {
2831
319
      continue;
2832
319
    }
2833
4.52k
2834
4.52k
    // Check if there is a valid region we can use for propagation, thus look
2835
4.52k
    // for a region that contains the predecessor and has @p BB as exit block.
2836
4.52k
    auto *PredR = RI.getRegionFor(PredBB);
2837
4.52k
    while (PredR->getExit() != BB && 
!PredR->contains(BB)3.33k
)
2838
0
      PredR->getParent();
2839
4.52k
2840
4.52k
    // If a valid region for propagation was found use the entry of that region
2841
4.52k
    // for propagation, otherwise the PredBB directly.
2842
4.52k
    if (PredR->getExit() == BB) {
2843
1.19k
      PredBB = PredR->getEntry();
2844
1.19k
      PropagatedRegions.insert(PredR);
2845
1.19k
    }
2846
4.52k
2847
4.52k
    isl::set PredBBDom = getDomainConditions(PredBB);
2848
4.52k
    Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
2849
4.52k
    PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
2850
4.52k
    PredDom = PredDom.unite(PredBBDom);
2851
4.52k
  }
2852
4.47k
2853
4.47k
  return PredDom;
2854
4.47k
}
2855
2856
bool Scop::propagateDomainConstraints(
2857
    Region *R, DominatorTree &DT, LoopInfo &LI,
2858
2.43k
    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2859
2.43k
  // Iterate over the region R and propagate the domain constrains from the
2860
2.43k
  // predecessors to the current node. In contrast to the
2861
2.43k
  // buildDomainsWithBranchConstraints function, this one will pull the domain
2862
2.43k
  // information from the predecessors instead of pushing it to the successors.
2863
2.43k
  // Additionally, we assume the domains to be already present in the domain
2864
2.43k
  // map here. However, we iterate again in reverse post order so we know all
2865
2.43k
  // predecessors have been visited before a block or non-affine subregion is
2866
2.43k
  // visited.
2867
2.43k
2868
2.43k
  ReversePostOrderTraversal<Region *> RTraversal(R);
2869
6.90k
  for (auto *RN : RTraversal) {
2870
6.90k
    // Recurse for affine subregions but go on for basic blocks and non-affine
2871
6.90k
    // subregions.
2872
6.90k
    if (RN->isSubRegion()) {
2873
1.35k
      Region *SubRegion = RN->getNodeAs<Region>();
2874
1.35k
      if (!isNonAffineSubRegion(SubRegion)) {
2875
1.25k
        if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap))
2876
0
          return false;
2877
1.25k
        continue;
2878
1.25k
      }
2879
1.35k
    }
2880
5.65k
2881
5.65k
    BasicBlock *BB = getRegionNodeBasicBlock(RN);
2882
5.65k
    isl::set &Domain = DomainMap[BB];
2883
5.65k
    assert(Domain);
2884
5.65k
2885
5.65k
    // Under the union of all predecessor conditions we can reach this block.
2886
5.65k
    isl::set PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI);
2887
5.65k
    Domain = Domain.intersect(PredDom).coalesce();
2888
5.65k
    Domain = Domain.align_params(getParamSpace());
2889
5.65k
2890
5.65k
    Loop *BBLoop = getRegionNodeLoop(RN, LI);
2891
5.65k
    if (BBLoop && 
BBLoop->getHeader() == BB4.89k
&&
contains(BBLoop)1.70k
)
2892
1.69k
      if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
2893
0
        return false;
2894
5.65k
  }
2895
2.43k
2896
2.43k
  return true;
2897
2.43k
}
2898
2899
/// Create a map to map from a given iteration to a subsequent iteration.
2900
///
2901
/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
2902
/// is incremented by one and all other dimensions are equal, e.g.,
2903
///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
2904
///
2905
/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
2906
1.69k
static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
2907
1.69k
  isl::space MapSpace = SetSpace.map_from_set();
2908
1.69k
  isl::map NextIterationMap = isl::map::universe(MapSpace);
2909
3.95k
  for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); 
u++2.26k
)
2910
2.26k
    if (u != Dim)
2911
571
      NextIterationMap =
2912
571
          NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
2913
1.69k
  isl::constraint C =
2914
1.69k
      isl::constraint::alloc_equality(isl::local_space(MapSpace));
2915
1.69k
  C = C.set_constant_si(1);
2916
1.69k
  C = C.set_coefficient_si(isl::dim::in, Dim, 1);
2917
1.69k
  C = C.set_coefficient_si(isl::dim::out, Dim, -1);
2918
1.69k
  NextIterationMap = NextIterationMap.add_constraint(C);
2919
1.69k
  return NextIterationMap;
2920
1.69k
}
2921
2922
bool Scop::addLoopBoundsToHeaderDomain(
2923
1.69k
    Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2924
1.69k
  int LoopDepth = getRelativeLoopDepth(L);
2925
1.69k
  assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
2926
1.69k
2927
1.69k
  BasicBlock *HeaderBB = L->getHeader();
2928
1.69k
  assert(DomainMap.count(HeaderBB));
2929
1.69k
  isl::set &HeaderBBDom = DomainMap[HeaderBB];
2930
1.69k
2931
1.69k
  isl::map NextIterationMap =
2932
1.69k
      createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
2933
1.69k
2934
1.69k
  isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
2935
1.69k
2936
1.69k
  SmallVector<BasicBlock *, 4> LatchBlocks;
2937
1.69k
  L->getLoopLatches(LatchBlocks);
2938
1.69k
2939
1.69k
  for (BasicBlock *LatchBB : LatchBlocks) {
2940
1.69k
    // If the latch is only reachable via error statements we skip it.
2941
1.69k
    isl::set LatchBBDom = DomainMap.lookup(LatchBB);
2942
1.69k
    if (!LatchBBDom)
2943
0
      continue;
2944
1.69k
2945
1.69k
    isl::set BackedgeCondition = nullptr;
2946
1.69k
2947
1.69k
    Instruction *TI = LatchBB->getTerminator();
2948
1.69k
    BranchInst *BI = dyn_cast<BranchInst>(TI);
2949
1.69k
    assert(BI && "Only branch instructions allowed in loop latches");
2950
1.69k
2951
1.69k
    if (BI->isUnconditional())
2952
937
      BackedgeCondition = LatchBBDom;
2953
758
    else {
2954
758
      SmallVector<isl_set *, 8> ConditionSets;
2955
758
      int idx = BI->getSuccessor(0) != HeaderBB;
2956
758
      if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom.get(),
2957
758
                              InvalidDomainMap, ConditionSets))
2958
0
        return false;
2959
758
2960
758
      // Free the non back edge condition set as we do not need it.
2961
758
      isl_set_free(ConditionSets[1 - idx]);
2962
758
2963
758
      BackedgeCondition = isl::manage(ConditionSets[idx]);
2964
758
    }
2965
1.69k
2966
1.69k
    int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
2967
1.69k
    assert(LatchLoopDepth >= LoopDepth);
2968
1.69k
    BackedgeCondition = BackedgeCondition.project_out(
2969
1.69k
        isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
2970
1.69k
    UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
2971
1.69k
  }
2972
1.69k
2973
1.69k
  isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
2974
2.26k
  for (int i = 0; i < LoopDepth; 
i++571
)
2975
571
    ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
2976
1.69k
2977
1.69k
  isl::set UnionBackedgeConditionComplement =
2978
1.69k
      UnionBackedgeCondition.complement();
2979
1.69k
  UnionBackedgeConditionComplement =
2980
1.69k
      UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
2981
1.69k
                                                      0);
2982
1.69k
  UnionBackedgeConditionComplement =
2983
1.69k
      UnionBackedgeConditionComplement.apply(ForwardMap);
2984
1.69k
  HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
2985
1.69k
  HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
2986
1.69k
2987
1.69k
  auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
2988
1.69k
  HeaderBBDom = Parts.second;
2989
1.69k
2990
1.69k
  // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
2991
1.69k
  // the bounded assumptions to the context as they are already implied by the
2992
1.69k
  // <nsw> tag.
2993
1.69k
  if (Affinator.hasNSWAddRecForLoop(L))
2994
1.31k
    return true;
2995
383
2996
383
  isl::set UnboundedCtx = Parts.first.params();
2997
383
  recordAssumption(INFINITELOOP, UnboundedCtx,
2998
383
                   HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
2999
383
  return true;
3000
383
}
3001
3002
1.33k
MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
3003
1.33k
  Value *PointerBase = MA->getOriginalBaseAddr();
3004
1.33k
3005
1.33k
  auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
3006
1.33k
  if (!PointerBaseInst)
3007
1.11k
    return nullptr;
3008
221
3009
221
  auto *BasePtrStmt = getStmtFor(PointerBaseInst);
3010
221
  if (!BasePtrStmt)
3011
221
    return nullptr;
3012
0
3013
0
  return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
3014
0
}
3015
3016
bool Scop::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
3017
486
                                        isl::union_map Writes) {
3018
486
  if (auto *BasePtrMA = lookupBasePtrAccess(MA)) {
3019
0
    return getNonHoistableCtx(BasePtrMA, Writes).is_null();
3020
0
  }
3021
486
3022
486
  Value *BaseAddr = MA->getOriginalBaseAddr();
3023
486
  if (auto *BasePtrInst = dyn_cast<Instruction>(BaseAddr))
3024
115
    if (!isa<LoadInst>(BasePtrInst))
3025
36
      return contains(BasePtrInst);
3026
450
3027
450
  return false;
3028
450
}
3029
3030
1.15k
bool Scop::buildAliasChecks(AliasAnalysis &AA) {
3031
1.15k
  if (!PollyUseRuntimeAliasChecks)
3032
21
    return true;
3033
1.13k
3034
1.13k
  if (buildAliasGroups(AA)) {
3035
1.13k
    // Aliasing assumptions do not go through addAssumption but we still want to
3036
1.13k
    // collect statistics so we do it here explicitly.
3037
1.13k
    if (MinMaxAliasGroups.size())
3038
203
      AssumptionsAliasing++;
3039
1.13k
    return true;
3040
1.13k
  }
3041
6
3042
6
  // If a problem occurs while building the alias groups we need to delete
3043
6
  // this SCoP and pretend it wasn't valid in the first place. To this end
3044
6
  // we make the assumed context infeasible.
3045
6
  invalidate(ALIASING, DebugLoc());
3046
6
3047
6
  LLVM_DEBUG(
3048
6
      dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()
3049
6
             << " could not be created as the number of parameters involved "
3050
6
                "is too high. The SCoP will be "
3051
6
                "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
3052
6
                "the maximal number of parameters but be advised that the "
3053
6
                "compile time might increase exponentially.\n\n");
3054
6
  return false;
3055
6
}
3056
3057
std::tuple<Scop::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
3058
1.13k
Scop::buildAliasGroupsForAccesses(AliasAnalysis &AA) {
3059
1.13k
  AliasSetTracker AST(AA);
3060
1.13k
3061
1.13k
  DenseMap<Value *, MemoryAccess *> PtrToAcc;
3062
1.13k
  DenseSet<const ScopArrayInfo *> HasWriteAccess;
3063
2.24k
  for (ScopStmt &Stmt : *this) {
3064
2.24k
3065
2.24k
    isl::set StmtDomain = Stmt.getDomain();
3066
2.24k
    bool StmtDomainEmpty = StmtDomain.is_empty();
3067
2.24k
3068
2.24k
    // Statements with an empty domain will never be executed.
3069
2.24k
    if (StmtDomainEmpty)
3070
4
      continue;
3071
2.24k
3072
4.56k
    
for (MemoryAccess *MA : Stmt)2.24k
{
3073
4.56k
      if (MA->isScalarKind())
3074
1.31k
        continue;
3075
3.25k
      if (!MA->isRead())
3076
1.67k
        HasWriteAccess.insert(MA->getScopArrayInfo());
3077
3.25k
      MemAccInst Acc(MA->getAccessInstruction());
3078
3.25k
      if (MA->isRead() && 
isa<MemTransferInst>(Acc)1.57k
)
3079
7
        PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
3080
3.24k
      else
3081
3.24k
        PtrToAcc[Acc.getPointerOperand()] = MA;
3082
3.25k
      AST.add(Acc);
3083
3.25k
    }
3084
2.24k
  }
3085
1.13k
3086
1.13k
  AliasGroupVectorTy AliasGroups;
3087
1.51k
  for (AliasSet &AS : AST) {
3088
1.51k
    if (AS.isMustAlias() || 
AS.isForwardingAliasSet()373
)
3089
1.14k
      continue;
3090
373
    AliasGroupTy AG;
3091
373
    for (auto &PR : AS)
3092
1.37k
      AG.push_back(PtrToAcc[PR.getValue()]);
3093
373
    if (AG.size() < 2)
3094
8
      continue;
3095
365
    AliasGroups.push_back(std::move(AG));
3096
365
  }
3097
1.13k
3098
1.13k
  return std::make_tuple(AliasGroups, HasWriteAccess);
3099
1.13k
}
3100
3101
1.13k
void Scop::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
3102
1.50k
  for (unsigned u = 0; u < AliasGroups.size(); 
u++373
) {
3103
373
    AliasGroupTy NewAG;
3104
373
    AliasGroupTy &AG = AliasGroups[u];
3105
373
    AliasGroupTy::iterator AGI = AG.begin();
3106
373
    isl::set AGDomain = getAccessDomain(*AGI);
3107
1.76k
    while (AGI != AG.end()) {
3108
1.39k
      MemoryAccess *MA = *AGI;
3109
1.39k
      isl::set MADomain = getAccessDomain(MA);
3110
1.39k
      if (AGDomain.is_disjoint(MADomain)) {
3111
26
        NewAG.push_back(MA);
3112
26
        AGI = AG.erase(AGI);
3113
1.36k
      } else {
3114
1.36k
        AGDomain = AGDomain.unite(MADomain);
3115
1.36k
        AGI++;
3116
1.36k
      }
3117
1.39k
    }
3118
373
    if (NewAG.size() > 1)
3119
8
      AliasGroups.push_back(std::move(NewAG));
3120
373
  }
3121
1.13k
}
3122
3123
1.13k
bool Scop::buildAliasGroups(AliasAnalysis &AA) {
3124
1.13k
  // To create sound alias checks we perform the following steps:
3125
1.13k
  //   o) We partition each group into read only and non read only accesses.
3126
1.13k
  //   o) For each group with more than one base pointer we then compute minimal
3127
1.13k
  //      and maximal accesses to each array of a group in read only and non
3128
1.13k
  //      read only partitions separately.
3129
1.13k
  AliasGroupVectorTy AliasGroups;
3130
1.13k
  DenseSet<const ScopArrayInfo *> HasWriteAccess;
3131
1.13k
3132
1.13k
  std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(AA);
3133
1.13k
3134
1.13k
  splitAliasGroupsByDomain(AliasGroups);
3135
1.13k
3136
1.13k
  for (AliasGroupTy &AG : AliasGroups) {
3137
372
    if (!hasFeasibleRuntimeContext())
3138
1
      return false;
3139
371
3140
371
    {
3141
371
      IslMaxOperationsGuard MaxOpGuard(getIslCtx().get(), OptComputeOut);
3142
371
      bool Valid = buildAliasGroup(AG, HasWriteAccess);
3143
371
      if (!Valid)
3144
5
        return false;
3145
366
    }
3146
366
    if (isl_ctx_last_error(getIslCtx().get()) == isl_error_quota) {
3147
0
      invalidate(COMPLEXITY, DebugLoc());
3148
0
      return false;
3149
0
    }
3150
366
  }
3151
1.13k
3152
1.13k
  
return true1.13k
;
3153
1.13k
}
3154
3155
bool Scop::buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
3156
371
                           DenseSet<const ScopArrayInfo *> HasWriteAccess) {
3157
371
  AliasGroupTy ReadOnlyAccesses;
3158
371
  AliasGroupTy ReadWriteAccesses;
3159
371
  SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
3160
371
  SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
3161
371
3162
371
  if (AliasGroup.size() < 2)
3163
4
    return true;
3164
367
3165
1.35k
  
for (MemoryAccess *Access : AliasGroup)367
{
3166
1.35k
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias",
3167
1.35k
                                        Access->getAccessInstruction())
3168
1.35k
             << "Possibly aliasing pointer, use restrict keyword.");
3169
1.35k
    const ScopArrayInfo *Array = Access->getScopArrayInfo();
3170
1.35k
    if (HasWriteAccess.count(Array)) {
3171
889
      ReadWriteArrays.insert(Array);
3172
889
      ReadWriteAccesses.push_back(Access);
3173
889
    } else {
3174
466
      ReadOnlyArrays.insert(Array);
3175
466
      ReadOnlyAccesses.push_back(Access);
3176
466
    }
3177
1.35k
  }
3178
367
3179
367
  // If there are no read-only pointers, and less than two read-write pointers,
3180
367
  // no alias check is needed.
3181
367
  if (ReadOnlyAccesses.empty() && 
ReadWriteArrays.size() <= 1187
)
3182
144
    return true;
3183
223
3184
223
  // If there is no read-write pointer, no alias check is needed.
3185
223
  if (ReadWriteArrays.empty())
3186
9
    return true;
3187
214
3188
214
  // For non-affine accesses, no alias check can be generated as we cannot
3189
214
  // compute a sufficiently tight lower and upper bound: bail out.
3190
846
  
for (MemoryAccess *MA : AliasGroup)214
{
3191
846
    if (!MA->isAffine()) {
3192
0
      invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
3193
0
                 MA->getAccessInstruction()->getParent());
3194
0
      return false;
3195
0
    }
3196
846
  }
3197
214
3198
214
  // Ensure that for all memory accesses for which we generate alias checks,
3199
214
  // their base pointers are available.
3200
846
  
for (MemoryAccess *MA : AliasGroup)214
{
3201
846
    if (MemoryAccess *BasePtrMA = lookupBasePtrAccess(MA))
3202
0
      addRequiredInvariantLoad(
3203
0
          cast<LoadInst>(BasePtrMA->getAccessInstruction()));
3204
846
  }
3205
214
3206
214
  MinMaxAliasGroups.emplace_back();
3207
214
  MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
3208
214
  MinMaxVectorTy &MinMaxAccessesReadWrite = pair.first;
3209
214
  MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
3210
214
3211
214
  bool Valid;
3212
214
3213
214
  Valid =
3214
214
      calculateMinMaxAccess(ReadWriteAccesses, *this, MinMaxAccessesReadWrite);
3215
214
3216
214
  if (!Valid)
3217
0
    return false;
3218
214
3219
214
  // Bail out if the number of values we need to compare is too large.
3220
214
  // This is important as the number of comparisons grows quadratically with
3221
214
  // the number of values we need to compare.
3222
214
  if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
3223
214
      RunTimeChecksMaxArraysPerGroup)
3224
1
    return false;
3225
213
3226
213
  Valid =
3227
213
      calculateMinMaxAccess(ReadOnlyAccesses, *this, MinMaxAccessesReadOnly);
3228
213
3229
213
  if (!Valid)
3230
4
    return false;
3231
209
3232
209
  return true;
3233
209
}
3234
3235
/// Get the smallest loop that contains @p S but is not in @p S.
3236
3.53k
static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
3237
3.53k
  // Start with the smallest loop containing the entry and expand that
3238
3.53k
  // loop until it contains all blocks in the region. If there is a loop
3239
3.53k
  // containing all blocks in the region check if it is itself contained
3240
3.53k
  // and if so take the parent loop as it will be the smallest containing
3241
3.53k
  // the region but not contained by it.
3242
3.53k
  Loop *L = LI.getLoopFor(S.getEntry());
3243
4.66k
  while (L) {
3244
3.11k
    bool AllContained = true;
3245
3.11k
    for (auto *BB : S.blocks())
3246
25.1k
      AllContained &= L->contains(BB);
3247
3.11k
    if (AllContained)
3248
1.99k
      break;
3249
1.12k
    L = L->getParentLoop();
3250
1.12k
  }
3251
3.53k
3252
3.53k
  return L ? 
(S.contains(L) 1.99k
?
L->getParentLoop()1.83k
:
L158
) :
nullptr1.54k
;
3253
3.53k
}
3254
3255
int Scop::NextScopID = 0;
3256
3257
std::string Scop::CurrentFunc;
3258
3259
1.20k
int Scop::getNextID(std::string ParentFunc) {
3260
1.20k
  if (ParentFunc != CurrentFunc) {
3261
1.18k
    CurrentFunc = ParentFunc;
3262
1.18k
    NextScopID = 0;
3263
1.18k
  }
3264
1.20k
  return NextScopID++;
3265
1.20k
}
3266
3267
Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
3268
           DominatorTree &DT, ScopDetection::DetectionContext &DC,
3269
           OptimizationRemarkEmitter &ORE)
3270
    : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
3271
      R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
3272
      ORE(ORE), Affinator(this, LI),
3273
1.20k
      ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
3274
1.20k
  if (IslOnErrorAbort)
3275
1.20k
    isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT);
3276
1.20k
  buildContext();
3277
1.20k
}
3278
3279
1.17k
Scop::~Scop() = default;
3280
3281
1.15k
void Scop::foldSizeConstantsToRight() {
3282
1.15k
  isl::union_set Accessed = getAccesses().range();
3283
1.15k
3284
2.46k
  for (auto Array : arrays()) {
3285
2.46k
    if (Array->getNumberOfDimensions() <= 1)
3286
2.18k
      continue;
3287
281
3288
281
    isl::space Space = Array->getSpace();
3289
281
    Space = Space.align_params(Accessed.get_space());
3290
281
3291
281
    if (!Accessed.contains(Space))
3292
0
      continue;
3293
281
3294
281
    isl::set Elements = Accessed.extract_set(Space);
3295
281
    isl::map Transform = isl::map::universe(Array->getSpace().map_from_set());
3296
281
3297
281
    std::vector<int> Int;
3298
281
    int Dims = Elements.dim(isl::dim::set);
3299
927
    for (int i = 0; i < Dims; 
i++646
) {
3300
646
      isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i);
3301
646
      DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1);
3302
646
      DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0);
3303
646
3304
646
      isl::basic_set DimHull = DimOnly.affine_hull();
3305
646
3306
646
      if (i == Dims - 1) {
3307
281
        Int.push_back(1);
3308
281
        Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
3309
281
        continue;
3310
281
      }
3311
365
3312
365
      if (DimHull.dim(isl::dim::div) == 1) {
3313
5
        isl::aff Diff = DimHull.get_div(0);
3314
5
        isl::val Val = Diff.get_denominator_val();
3315
5
3316
5
        int ValInt = 1;
3317
5
        if (Val.is_int()) {
3318
5
          auto ValAPInt = APIntFromVal(Val);
3319
5
          if (ValAPInt.isSignedIntN(32))
3320
4
            ValInt = ValAPInt.getSExtValue();
3321
5
        } else {
3322
0
        }
3323
5
3324
5
        Int.push_back(ValInt);
3325
5
        isl::constraint C = isl::constraint::alloc_equality(
3326
5
            isl::local_space(Transform.get_space()));
3327
5
        C = C.set_coefficient_si(isl::dim::out, i, ValInt);
3328
5
        C = C.set_coefficient_si(isl::dim::in, i, -1);
3329
5
        Transform = Transform.add_constraint(C);
3330
5
        continue;
3331
5
      }
3332
360
3333
360
      isl::basic_set ZeroSet = isl::basic_set(DimHull);
3334
360
      ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0);
3335
360
3336
360
      int ValInt = 1;
3337
360
      if (ZeroSet.is_equal(DimHull)) {
3338
11
        ValInt = 0;
3339
11
      }
3340
360
3341
360
      Int.push_back(ValInt);
3342
360
      Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
3343
360
    }
3344
281
3345
281
    isl::set MappedElements = isl::map(Transform).domain();
3346
281
    if (!Elements.is_subset(MappedElements))
3347
0
      continue;
3348
281
3349
281
    bool CanFold = true;
3350
281
    if (Int[0] <= 1)
3351
277
      CanFold = false;
3352
281
3353
281
    unsigned NumDims = Array->getNumberOfDimensions();
3354
365
    for (unsigned i = 1; i < NumDims - 1; 
i++84
)
3355
84
      if (Int[0] != Int[i] && 
Int[i]3
)
3356
1
        CanFold = false;
3357
281
3358
281
    if (!CanFold)
3359
277
      continue;
3360
4
3361
4
    for (auto &Access : AccessFunctions)
3362
60
      if (Access->getScopArrayInfo() == Array)
3363
15
        Access->setAccessRelation(
3364
15
            Access->getAccessRelation().apply_range(Transform));
3365
4
3366
4
    std::vector<const SCEV *> Sizes;
3367
12
    for (unsigned i = 0; i < NumDims; 
i++8
) {
3368
8
      auto Size = Array->getDimensionSize(i);
3369
8
3370
8
      if (i == NumDims - 1)
3371
4
        Size = SE->getMulExpr(Size, SE->getConstant(Size->getType(), Int[0]));
3372
8
      Sizes.push_back(Size);
3373
8
    }
3374
4
3375
4
    Array->updateSizes(Sizes, false /* CheckConsistency */);
3376
4
  }
3377
1.15k
}
3378
3379
1.15k
void Scop::markFortranArrays() {
3380
2.30k
  for (ScopStmt &Stmt : Stmts) {
3381
4.70k
    for (MemoryAccess *MemAcc : Stmt) {
3382
4.70k
      Value *FAD = MemAcc->getFortranArrayDescriptor();
3383
4.70k
      if (!FAD)
3384
4.69k
        continue;
3385
10
3386
10
      // TODO: const_cast-ing to edit
3387
10
      ScopArrayInfo *SAI =
3388
10
          const_cast<ScopArrayInfo *>(MemAcc->getLatestScopArrayInfo());
3389
10
      assert(SAI && "memory access into a Fortran array does not "
3390
10
                    "have an associated ScopArrayInfo");
3391
10
      SAI->applyAndSetFAD(FAD);
3392
10
    }
3393
2.30k
  }
3394
1.15k
}
3395
3396
1.15k
void Scop::finalizeAccesses() {
3397
1.15k
  updateAccessDimensionality();
3398
1.15k
  foldSizeConstantsToRight();
3399
1.15k
  foldAccessRelations();
3400
1.15k
  assumeNoOutOfBounds();
3401
1.15k
  markFortranArrays();
3402
1.15k
}
3403
3404
1.15k
void Scop::updateAccessDimensionality() {
3405
1.15k
  // Check all array accesses for each base pointer and find a (virtual) element
3406
1.15k
  // size for the base pointer that divides all access functions.
3407
1.15k
  for (ScopStmt &Stmt : *this)
3408
4.70k
    
for (MemoryAccess *Access : Stmt)2.30k
{
3409
4.70k
      if (!Access->isArrayKind())
3410
1.31k
        continue;
3411
3.39k
      ScopArrayInfo *Array =
3412
3.39k
          const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
3413
3.39k
3414
3.39k
      if (Array->getNumberOfDimensions() != 1)
3415
436
        continue;
3416
2.95k
      unsigned DivisibleSize = Array->getElemSizeInBytes();
3417
2.95k
      const SCEV *Subscript = Access->getSubscript(0);
3418
2.95k
      while (!isDivisible(Subscript, DivisibleSize, *SE))
3419
2
        DivisibleSize /= 2;
3420
2.95k
      auto *Ty = IntegerType::get(SE->getContext(), DivisibleSize * 8);
3421
2.95k
      Array->updateElementType(Ty);
3422
2.95k
    }
3423
1.15k
3424
1.15k
  for (auto &Stmt : *this)
3425
2.30k
    for (auto &Access : Stmt)
3426
4.70k
      Access->updateDimensionality();
3427
1.15k
}
3428
3429
1.15k
void Scop::foldAccessRelations() {
3430
1.15k
  for (auto &Stmt : *this)
3431
2.30k
    for (auto &Access : Stmt)
3432
4.70k
      Access->foldAccessRelation();
3433
1.15k
}
3434
3435
1.15k
void Scop::assumeNoOutOfBounds() {
3436
1.15k
  for (auto &Stmt : *this)
3437
2.30k
    for (auto &Access : Stmt)
3438
4.70k
      Access->assumeNoOutOfBound();
3439
1.15k
}
3440
3441
6.95k
void Scop::removeFromStmtMap(ScopStmt &Stmt) {
3442
6.95k
  for (Instruction *Inst : Stmt.getInstructions())
3443
2.15k
    InstStmtMap.erase(Inst);
3444
6.95k
3445
6.95k
  if (Stmt.isRegionStmt()) {
3446
44
    for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
3447
44
      StmtMap.erase(BB);
3448
44
      // Skip entry basic block, as its instructions are already deleted as
3449
44
      // part of the statement's instruction list.
3450
44
      if (BB == Stmt.getEntryBlock())
3451
17
        continue;
3452
27
      for (Instruction &Inst : *BB)
3453
60
        InstStmtMap.erase(&Inst);
3454
27
    }
3455
6.93k
  } else {
3456
6.93k
    auto StmtMapIt = StmtMap.find(Stmt.getBasicBlock());
3457
6.93k
    if (StmtMapIt != StmtMap.end())
3458
6.93k
      StmtMapIt->second.erase(std::remove(StmtMapIt->second.begin(),
3459
6.93k
                                          StmtMapIt->second.end(), &Stmt),
3460
6.93k
                              StmtMapIt->second.end());
3461
6.93k
    for (Instruction *Inst : Stmt.getInstructions())
3462
2.12k
      InstStmtMap.erase(Inst);
3463
6.93k
  }
3464
6.95k
}
3465
3466
void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete,
3467
3.58k
                       bool AfterHoisting) {
3468
23.9k
  for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
3469
20.3k
    if (!ShouldDelete(*StmtIt)) {
3470
13.3k
      StmtIt++;
3471
13.3k
      continue;
3472
13.3k
    }
3473
6.95k
3474
6.95k
    // Start with removing all of the statement's accesses including erasing it
3475
6.95k
    // from all maps that are pointing to them.
3476
6.95k
    // Make a temporary copy because removing MAs invalidates the iterator.
3477
6.95k
    SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());
3478
6.95k
    for (MemoryAccess *MA : MAList)
3479
189
      StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);
3480
6.95k
3481
6.95k
    removeFromStmtMap(*StmtIt);
3482
6.95k
    StmtIt = Stmts.erase(StmtIt);
3483
6.95k
  }
3484
3.58k
}
3485
3486
1.19k
void Scop::removeStmtNotInDomainMap() {
3487
9.10k
  auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
3488
9.10k
    isl::set Domain = DomainMap.lookup(Stmt.getEntryBlock());
3489
9.10k
    if (!Domain)
3490
0
      return true;
3491
9.10k
    return Domain.is_empty();
3492
9.10k
  };
3493
1.19k
  removeStmts(ShouldDelete, false);
3494
1.19k
}
3495
3496
2.38k
void Scop::simplifySCoP(bool AfterHoisting) {
3497
11.2k
  auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
3498
11.2k
    // Never delete statements that contain calls to debug functions.
3499
11.2k
    if (hasDebugCall(&Stmt))
3500
2
      return false;
3501
11.2k
3502
11.2k
    bool RemoveStmt = Stmt.isEmpty();
3503
11.2k
3504
11.2k
    // Remove read only statements only after invariant load hoisting.
3505
11.2k
    if (!RemoveStmt && 
AfterHoisting4.58k
) {
3506
2.26k
      bool OnlyRead = true;
3507
3.72k
      for (MemoryAccess *MA : Stmt) {
3508
3.72k
        if (MA->isRead())
3509
1.51k
          continue;
3510
2.21k
3511
2.21k
        OnlyRead = false;
3512
2.21k
        break;
3513
2.21k
      }
3514
2.26k
3515
2.26k
      RemoveStmt = OnlyRead;
3516
2.26k
    }
3517
11.2k
    return RemoveStmt;
3518
11.2k
  };
3519
2.38k
3520
2.38k
  removeStmts(ShouldDelete, AfterHoisting);
3521
2.38k
}
3522
3523
5.80k
InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {
3524
5.80k
  LoadInst *LInst = dyn_cast<LoadInst>(Val);
3525
5.80k
  if (!LInst)
3526
3.50k
    return nullptr;
3527
2.30k
3528
2.30k
  if (Value *Rep = InvEquivClassVMap.lookup(LInst))
3529
2
    LInst = cast<LoadInst>(Rep);
3530
2.30k
3531
2.30k
  Type *Ty = LInst->getType();
3532
2.30k
  const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
3533
2.30k
  for (auto &IAClass : InvariantEquivClasses) {
3534
276
    if (PointerSCEV != IAClass.IdentifyingPointer || 
Ty != IAClass.AccessType87
)
3535
191
      continue;
3536
85
3537
85
    auto &MAs = IAClass.InvariantAccesses;
3538
85
    for (auto *MA : MAs)
3539
91
      if (MA->getAccessInstruction() == Val)
3540
83
        return &IAClass;
3541
85
  }
3542
2.30k
3543
2.30k
  
return nullptr2.22k
;
3544
2.30k
}
3545
3546
6
bool isAParameter(llvm::Value *maybeParam, const Function &F) {
3547
6
  for (const llvm::Argument &Arg : F.args())
3548
10
    if (&Arg == maybeParam)
3549
6
      return true;
3550
6
3551
6
  
return false0
;
3552
6
}
3553
3554
bool Scop::canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
3555
                              bool MAInvalidCtxIsEmpty,
3556
361
                              bool NonHoistableCtxIsEmpty) {
3557
361
  LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
3558
361
  const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
3559
361
  if (PollyAllowDereferenceOfAllFunctionParams &&
3560
361
      
isAParameter(LInst->getPointerOperand(), getFunction())6
)
3561
6
    return true;
3562
355
3563
355
  // TODO: We can provide more information for better but more expensive
3564
355
  //       results.
3565
355
  if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
3566
355
                                          LInst->getAlignment(), DL))
3567
299
    return false;
3568
56
3569
56
  // If the location might be overwritten we do not hoist it unconditionally.
3570
56
  //
3571
56
  // TODO: This is probably too conservative.
3572
56
  if (!NonHoistableCtxIsEmpty)
3573
1
    return false;
3574
55
3575
55
  // If a dereferenceable load is in a statement that is modeled precisely we
3576
55
  // can hoist it.
3577
55
  if (StmtInvalidCtxIsEmpty && 
MAInvalidCtxIsEmpty50
)
3578
50
    return true;
3579
5
3580
5
  // Even if the statement is not modeled precisely we can hoist the load if it
3581
5
  // does not involve any parameters that might have been specialized by the
3582
5
  // statement domain.
3583
10
  
for (unsigned u = 0, e = MA->getNumSubscripts(); 5
u < e;
u++5
)
3584
5
    if (!isa<SCEVConstant>(MA->getSubscript(u)))
3585
0
      return false;
3586
5
  return true;
3587
5
}
3588
3589
369
void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) {
3590
369
  if (InvMAs.empty())
3591
122
    return;
3592
247
3593
247
  isl::set StmtInvalidCtx = Stmt.getInvalidContext();
3594
247
  bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
3595
247
3596
247
  // Get the context under which the statement is executed but remove the error
3597
247
  // context under which this statement is reached.
3598
247
  isl::set DomainCtx = Stmt.getDomain().params();
3599
247
  DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
3600
247
3601
247
  if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
3602
1
    auto *AccInst = InvMAs.front().MA->getAccessInstruction();
3603
1
    invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
3604
1
    return;
3605
1
  }
3606
246
3607
246
  // Project out all parameters that relate to loads in the statement. Otherwise
3608
246
  // we could have cyclic dependences on the constraints under which the
3609
246
  // hoisted loads are executed and we could not determine an order in which to
3610
246
  // pre-load them. This happens because not only lower bounds are part of the
3611
246
  // domain but also upper bounds.
3612
361
  
for (auto &InvMA : InvMAs)246
{
3613
361
    auto *MA = InvMA.MA;
3614
361
    Instruction *AccInst = MA->getAccessInstruction();
3615
361
    if (SE->isSCEVable(AccInst->getType())) {
3616
337
      SetVector<Value *> Values;
3617
586
      for (const SCEV *Parameter : Parameters) {
3618
586
        Values.clear();
3619
586
        findValues(Parameter, *SE, Values);
3620
586
        if (!Values.count(AccInst))
3621
474
          continue;
3622
112
3623
112
        if (isl::id ParamId = getIdForParam(Parameter)) {
3624
112
          int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
3625
112
          if (Dim >= 0)
3626
111
            DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
3627
112
        }
3628
112
      }
3629
337
    }
3630
361
  }
3631
246
3632
361
  for (auto &InvMA : InvMAs) {
3633
361
    auto *MA = InvMA.MA;
3634
361
    isl::set NHCtx = InvMA.NonHoistableCtx;
3635
361
3636
361
    // Check for another invariant access that accesses the same location as
3637
361
    // MA and if found consolidate them. Otherwise create a new equivalence
3638
361
    // class at the end of InvariantEquivClasses.
3639
361
    LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
3640
361
    Type *Ty = LInst->getType();
3641
361
    const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
3642
361
3643
361
    isl::set MAInvalidCtx = MA->getInvalidContext();
3644
361
    bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
3645
361
    bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
3646
361
3647
361
    isl::set MACtx;
3648
361
    // Check if we know that this pointer can be speculatively accessed.
3649
361
    if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
3650
361
                           NonHoistableCtxIsEmpty)) {
3651
61
      MACtx = isl::set::universe(DomainCtx.get_space());
3652
300
    } else {
3653
300
      MACtx = DomainCtx;
3654
300
      MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
3655
300
      MACtx = MACtx.gist_params(getContext());
3656
300
    }
3657
361
3658
361
    bool Consolidated = false;
3659
927
    for (auto &IAClass : InvariantEquivClasses) {
3660
927
      if (PointerSCEV != IAClass.IdentifyingPointer || 
Ty != IAClass.AccessType241
)
3661
690
        continue;
3662
237
3663
237
      // If the pointer and the type is equal check if the access function wrt.
3664
237
      // to the domain is equal too. It can happen that the domain fixes
3665
237
      // parameter values and these can be different for distinct part of the
3666
237
      // SCoP. If this happens we cannot consolidate the loads but need to
3667
237
      // create a new invariant load equivalence class.
3668
237
      auto &MAs = IAClass.InvariantAccesses;
3669
237
      if (!MAs.empty()) {
3670
45
        auto *LastMA = MAs.front();
3671
45
3672
45
        isl::set AR = MA->getAccessRelation().range();
3673
45
        isl::set LastAR = LastMA->getAccessRelation().range();
3674
45
        bool SameAR = AR.is_equal(LastAR);
3675
45
3676
45
        if (!SameAR)
3677
4
          continue;
3678
233
      }
3679
233
3680
233
      // Add MA to the list of accesses that are in this class.
3681
233
      MAs.push_front(MA);
3682
233
3683
233
      Consolidated = true;
3684
233
3685
233
      // Unify the execution context of the class and this statement.
3686
233
      isl::set IAClassDomainCtx = IAClass.ExecutionContext;
3687
233
      if (IAClassDomainCtx)
3688
41
        IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
3689
192
      else
3690
192
        IAClassDomainCtx = MACtx;
3691
233
      IAClass.ExecutionContext = IAClassDomainCtx;
3692
233
      break;
3693
233
    }
3694
361
3695
361
    if (Consolidated)
3696
233
      continue;
3697
128
3698
128
    MACtx = MACtx.coalesce();
3699
128
3700
128
    // If we did not consolidate MA, thus did not find an equivalence class
3701
128
    // for it, we create a new one.
3702
128
    InvariantEquivClasses.emplace_back(
3703
128
        InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
3704
128
  }
3705
246
}
3706
3707
/// Check if an access range is too complex.
3708
///
3709
/// An access range is too complex, if it contains either many disjuncts or
3710
/// very complex expressions. As a simple heuristic, we assume if a set to
3711
/// be too complex if the sum of existentially quantified dimensions and
3712
/// set dimensions is larger than a threshold. This reliably detects both
3713
/// sets with many disjuncts as well as sets with many divisions as they
3714
/// arise in h264.
3715
///
3716
/// @param AccessRange The range to check for complexity.
3717
///
3718
/// @returns True if the access range is too complex.
3719
411
static bool isAccessRangeTooComplex(isl::set AccessRange) {
3720
411
  unsigned NumTotalDims = 0;
3721
411
3722
457
  for (isl::basic_set BSet : AccessRange.get_basic_set_list()) {
3723
457
    NumTotalDims += BSet.dim(isl::dim::div);
3724
457
    NumTotalDims += BSet.dim(isl::dim::set);
3725
457
  }
3726
411
3727
411
  if (NumTotalDims > MaxDimensionsInAccessRange)
3728
1
    return true;
3729
410
3730
410
  return false;
3731
410
}
3732
3733
903
isl::set Scop::getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes) {
3734
903
  // TODO: Loads that are not loop carried, hence are in a statement with
3735
903
  //       zero iterators, are by construction invariant, though we
3736
903
  //       currently "hoist" them anyway. This is necessary because we allow
3737
903
  //       them to be treated as parameters (e.g., in conditions) and our code
3738
903
  //       generation would otherwise use the old value.
3739
903
3740
903
  auto &Stmt = *Access->getStatement();
3741
903
  BasicBlock *BB = Stmt.getEntryBlock();
3742
903
3743
903
  if (Access->isScalarKind() || 
Access->isWrite()762
||
!Access->isAffine()500
||
3744
903
      
Access->isMemoryIntrinsic()486
)
3745
417
    return nullptr;
3746
486
3747
486
  // Skip accesses that have an invariant base pointer which is defined but
3748
486
  // not loaded inside the SCoP. This can happened e.g., if a readnone call
3749
486
  // returns a pointer that is used as a base address. However, as we want
3750
486
  // to hoist indirect pointers, we allow the base pointer to be defined in
3751
486
  // the region if it is also a memory access. Each ScopArrayInfo object
3752
486
  // that has a base pointer origin has a base pointer that is loaded and
3753
486
  // that it is invariant, thus it will be hoisted too. However, if there is
3754
486
  // no base pointer origin we check that the base pointer is defined
3755
486
  // outside the region.
3756
486
  auto *LI = cast<LoadInst>(Access->getAccessInstruction());
3757
486
  if (hasNonHoistableBasePtrInScop(Access, Writes))
3758
0
    return nullptr;
3759
486
3760
486
  isl::map AccessRelation = Access->getAccessRelation();
3761
486
  assert(!AccessRelation.is_empty());
3762
486
3763
486
  if (AccessRelation.involves_dims(isl::dim::in, 0, Stmt.getNumIterators()))
3764
74
    return nullptr;
3765
412
3766
412
  AccessRelation = AccessRelation.intersect_domain(Stmt.getDomain());
3767
412
  isl::set SafeToLoad;
3768
412
3769
412
  auto &DL = getFunction().getParent()->getDataLayout();
3770
412
  if (isSafeToLoadUnconditionally(LI->getPointerOperand(), LI->getAlignment(),
3771
412
                                  DL)) {
3772
79
    SafeToLoad = isl::set::universe(AccessRelation.get_space().range());
3773
333
  } else if (BB != LI->getParent()) {
3774
1
    // Skip accesses in non-affine subregions as they might not be executed
3775
1
    // under the same condition as the entry of the non-affine subregion.
3776
1
    return nullptr;
3777
332
  } else {
3778
332
    SafeToLoad = AccessRelation.range();
3779
332
  }
3780
412
3781
412
  
if (411
isAccessRangeTooComplex(AccessRelation.range())411
)
3782
1
    return nullptr;
3783
410
3784
410
  isl::union_map Written = Writes.intersect_range(SafeToLoad);
3785
410
  isl::set WrittenCtx = Written.params();
3786
410
  bool IsWritten = !WrittenCtx.is_empty();
3787
410
3788
410
  if (!IsWritten)
3789
348
    return WrittenCtx;
3790
62
3791
62
  WrittenCtx = WrittenCtx.remove_divs();
3792
62
  bool TooComplex = WrittenCtx.n_basic_set() >= MaxDisjunctsInDomain;
3793
62
  if (TooComplex || 
!isRequiredInvariantLoad(LI)56
)
3794
48
    return nullptr;
3795
14
3796
14
  addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(), AS_RESTRICTION,
3797
14
                LI->getParent());
3798
14
  return WrittenCtx;
3799
14
}
3800
3801
1.15k
void Scop::verifyInvariantLoads() {
3802
1.15k
  auto &RIL = getRequiredInvariantLoads();
3803
1.15k
  for (LoadInst *LI : RIL) {
3804
230
    assert(LI && contains(LI));
3805
230
    // If there exists a statement in the scop which has a memory access for
3806
230
    // @p LI, then mark this scop as infeasible for optimization.
3807
230
    for (ScopStmt &Stmt : Stmts)
3808
887
      if (Stmt.getArrayAccessOrNULLFor(LI)) {
3809
3
        invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
3810
3
        return;
3811
3
      }
3812
230
  }
3813
1.15k
}
3814
3815
1.15k
void Scop::hoistInvariantLoads() {
3816
1.15k
  if (!PollyInvariantLoadHoisting)
3817
985
    return;
3818
166
3819
166
  isl::union_map Writes = getWrites();
3820
369
  for (ScopStmt &Stmt : *this) {
3821
369
    InvariantAccessesTy InvariantAccesses;
3822
369
3823
369
    for (MemoryAccess *Access : Stmt)
3824
903
      if (isl::set NHCtx = getNonHoistableCtx(Access, Writes))
3825
362
        InvariantAccesses.push_back({Access, NHCtx});
3826
369
3827
369
    // Transfer the memory access from the statement to the SCoP.
3828
369
    for (auto InvMA : InvariantAccesses)
3829
362
      Stmt.removeMemoryAccess(InvMA.MA);
3830
369
    addInvariantLoads(Stmt, InvariantAccesses);
3831
369
  }
3832
166
}
3833
3834
/// Find the canonical scop array info object for a set of invariant load
3835
/// hoisted loads. The canonical array is the one that corresponds to the
3836
/// first load in the list of accesses which is used as base pointer of a
3837
/// scop array.
3838
static const ScopArrayInfo *findCanonicalArray(Scop *S,
3839
327
                                               MemoryAccessList &Accesses) {
3840
345
  for (MemoryAccess *Access : Accesses) {
3841
345
    const ScopArrayInfo *CanonicalArray = S->getScopArrayInfoOrNull(
3842
345
        Access->getAccessInstruction(), MemoryKind::Array);
3843
345
    if (CanonicalArray)
3844
75
      return CanonicalArray;
3845
345
  }
3846
327
  
return nullptr252
;
3847
327
}
3848
3849
/// Check if @p Array severs as base array in an invariant load.
3850
11
static bool isUsedForIndirectHoistedLoad(Scop *S, const ScopArrayInfo *Array) {
3851
11
  for (InvariantEquivClassTy &EqClass2 : S->getInvariantAccesses())
3852
23
    for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
3853
38
      if (Access2->getScopArrayInfo() == Array)
3854
6
        return true;
3855
11
  
return false5
;
3856
11
}
3857
3858
/// Replace the base pointer arrays in all memory accesses referencing @p Old,
3859
/// with a reference to @p New.
3860
static void replaceBasePtrArrays(Scop *S, const ScopArrayInfo *Old,
3861
5
                                 const ScopArrayInfo *New) {
3862
5
  for (ScopStmt &Stmt : *S)
3863
17
    
for (MemoryAccess *Access : Stmt)14
{
3864
17
      if (Access->getLatestScopArrayInfo() != Old)
3865
11
        continue;
3866
6
3867
6
      isl::id Id = New->getBasePtrId();
3868
6
      isl::map Map = Access->getAccessRelation();
3869
6
      Map = Map.set_tuple_id(isl::dim::out, Id);
3870
6
      Access->setAccessRelation(Map);
3871
6
    }
3872
5
}
3873
3874
1.15k
void Scop::canonicalizeDynamicBasePtrs() {
3875
1.15k
  for (InvariantEquivClassTy &EqClass : InvariantEquivClasses) {
3876
327
    MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
3877
327
3878
327
    const ScopArrayInfo *CanonicalBasePtrSAI =
3879
327
        findCanonicalArray(this, BasePtrAccesses);
3880
327
3881
327
    if (!CanonicalBasePtrSAI)
3882
252
      continue;
3883
75
3884
92
    
for (MemoryAccess *BasePtrAccess : BasePtrAccesses)75
{
3885
92
      const ScopArrayInfo *BasePtrSAI = getScopArrayInfoOrNull(
3886
92
          BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
3887
92
      if (!BasePtrSAI || 
BasePtrSAI == CanonicalBasePtrSAI89
||
3888
92
          
!BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI)14
)
3889
81
        continue;
3890
11
3891
11
      // we currently do not canonicalize arrays where some accesses are
3892
11
      // hoisted as invariant loads. If we would, we need to update the access
3893
11
      // function of the invariant loads as well. However, as this is not a
3894
11
      // very common situation, we leave this for now to avoid further
3895
11
      // complexity increases.
3896
11
      if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
3897
6
        continue;
3898
5
3899
5
      replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
3900
5
    }
3901
75
  }
3902
1.15k
}
3903
3904
ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
3905
                                              ArrayRef<const SCEV *> Sizes,
3906
                                              MemoryKind Kind,
3907
4.98k
                                              const char *BaseName) {
3908
4.98k
  assert((BasePtr || BaseName) &&
3909
4.98k
         "BasePtr and BaseName can not be nullptr at the same time.");
3910
4.98k
  assert(!(BasePtr && BaseName) && "BaseName is redundant.");
3911
4.98k
  auto &SAI = BasePtr ? 
ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]4.89k
3912
4.98k
                      : 
ScopArrayNameMap[BaseName]85
;
3913
4.98k
  if (!SAI) {
3914
2.56k
    auto &DL = getFunction().getParent()->getDataLayout();
3915
2.56k
    SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
3916
2.56k
                                DL, this, BaseName));
3917
2.56k
    ScopArrayInfoSet.insert(SAI.get());
3918
2.56k
  } else {
3919
2.41k
    SAI->updateElementType(ElementType);
3920
2.41k
    // In case of mismatching array sizes, we bail out by setting the run-time
3921
2.41k
    // context to false.
3922
2.41k
    if (!SAI->updateSizes(Sizes))
3923
0
      invalidate(DELINEARIZATION, DebugLoc());
3924
2.41k
  }
3925
4.98k
  return SAI.get();
3926
4.98k
}
3927
3928
ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,
3929
                                         const std::string &BaseName,
3930
85
                                         const std::vector<unsigned> &Sizes) {
3931
85
  auto *DimSizeType = Type::getInt64Ty(getSE()->getContext());
3932
85
  std::vector<const SCEV *> SCEVSizes;
3933
85
3934
85
  for (auto size : Sizes)
3935
168
    if (size)
3936
168
      SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
3937
0
    else
3938
0
      SCEVSizes.push_back(nullptr);
3939
85
3940
85
  auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
3941
85
                                       MemoryKind::Array, BaseName.c_str());
3942
85
  return SAI;
3943
85
}
3944
3945
const ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr,
3946
530
                                                  MemoryKind Kind) {
3947
530
  auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
3948
530
  return SAI;
3949
530
}
3950
3951
93
const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
3952
93
  auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);
3953
93
  assert(SAI && "No ScopArrayInfo available for this base pointer");
3954
93
  return SAI;
3955
93
}
3956
3957
0
std::string Scop::getContextStr() const { return getContext().to_str(); }
3958
3959
0
std::string Scop::getAssumedContextStr() const {
3960
0
  assert(AssumedContext && "Assumed context not yet built");
3961
0
  return AssumedContext.to_str();
3962
0
}
3963
3964
0
std::string Scop::getInvalidContextStr() const {
3965
0
  return InvalidContext.to_str();
3966
0
}
3967
3968
839
std::string Scop::getNameStr() const {
3969
839
  std::string ExitName, EntryName;
3970
839
  std::tie(EntryName, ExitName) = getEntryExitStr();
3971
839
  return EntryName + "---" + ExitName;
3972
839
}
3973
3974
849
std::pair<std::string, std::string> Scop::getEntryExitStr() const {
3975
849
  std::string ExitName, EntryName;
3976
849
  raw_string_ostream ExitStr(ExitName);
3977
849
  raw_string_ostream EntryStr(EntryName);
3978
849
3979
849
  R.getEntry()->printAsOperand(EntryStr, false);
3980
849
  EntryStr.str();
3981
849
3982
849
  if (R.getExit()) {
3983
845
    R.getExit()->printAsOperand(ExitStr, false);
3984
845
    ExitStr.str();
3985
845
  } else
3986
4
    ExitName = "FunctionExit";
3987
849
3988
849
  return std::make_pair(EntryName, ExitName);
3989
849
}
3990
3991
30.6k
isl::set Scop::getContext() const { return Context; }
3992
10.1k
isl::space Scop::getParamSpace() const { return getContext().get_space(); }
3993
3994
1.15k
isl::space Scop::getFullParamSpace() const {
3995
1.15k
  std::vector<isl::id> FortranIDs;
3996
1.15k
  FortranIDs = getFortranArrayIds(arrays());
3997
1.15k
3998
1.15k
  isl::space Space = isl::space::params_alloc(
3999
1.15k
      getIslCtx(), ParameterIds.size() + FortranIDs.size());
4000
1.15k
4001
1.15k
  unsigned PDim = 0;
4002
1.20k
  for (const SCEV *Parameter : Parameters) {
4003
1.20k
    isl::id Id = getIdForParam(Parameter);
4004
1.20k
    Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
4005
1.20k
  }
4006
1.15k
4007
1.15k
  for (isl::id Id : FortranIDs)
4008
7
    Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
4009
1.15k
4010
1.15k
  return Space;
4011
1.15k
}
4012
4013
4.95k
isl::set Scop::getAssumedContext() const {
4014
4.95k
  assert(AssumedContext && "Assumed context not yet built");
4015
4.95k
  return AssumedContext;
4016
4.95k
}
4017
4018
1.15k
bool Scop::isProfitable(bool ScalarsAreUnprofitable) const {
4019
1.15k
  if (PollyProcessUnprofitable)
4020
1.15k
    return true;
4021
3
4022
3
  if (isEmpty())
4023
0
    return false;
4024
3
4025
3
  unsigned OptimizableStmtsOrLoops = 0;
4026
14
  for (auto &Stmt : *this) {
4027
14
    if (Stmt.getNumIterators() == 0)
4028
0
      continue;
4029
14
4030
14
    bool ContainsArrayAccs = false;
4031
14
    bool ContainsScalarAccs = false;
4032
33
    for (auto *MA : Stmt) {
4033
33
      if (MA->isRead())
4034
15
        continue;
4035
18
      ContainsArrayAccs |= MA->isLatestArrayKind();
4036
18
      ContainsScalarAccs |= MA->isLatestScalarKind();
4037
18
    }
4038
14
4039
14
    if (!ScalarsAreUnprofitable || 
(9
ContainsArrayAccs9
&&
!ContainsScalarAccs4
))
4040
6
      OptimizableStmtsOrLoops += Stmt.getNumIterators();
4041
14
  }
4042
3
4043
3
  return OptimizableStmtsOrLoops > 1;
4044
3
}
4045
4046
3.88k
bool Scop::hasFeasibleRuntimeContext() const {
4047
3.88k
  auto PositiveContext = getAssumedContext();
4048
3.88k
  auto NegativeContext = getInvalidContext();
4049
3.88k
  PositiveContext = addNonEmptyDomainConstraints(PositiveContext);
4050
3.88k
  // addNonEmptyDomainConstraints returns null if ScopStmts have a null domain
4051
3.88k
  if (!PositiveContext)
4052
8
    return false;
4053
3.87k
4054
3.87k
  bool IsFeasible = !(PositiveContext.is_empty() ||
4055
3.87k
                      
PositiveContext.is_subset(NegativeContext)3.81k
);
4056
3.87k
  if (!IsFeasible)
4057
82
    return false;
4058
3.79k
4059
3.79k
  auto DomainContext = getDomains().params();
4060
3.79k
  IsFeasible = !DomainContext.is_subset(NegativeContext);
4061
3.79k
  IsFeasible &= !Context.is_subset(NegativeContext);
4062
3.79k
4063
3.79k
  return IsFeasible;
4064
3.79k
}
4065
4066
665
static std::string toString(AssumptionKind Kind) {
4067
665
  switch (Kind) {
4068
665
  case ALIASING:
4069
5
    return "No-aliasing";
4070
665
  case INBOUNDS:
4071
111
    return "Inbounds";
4072
665
  case WRAPPING:
4073
347
    return "No-overflows";
4074
665
  case UNSIGNED:
4075
87
    return "Signed-unsigned";
4076
665
  case COMPLEXITY:
4077
8
    return "Low complexity";
4078
665
  case PROFITABLE:
4079
2
    return "Profitable";
4080
665
  case ERRORBLOCK:
4081
22
    return "No-error";
4082
665
  case INFINITELOOP:
4083
71
    return "Finite loop";
4084
665
  case INVARIANTLOAD:
4085
10
    return "Invariant load";
4086
665
  case DELINEARIZATION:
4087
2
    return "Delinearization";
4088
0
  }
4089
0
  llvm_unreachable("Unknown AssumptionKind!");
4090
0
}
4091
4092
8.00k
bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {
4093
8.00k
  if (Sign == AS_ASSUMPTION) {
4094
4.63k
    if (Context.is_subset(Set))
4095
4.45k
      return false;
4096
179
4097
179
    if (AssumedContext.is_subset(Set))
4098
48
      return false;
4099
3.37k
  } else {
4100
3.37k
    if (Set.is_disjoint(Context))
4101
2.31k
      return false;
4102
1.05k
4103
1.05k
    if (Set.is_subset(InvalidContext))
4104
523
      return false;
4105
665
  }
4106
665
  return true;
4107
665
}
4108
4109
bool Scop::trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4110
8.00k
                           AssumptionSign Sign, BasicBlock *BB) {
4111
8.00k
  if (PollyRemarksMinimal && !isEffectiveAssumption(Set, Sign))
4112
7.34k
    return false;
4113
665
4114
665
  // Do never emit trivial assumptions as they only clutter the output.
4115
665
  if (!PollyRemarksMinimal) {
4116
0
    isl::set Univ;
4117
0
    if (Sign == AS_ASSUMPTION)
4118
0
      Univ = isl::set::universe(Set.get_space());
4119
0
4120
0
    bool IsTrivial = (Sign == AS_RESTRICTION && Set.is_empty()) ||
4121
0
                     (Sign == AS_ASSUMPTION && Univ.is_equal(Set));
4122
0
4123
0
    if (IsTrivial)
4124
0
      return false;
4125
665
  }
4126
665
4127
665
  switch (Kind) {
4128
665
  case ALIASING:
4129
5
    AssumptionsAliasing++;
4130
5
    break;
4131
665
  case INBOUNDS:
4132
111
    AssumptionsInbounds++;
4133
111
    break;
4134
665
  case WRAPPING:
4135
347
    AssumptionsWrapping++;
4136
347
    break;
4137
665
  case UNSIGNED:
4138
87
    AssumptionsUnsigned++;
4139
87
    break;
4140
665
  case COMPLEXITY:
4141
8
    AssumptionsComplexity++;
4142
8
    break;
4143
665
  case PROFITABLE:
4144
2
    AssumptionsUnprofitable++;
4145
2
    break;
4146
665
  case ERRORBLOCK:
4147
22
    AssumptionsErrorBlock++;
4148
22
    break;
4149
665
  case INFINITELOOP:
4150
71
    AssumptionsInfiniteLoop++;
4151
71
    break;
4152
665
  case INVARIANTLOAD:
4153
10
    AssumptionsInvariantLoad++;
4154
10
    break;
4155
665
  case DELINEARIZATION:
4156
2
    AssumptionsDelinearization++;
4157
2
    break;
4158
665
  }
4159
665
4160
665
  auto Suffix = Sign == AS_ASSUMPTION ? 
" assumption:\t"131
:
" restriction:\t"534
;
4161
665
  std::string Msg = toString(Kind) + Suffix + Set.to_str();
4162
665
  if (BB)
4163
445
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc, BB)
4164
445
             << Msg);
4165
220
  else
4166
220
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc,
4167
220
                                        R.getEntry())
4168
220
             << Msg);
4169
665
  return true;
4170
665
}
4171
4172
void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4173
8.00k
                         AssumptionSign Sign, BasicBlock *BB) {
4174
8.00k
  // Simplify the assumptions/restrictions first.
4175
8.00k
  Set = Set.gist_params(getContext());
4176
8.00k
4177
8.00k
  if (!trackAssumption(Kind, Set, Loc, Sign, BB))
4178
7.34k
    return;
4179
665
4180
665
  if (Sign == AS_ASSUMPTION)
4181
131
    AssumedContext = AssumedContext.intersect(Set).coalesce();
4182
534
  else
4183
534
    InvalidContext = InvalidContext.unite(Set).coalesce();
4184
665
}
4185
4186
void Scop::recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4187
8.17k
                            AssumptionSign Sign, BasicBlock *BB) {
4188
8.17k
  assert((Set.is_params() || BB) &&
4189
8.17k
         "Assumptions without a basic block must be parameter sets");
4190
8.17k
  RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB});
4191
8.17k
}
4192
4193
1.15k
void Scop::addRecordedAssumptions() {
4194
9.12k
  while (!RecordedAssumptions.empty()) {
4195
7.97k
    Assumption AS = RecordedAssumptions.pop_back_val();
4196
7.97k
4197
7.97k
    if (!AS.BB) {
4198
5.09k
      addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, nullptr /* BasicBlock */);
4199
5.09k
      continue;
4200
5.09k
    }
4201
2.88k
4202
2.88k
    // If the domain was deleted the assumptions are void.
4203
2.88k
    isl_set *Dom = getDomainConditions(AS.BB).release();
4204
2.88k
    if (!Dom)
4205
0
      continue;
4206
2.88k
4207
2.88k
    // If a basic block was given use its domain to simplify the assumption.
4208
2.88k
    // In case of restrictions we know they only have to hold on the domain,
4209
2.88k
    // thus we can intersect them with the domain of the block. However, for
4210
2.88k
    // assumptions the domain has to imply them, thus:
4211
2.88k
    //                     _              _____
4212
2.88k
    //   Dom => S   <==>   A v B   <==>   A - B
4213
2.88k
    //
4214
2.88k
    // To avoid the complement we will register A - B as a restriction not an
4215
2.88k
    // assumption.
4216
2.88k
    isl_set *S = AS.Set.copy();
4217
2.88k
    if (AS.Sign == AS_RESTRICTION)
4218
2.88k
      S = isl_set_params(isl_set_intersect(S, Dom));
4219
0
    else /* (AS.Sign == AS_ASSUMPTION) */
4220
0
      S = isl_set_params(isl_set_subtract(Dom, S));
4221
2.88k
4222
2.88k
    addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
4223
2.88k
  }
4224
1.15k
}
4225
4226
21
void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
4227
21
  LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");
4228
21
  addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);
4229
21
}
4230
4231
4.00k
isl::set Scop::getInvalidContext() const { return InvalidContext; }
4232
4233
489
void Scop::printContext(raw_ostream &OS) const {
4234
489
  OS << "Context:\n";
4235
489
  OS.indent(4) << Context << "\n";
4236
489
4237
489
  OS.indent(4) << "Assumed Context:\n";
4238
489
  OS.indent(4) << AssumedContext << "\n";
4239
489
4240
489
  OS.indent(4) << "Invalid Context:\n";
4241
489
  OS.indent(4) << InvalidContext << "\n";
4242
489
4243
489
  unsigned Dim = 0;
4244
489
  for (const SCEV *Parameter : Parameters)
4245
653
    OS.indent(4) << "p" << Dim++ << ": " << *Parameter << "\n";
4246
489
}
4247
4248
489
void Scop::printAliasAssumptions(raw_ostream &OS) const {
4249
489
  int noOfGroups = 0;
4250
489
  for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
4251
91
    if (Pair.second.size() == 0)
4252
29
      noOfGroups += 1;
4253
62
    else
4254
62
      noOfGroups += Pair.second.size();
4255
91
  }
4256
489
4257
489
  OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";
4258
489
  if (MinMaxAliasGroups.empty()) {
4259
402
    OS.indent(8) << "n/a\n";
4260
402
    return;
4261
402
  }
4262
87
4263
91
  
for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups)87
{
4264
91
4265
91
    // If the group has no read only accesses print the write accesses.
4266
91
    if (Pair.second.empty()) {
4267
29
      OS.indent(8) << "[[";
4268
68
      for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
4269
68
        OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
4270
68
           << ">";
4271
68
      }
4272
29
      OS << " ]]\n";
4273
29
    }
4274
91
4275
92
    for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
4276
92
      OS.indent(8) << "[[";
4277
92
      OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
4278
110
      for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
4279
110
        OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
4280
110
           << ">";
4281
110
      }
4282
92
      OS << " ]]\n";
4283
92
    }
4284
91
  }
4285
87
}
4286
4287
489
void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {
4288
489
  OS << "Statements {\n";
4289
489
4290
850
  for (const ScopStmt &Stmt : *this) {
4291
850
    OS.indent(4);
4292
850
    Stmt.print(OS, PrintInstructions);
4293
850
  }
4294
489
4295
489
  OS.indent(4) << "}\n";
4296
489
}
4297
4298
489
void Scop::printArrayInfo(raw_ostream &OS) const {
4299
489
  OS << "Arrays {\n";
4300
489
4301
489
  for (auto &Array : arrays())
4302
1.07k
    Array->print(OS);
4303
489
4304
489
  OS.indent(4) << "}\n";
4305
489
4306
489
  OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
4307
489
4308
489
  for (auto &Array : arrays())
4309
1.07k
    Array->print(OS, /* SizeAsPwAff */ true);
4310
489
4311
489
  OS.indent(4) << "}\n";
4312
489
}
4313
4314
489
void Scop::print(raw_ostream &OS, bool PrintInstructions) const {
4315
489
  OS.indent(4) << "Function: " << getFunction().getName() << "\n";
4316
489
  OS.indent(4) << "Region: " << getNameStr() << "\n";
4317
489
  OS.indent(4) << "Max Loop Depth:  " << getMaxLoopDepth() << "\n";
4318
489
  OS.indent(4) << "Invariant Accesses: {\n";
4319
489
  for (const auto &IAClass : InvariantEquivClasses) {
4320
163
    const auto &MAs = IAClass.InvariantAccesses;
4321
163
    if (MAs.empty()) {
4322
1
      OS.indent(12) << "Class Pointer: " << *IAClass.IdentifyingPointer << "\n";
4323
162
    } else {
4324
162
      MAs.front()->print(OS);
4325
162
      OS.indent(12) << "Execution Context: " << IAClass.ExecutionContext
4326
162
                    << "\n";
4327
162
    }
4328
163
  }
4329
489
  OS.indent(4) << "}\n";
4330
489
  printContext(OS.indent(4));
4331
489
  printArrayInfo(OS.indent(4));
4332
489
  printAliasAssumptions(OS);
4333
489
  printStatements(OS.indent(4), PrintInstructions);
4334
489
}
4335
4336
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4337
LLVM_DUMP_METHOD void Scop::dump() const { print(dbgs(), true); }
4338
#endif
4339
4340
32.9k
isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }
4341
4342
__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
4343
10.2k
                                 bool NonNegative) {
4344
10.2k
  // First try to use the SCEVAffinator to generate a piecewise defined
4345
10.2k
  // affine function from @p E in the context of @p BB. If that tasks becomes to
4346
10.2k
  // complex the affinator might return a nullptr. In such a case we invalidate
4347
10.2k
  // the SCoP and return a dummy value. This way we do not need to add error
4348
10.2k
  // handling code to all users of this function.
4349
10.2k
  auto PWAC = Affinator.getPwAff(E, BB);
4350
10.2k
  if (PWAC.first) {
4351
10.2k
    // TODO: We could use a heuristic and either use:
4352
10.2k
    //         SCEVAffinator::takeNonNegativeAssumption
4353
10.2k
    //       or
4354
10.2k
    //         SCEVAffinator::interpretAsUnsigned
4355
10.2k
    //       to deal with unsigned or "NonNegative" SCEVs.
4356
10.2k
    if (NonNegative)
4357
43
      Affinator.takeNonNegativeAssumption(PWAC);
4358
10.2k
    return PWAC;
4359
10.2k
  }
4360
0
4361
0
  auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
4362
0
  invalidate(COMPLEXITY, DL, BB);
4363
0
  return Affinator.getPwAff(SE->getZero(E->getType()), BB);
4364
0
}
4365
4366
12.6k
isl::union_set Scop::getDomains() const {
4367
12.6k
  isl_space *EmptySpace = isl_space_params_alloc(getIslCtx().get(), 0);
4368
12.6k
  isl_union_set *Domain = isl_union_set_empty(EmptySpace);
4369
12.6k
4370
12.6k
  for (const ScopStmt &Stmt : *this)
4371
27.3k
    Domain = isl_union_set_add_set(Domain, Stmt.getDomain().release());
4372
12.6k
4373
12.6k
  return isl::manage(Domain);
4374
12.6k
}
4375
4376
539
isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB) {
4377
539
  PWACtx PWAC = getPwAff(E, BB);
4378
539
  return PWAC.first;
4379
539
}
4380
4381
isl::union_map
4382
1.33k
Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
4383
1.33k
  isl::union_map Accesses = isl::union_map::empty(getParamSpace());
4384
1.33k
4385
2.70k
  for (ScopStmt &Stmt : *this) {
4386
5.65k
    for (MemoryAccess *MA : Stmt) {
4387
5.65k
      if (!Predicate(*MA))
4388
586
        continue;
4389
5.07k
4390
5.07k
      isl::set Domain = Stmt.getDomain();
4391
5.07k
      isl::map AccessDomain = MA->getAccessRelation();
4392
5.07k
      AccessDomain = AccessDomain.intersect_domain(Domain);
4393
5.07k
      Accesses = Accesses.add_map(AccessDomain);
4394
5.07k
    }
4395
2.70k
  }
4396
1.33k
4397
1.33k
  return Accesses.coalesce();
4398
1.33k
}
4399
4400
7
isl::union_map Scop::getMustWrites() {
4401
23
  return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); });
4402
7
}
4403
4404
7
isl::union_map Scop::getMayWrites() {
4405
23
  return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); });
4406
7
}
4407
4408
166
isl::union_map Scop::getWrites() {
4409
903
  return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); });
4410
166
}
4411
4412
0
isl::union_map Scop::getReads() {
4413
0
  return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });
4414
0
}
4415
4416
1.15k
isl::union_map Scop::getAccesses() {
4417
4.70k
  return getAccessesOfType([](MemoryAccess &MA) { return true; });
4418
1.15k
}
4419
4420
0
isl::union_map Scop::getAccesses(ScopArrayInfo *Array) {
4421
0
  return getAccessesOfType(
4422
0
      [Array](MemoryAccess &MA) { return MA.getScopArrayInfo() == Array; });
4423
0
}
4424
4425
// Check whether @p Node is an extension node.
4426
//
4427
// @return true if @p Node is an extension node.
4428
17.0k
isl_bool isNotExtNode(__isl_keep isl_schedule_node *Node, void *User) {
4429
17.0k
  if (isl_schedule_node_get_type(Node) == isl_schedule_node_extension)
4430
16
    return isl_bool_error;
4431
17.0k
  else
4432
17.0k
    return isl_bool_true;
4433
17.0k
}
4434
4435
1.57k
bool Scop::containsExtensionNode(isl::schedule Schedule) {
4436
1.57k
  return isl_schedule_foreach_schedule_node_top_down(
4437
1.57k
             Schedule.get(), isNotExtNode, nullptr) == isl_stat_error;
4438
1.57k
}
4439
4440
1.41k
isl::union_map Scop::getSchedule() const {
4441
1.41k
  auto Tree = getScheduleTree();
4442
1.41k
  if (containsExtensionNode(Tree))
4443
4
    return nullptr;
4444
1.40k
4445
1.40k
  return Tree.get_map();
4446
1.40k
}
4447
4448
3.13k
isl::schedule Scop::getScheduleTree() const {
4449
3.13k
  return Schedule.intersect_domain(getDomains());
4450
3.13k
}
4451
4452
106
void Scop::setSchedule(isl::union_map NewSchedule) {
4453
106
  auto S = isl::schedule::from_domain(getDomains());
4454
106
  Schedule = S.insert_partial_schedule(
4455
106
      isl::multi_union_pw_aff::from_union_map(NewSchedule));
4456
106
  ScheduleModified = true;
4457
106
}
4458
4459
36
void Scop::setScheduleTree(isl::schedule NewSchedule) {
4460
36
  Schedule = NewSchedule;
4461
36
  ScheduleModified = true;
4462
36
}
4463
4464
7
bool Scop::restrictDomains(isl::union_set Domain) {
4465
7
  bool Changed = false;
4466
19
  for (ScopStmt &Stmt : *this) {
4467
19
    isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());
4468
19
    isl::union_set NewStmtDomain = StmtDomain.intersect(Domain);
4469
19
4470
19
    if (StmtDomain.is_subset(NewStmtDomain))
4471
11
      continue;
4472
8
4473
8
    Changed = true;
4474
8
4475
8
    NewStmtDomain = NewStmtDomain.coalesce();
4476
8
4477
8
    if (NewStmtDomain.is_empty())
4478
7
      Stmt.restrictDomain(isl::set::empty(Stmt.getDomainSpace()));
4479
1
    else
4480
1
      Stmt.restrictDomain(isl::set(NewStmtDomain));
4481
8
  }
4482
7
  return Changed;
4483
7
}
4484
4485
18.9k
ScalarEvolution *Scop::getSE() const { return SE; }
4486
4487
// Create an isl_multi_union_aff that defines an identity mapping from the
4488
// elements of USet to their N-th dimension.
4489
//
4490
// # Example:
4491
//
4492
//            Domain: { A[i,j]; B[i,j,k] }
4493
//                 N: 1
4494
//
4495
// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
4496
//
4497
// @param USet   A union set describing the elements for which to generate a
4498
//               mapping.
4499
// @param N      The dimension to map to.
4500
// @returns      A mapping from USet to its N-th dimension.
4501
1.62k
static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
4502
1.62k
  assert(N >= 0);
4503
1.62k
  assert(USet);
4504
1.62k
  assert(!USet.is_empty());
4505
1.62k
4506
1.62k
  auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
4507
1.62k
4508
2.56k
  for (isl::set S : USet.get_set_list()) {
4509
2.56k
    int Dim = S.dim(isl::dim::set);
4510
2.56k
    auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
4511
2.56k
                                                  N, Dim - N);
4512
2.56k
    if (N > 1)
4513
619
      PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
4514
2.56k
4515
2.56k
    Result = Result.add_pw_multi_aff(PMA);
4516
2.56k
  }
4517
1.62k
4518
1.62k
  return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
4519
1.62k
}
4520
4521
void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
4522
9.12k
                       std::vector<Instruction *> Instructions) {
4523
9.12k
  assert(BB && "Unexpected nullptr!");
4524
9.12k
  Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);
4525
9.12k
  auto *Stmt = &Stmts.back();
4526
9.12k
  StmtMap[BB].push_back(Stmt);
4527
9.12k
  for (Instruction *Inst : Instructions) {
4528
7.07k
    assert(!InstStmtMap.count(Inst) &&
4529
7.07k
           "Unexpected statement corresponding to the instruction.");
4530
7.07k
    InstStmtMap[Inst] = Stmt;
4531
7.07k
  }
4532
9.12k
}
4533
4534
void Scop::addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,
4535
121
                       std::vector<Instruction *> Instructions) {
4536
121
  assert(R && "Unexpected nullptr!");
4537
121
  Stmts.emplace_back(*this, *R, Name, SurroundingLoop, Instructions);
4538
121
  auto *Stmt = &Stmts.back();
4539
121
4540
446
  for (Instruction *Inst : Instructions) {
4541
446
    assert(!InstStmtMap.count(Inst) &&
4542
446
           "Unexpected statement corresponding to the instruction.");
4543
446
    InstStmtMap[Inst] = Stmt;
4544
446
  }
4545
121
4546
333
  for (BasicBlock *BB : R->blocks()) {
4547
333
    StmtMap[BB].push_back(Stmt);
4548
333
    if (BB == R->getEntry())
4549
121
      continue;
4550
545
    
for (Instruction &Inst : *BB)212
{
4551
545
      assert(!InstStmtMap.count(&Inst) &&
4552
545
             "Unexpected statement corresponding to the instruction.");
4553
545
      InstStmtMap[&Inst] = Stmt;
4554
545
    }
4555
212
  }
4556
121
}
4557
4558
ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,
4559
24
                            isl::set Domain) {
4560
#ifndef NDEBUG
4561
  isl::set SourceDomain = SourceRel.domain();
4562
  isl::set TargetDomain = TargetRel.domain();
4563
  assert(Domain.is_subset(TargetDomain) &&
4564
         "Target access not defined for complete statement domain");
4565
  assert(Domain.is_subset(SourceDomain) &&
4566
         "Source access not defined for complete statement domain");
4567
#endif
4568
  Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
4569
24
  CopyStmtsNum++;
4570
24
  return &(Stmts.back());
4571
24
}
4572
4573
1.15k
void Scop::buildSchedule(LoopInfo &LI) {
4574
1.15k
  Loop *L = getLoopSurroundingScop(*this, LI);
4575
1.15k
  LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
4576
1.15k
  buildSchedule(getRegion().getNode(), LoopStack, LI);
4577
1.15k
  assert(LoopStack.size() == 1 && LoopStack.back().L == L);
4578
1.15k
  Schedule = LoopStack[0].Schedule;
4579
1.15k
}
4580
4581
/// To generate a schedule for the elements in a Region we traverse the Region
4582
/// in reverse-post-order and add the contained RegionNodes in traversal order
4583
/// to the schedule of the loop that is currently at the top of the LoopStack.
4584
/// For loop-free codes, this results in a correct sequential ordering.
4585
///
4586
/// Example:
4587
///           bb1(0)
4588
///         /     \.
4589
///      bb2(1)   bb3(2)
4590
///         \    /  \.
4591
///          bb4(3)  bb5(4)
4592
///             \   /
4593
///              bb6(5)
4594
///
4595
/// Including loops requires additional processing. Whenever a loop header is
4596
/// encountered, the corresponding loop is added to the @p LoopStack. Starting
4597
/// from an empty schedule, we first process all RegionNodes that are within
4598
/// this loop and complete the sequential schedule at this loop-level before
4599
/// processing about any other nodes. To implement this
4600
/// loop-nodes-first-processing, the reverse post-order traversal is
4601
/// insufficient. Hence, we additionally check if the traversal yields
4602
/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
4603
/// These region-nodes are then queue and only traverse after the all nodes
4604
/// within the current loop have been processed.
4605
2.37k
void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI) {
4606
2.37k
  Loop *OuterScopLoop = getLoopSurroundingScop(*this, LI);
4607
2.37k
4608
2.37k
  ReversePostOrderTraversal<Region *> RTraversal(R);
4609
2.37k
  std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
4610
2.37k
  std::deque<RegionNode *> DelayList;
4611
2.37k
  bool LastRNWaiting = false;
4612
2.37k
4613
2.37k
  // Iterate over the region @p R in reverse post-order but queue
4614
2.37k
  // sub-regions/blocks iff they are not part of the last encountered but not
4615
2.37k
  // completely traversed loop. The variable LastRNWaiting is a flag to indicate
4616
2.37k
  // that we queued the last sub-region/block from the reverse post-order
4617
2.37k
  // iterator. If it is set we have to explore the next sub-region/block from
4618
2.37k
  // the iterator (if any) to guarantee progress. If it is not set we first try
4619
2.37k
  // the next queued sub-region/blocks.
4620
9.13k
  while (!WorkList.empty() || 
!DelayList.empty()2.37k
) {
4621
6.75k
    RegionNode *RN;
4622
6.75k
4623
6.75k
    if ((LastRNWaiting && 
!WorkList.empty()0
) || DelayList.empty()) {
4624
6.75k
      RN = WorkList.front();
4625
6.75k
      WorkList.pop_front();
4626
6.75k
      LastRNWaiting = false;
4627
6.75k
    } else {
4628
0
      RN = DelayList.front();
4629
0
      DelayList.pop_front();
4630
0
    }
4631
6.75k
4632
6.75k
    Loop *L = getRegionNodeLoop(RN, LI);
4633
6.75k
    if (!contains(L))
4634
1.47k
      L = OuterScopLoop;
4635
6.75k
4636
6.75k
    Loop *LastLoop = LoopStack.back().L;
4637
6.75k
    if (LastLoop != L) {
4638
1.65k
      if (LastLoop && 
!LastLoop->contains(L)487
) {
4639
0
        LastRNWaiting = true;
4640
0
        DelayList.push_back(RN);
4641
0
        continue;
4642
0
      }
4643
1.65k
      LoopStack.push_back({L, nullptr, 0});
4644
1.65k
    }
4645
6.75k
    buildSchedule(RN, LoopStack, LI);
4646
6.75k
  }
4647
2.37k
}
4648
4649
7.91k
void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) {
4650
7.91k
  if (RN->isSubRegion()) {
4651
2.48k
    auto *LocalRegion = RN->getNodeAs<Region>();
4652
2.48k
    if (!isNonAffineSubRegion(LocalRegion)) {
4653
2.37k
      buildSchedule(LocalRegion, LoopStack, LI);
4654
2.37k
      return;
4655
2.37k
    }
4656
5.53k
  }
4657
5.53k
4658
5.53k
  assert(LoopStack.rbegin() != LoopStack.rend());
4659
5.53k
  auto LoopData = LoopStack.rbegin();
4660
5.53k
  LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
4661
5.53k
4662
5.53k
  for (auto *Stmt : getStmtListFor(RN)) {
4663
2.30k
    isl::union_set UDomain{Stmt->getDomain()};
4664
2.30k
    auto StmtSchedule = isl::schedule::from_domain(UDomain);
4665
2.30k
    LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);
4666
2.30k
  }
4667
5.53k
4668
5.53k
  // Check if we just processed the last node in this loop. If we did, finalize
4669
5.53k
  // the loop by:
4670
5.53k
  //
4671
5.53k
  //   - adding new schedule dimensions
4672
5.53k
  //   - folding the resulting schedule into the parent loop schedule
4673
5.53k
  //   - dropping the loop schedule from the LoopStack.
4674
5.53k
  //
4675
5.53k
  // Then continue to check surrounding loops, which might also have been
4676
5.53k
  // completed by this node.
4677
5.53k
  size_t Dimension = LoopStack.size();
4678
7.19k
  while (LoopData->L &&
4679
7.19k
         
LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)5.28k
) {
4680
1.65k
    isl::schedule Schedule = LoopData->Schedule;
4681
1.65k
    auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
4682
1.65k
4683
1.65k
    assert(std::next(LoopData) != LoopStack.rend());
4684
1.65k
    ++LoopData;
4685
1.65k
    --Dimension;
4686
1.65k
4687
1.65k
    if (Schedule) {
4688
1.62k
      isl::union_set Domain = Schedule.get_domain();
4689
1.62k
      isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);
4690
1.62k
      Schedule = Schedule.insert_partial_schedule(MUPA);
4691
1.62k
      LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);
4692
1.62k
    }
4693
1.65k
4694
1.65k
    LoopData->NumBlocksProcessed += NumBlocksProcessed;
4695
1.65k
  }
4696
5.53k
  // Now pop all loops processed up there from the LoopStack
4697
5.53k
  LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
4698
5.53k
}
4699
4700
6.31k
ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
4701
6.31k
  auto StmtMapIt = StmtMap.find(BB);
4702
6.31k
  if (StmtMapIt == StmtMap.end())
4703
74
    return {};
4704
6.23k
  return StmtMapIt->second;
4705
6.23k
}
4706
4707
599
ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {
4708
599
  auto *PHI = cast<PHINode>(U.getUser());
4709
599
  BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
4710
599
4711
599
  // If the value is a non-synthesizable from the incoming block, use the
4712
599
  // statement that contains it as user statement.
4713
599
  if (auto *IncomingInst = dyn_cast<Instruction>(U.get())) {
4714
318
    if (IncomingInst->getParent() == IncomingBB) {
4715
175
      if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst))
4716
152
        return IncomingStmt;
4717
447
    }
4718
318
  }
4719
447
4720
447
  // Otherwise, use the epilogue/last statement.
4721
447
  return getLastStmtFor(IncomingBB);
4722
447
}
4723
4724
488
ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
4725
488
  ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
4726
488
  if (!StmtList.empty())
4727
417
    return StmtList.back();
4728
71
  return nullptr;
4729
71
}
4730
4731
5.53k
ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {
4732
5.53k
  if (RN->isSubRegion())
4733
105
    return getStmtListFor(RN->getNodeAs<Region>());
4734
5.43k
  return getStmtListFor(RN->getNodeAs<BasicBlock>());
4735
5.43k
}
4736
4737
105
ArrayRef<ScopStmt *> Scop::getStmtListFor(Region *R) const {
4738
105
  return getStmtListFor(R->getEntry());
4739
105
}
4740
4741
14.2k
int Scop::getRelativeLoopDepth(const Loop *L) const {
4742
14.2k
  if (!L || 
!R.contains(L)12.8k
)
4743
1.51k
    return -1;
4744
12.7k
  // outermostLoopInRegion always returns nullptr for top level regions
4745
12.7k
  if (R.isTopLevelRegion()) {
4746
48
    // LoopInfo's depths start at 1, we start at 0
4747
48
    return L->getLoopDepth() - 1;
4748
12.7k
  } else {
4749
12.7k
    Loop *OuterLoop = R.outermostLoopInRegion(const_cast<Loop *>(L));
4750
12.7k
    assert(OuterLoop);
4751
12.7k
    return L->getLoopDepth() - OuterLoop->getLoopDepth();
4752
12.7k
  }
4753
12.7k
}
4754
4755
255
ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
4756
519
  for (auto &SAI : arrays()) {
4757
519
    if (SAI->getName() == BaseName)
4758
254
      return SAI;
4759
519
  }
4760
255
  
return nullptr1
;
4761
255
}
4762
4763
4.75k
void Scop::addAccessData(MemoryAccess *Access) {
4764
4.75k
  const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo();
4765
4.75k
  assert(SAI && "can only use after access relations have been constructed");
4766
4.75k
4767
4.75k
  if (Access->isOriginalValueKind() && 
Access->isRead()682
)
4768
353
    ValueUseAccs[SAI].push_back(Access);
4769
4.40k
  else if (Access->isOriginalAnyPHIKind() && 
Access->isWrite()652
)
4770
424
    PHIIncomingAccs[SAI].push_back(Access);
4771
4.75k
}
4772
4773
525
void Scop::removeAccessData(MemoryAccess *Access) {
4774
525
  if (Access->isOriginalValueKind() && 
Access->isWrite()71
) {
4775
27
    ValueDefAccs.erase(Access->getAccessValue());
4776
498
  } else if (Access->isOriginalValueKind() && 
Access->isRead()44
) {
4777
44
    auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];
4778
44
    auto NewEnd = std::remove(Uses.begin(), Uses.end(), Access);
4779
44
    Uses.erase(NewEnd, Uses.end());
4780
454
  } else if (Access->isOriginalPHIKind() && 
Access->isRead()21
) {
4781
14
    PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());
4782
14
    PHIReadAccs.erase(PHI);
4783
440
  } else if (Access->isOriginalAnyPHIKind() && 
Access->isWrite()7
) {
4784
7
    auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];
4785
7
    auto NewEnd = std::remove(Incomings.begin(), Incomings.end(), Access);
4786
7
    Incomings.erase(NewEnd, Incomings.end());
4787
7
  }
4788
525
}
4789
4790
295
MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {
4791
295
  assert(SAI->isValueKind());
4792
295
4793
295
  Instruction *Val = dyn_cast<Instruction>(SAI->getBasePtr());
4794
295
  if (!Val)
4795
3
    return nullptr;
4796
292
4797
292
  return ValueDefAccs.lookup(Val);
4798
292
}
4799
4800
110
ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {
4801
110
  assert(SAI->isValueKind());
4802
110
  auto It = ValueUseAccs.find(SAI);
4803
110
  if (It == ValueUseAccs.end())
4804
0
    return {};
4805
110
  return It->second;
4806
110
}
4807
4808
188
MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {
4809
188
  assert(SAI->isPHIKind() || SAI->isExitPHIKind());
4810
188
4811
188
  if (SAI->isExitPHIKind())
4812
0
    return nullptr;
4813
188
4814
188
  PHINode *PHI = cast<PHINode>(SAI->getBasePtr());
4815
188
  return PHIReadAccs.lookup(PHI);
4816
188
}
4817
4818
232
ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {
4819
232
  assert(SAI->isPHIKind() || SAI->isExitPHIKind());
4820
232
  auto It = PHIIncomingAccs.find(SAI);
4821
232
  if (It == PHIIncomingAccs.end())
4822
0
    return {};
4823
232
  return It->second;
4824
232
}
4825
4826
21.8k
bool Scop::isEscaping(Instruction *Inst) {
4827
21.8k
  assert(contains(Inst) && "The concept of escaping makes only sense for "
4828
21.8k
                           "values defined inside the SCoP");
4829
21.8k
4830
21.8k
  for (Use &Use : Inst->uses()) {
4831
19.1k
    BasicBlock *UserBB = getUseBlock(Use);
4832
19.1k
    if (!contains(UserBB))
4833
61
      return true;
4834
19.0k
4835
19.0k
    // When the SCoP region exit needs to be simplified, PHIs in the region exit
4836
19.0k
    // move to a new basic block such that its incoming blocks are not in the
4837
19.0k
    // SCoP anymore.
4838
19.0k
    if (hasSingleExitEdge() && 
isa<PHINode>(Use.getUser())16.4k
&&
4839
19.0k
        
isExit(cast<PHINode>(Use.getUser())->getParent())1.84k
)
4840
34
      return true;
4841
19.0k
  }
4842
21.8k
  
return false21.8k
;
4843
21.8k
}
4844
4845
926
Scop::ScopStatistics Scop::getStatistics() const {
4846
926
  ScopStatistics Result;
4847
#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
4848
  auto LoopStat = ScopDetection::countBeneficialLoops(&R, *SE, *getLI(), 0);
4849
4850
  int NumTotalLoops = LoopStat.NumLoops;
4851
  Result.NumBoxedLoops = getBoxedLoops().size();
4852
  Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;
4853
4854
  for (const ScopStmt &Stmt : *this) {
4855
    isl::set Domain = Stmt.getDomain().intersect_params(getContext());
4856
    bool IsInLoop = Stmt.getNumIterators() >= 1;
4857
    for (MemoryAccess *MA : Stmt) {
4858
      if (!MA->isWrite())
4859
        continue;
4860
4861
      if (MA->isLatestValueKind()) {
4862
        Result.NumValueWrites += 1;
4863
        if (IsInLoop)
4864
          Result.NumValueWritesInLoops += 1;
4865
      }
4866
4867
      if (MA->isLatestAnyPHIKind()) {
4868
        Result.NumPHIWrites += 1;
4869
        if (IsInLoop)
4870
          Result.NumPHIWritesInLoops += 1;
4871
      }
4872
4873
      isl::set AccSet =
4874
          MA->getAccessRelation().intersect_domain(Domain).range();
4875
      if (AccSet.is_singleton()) {
4876
        Result.NumSingletonWrites += 1;
4877
        if (IsInLoop)
4878
          Result.NumSingletonWritesInLoops += 1;
4879
      }
4880
    }
4881
  }
4882
#endif
4883
  return Result;
4884
926
}
4885
4886
42
raw_ostream &polly::operator<<(raw_ostream &OS, const Scop &scop) {
4887
42
  scop.print(OS, PollyPrintInstructions);
4888
42
  return OS;
4889
42
}
4890
4891
//===----------------------------------------------------------------------===//
4892
1.13k
void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
4893
1.13k
  AU.addRequired<LoopInfoWrapperPass>();
4894
1.13k
  AU.addRequired<RegionInfoPass>();
4895
1.13k
  AU.addRequired<DominatorTreeWrapperPass>();
4896
1.13k
  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
4897
1.13k
  AU.addRequiredTransitive<ScopDetectionWrapperPass>();
4898
1.13k
  AU.addRequired<AAResultsWrapperPass>();
4899
1.13k
  AU.addRequired<AssumptionCacheTracker>();
4900
1.13k
  AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
4901
1.13k
  AU.setPreservesAll();
4902
1.13k
}
4903
4904
void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
4905
0
                              Scop::ScopStatistics ScopStats) {
4906
0
  assert(Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops);
4907
0
4908
0
  NumScops++;
4909
0
  NumLoopsInScop += Stats.NumLoops;
4910
0
  MaxNumLoopsInScop =
4911
0
      std::max(MaxNumLoopsInScop.getValue(), (unsigned)Stats.NumLoops);
4912
0
4913
0
  if (Stats.MaxDepth == 0)
4914
0
    NumScopsDepthZero++;
4915
0
  else if (Stats.MaxDepth == 1)
4916
0
    NumScopsDepthOne++;
4917
0
  else if (Stats.MaxDepth == 2)
4918
0
    NumScopsDepthTwo++;
4919
0
  else if (Stats.MaxDepth == 3)
4920
0
    NumScopsDepthThree++;
4921
0
  else if (Stats.MaxDepth == 4)
4922
0
    NumScopsDepthFour++;
4923
0
  else if (Stats.MaxDepth == 5)
4924
0
    NumScopsDepthFive++;
4925
0
  else
4926
0
    NumScopsDepthLarger++;
4927
0
4928
0
  NumAffineLoops += ScopStats.NumAffineLoops;
4929
0
  NumBoxedLoops += ScopStats.NumBoxedLoops;
4930
0
4931
0
  NumValueWrites += ScopStats.NumValueWrites;
4932
0
  NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
4933
0
  NumPHIWrites += ScopStats.NumPHIWrites;
4934
0
  NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
4935
0
  NumSingletonWrites += ScopStats.NumSingletonWrites;
4936
0
  NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
4937
0
}
4938
4939
4.27k
bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
4940
4.27k
  auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
4941
4.27k
4942
4.27k
  if (!SD.isMaxRegionInScop(*R))
4943
3.12k
    return false;
4944
1.15k
4945
1.15k
  Function *F = R->getEntry()->getParent();
4946
1.15k
  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
4947
1.15k
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
4948
1.15k
  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
4949
1.15k
  auto const &DL = F->getParent()->getDataLayout();
4950
1.15k
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4951
1.15k
  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
4952
1.15k
  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
4953
1.15k
4954
1.15k
  ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
4955
1.15k
  S = SB.getScop(); // take ownership of scop object
4956
1.15k
4957
#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
4958
  if (S) {
4959
    ScopDetection::LoopStats Stats =
4960
        ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
4961
    updateLoopCountStatistic(Stats, S->getStatistics());
4962
  }
4963
#endif
4964
4965
1.15k
  return false;
4966
1.15k
}
4967
4968
1.51k
void ScopInfoRegionPass::print(raw_ostream &OS, const Module *) const {
4969
1.51k
  if (S)
4970
409
    S->print(OS, PollyPrintInstructions);
4971
1.10k
  else
4972
1.10k
    OS << "Invalid Scop!\n";
4973
1.51k
}
4974
4975
char ScopInfoRegionPass::ID = 0;
4976
4977
0
Pass *polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
4978
4979
47.0k
INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",
4980
47.0k
                      "Polly - Create polyhedral description of Scops", false,
4981
47.0k
                      false);
4982
47.0k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
4983
47.0k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
4984
47.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
4985
47.0k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
4986
47.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
4987
47.0k
INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
4988
47.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
4989
47.0k
INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
4990
                    "Polly - Create polyhedral description of Scops", false,
4991
                    false)
4992
4993
//===----------------------------------------------------------------------===//
4994
ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
4995
                   LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
4996
                   AssumptionCache &AC, OptimizationRemarkEmitter &ORE)
4997
50
    : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {
4998
50
  recompute();
4999
50
}
5000
5001
50
void ScopInfo::recompute() {
5002
50
  RegionToScopMap.clear();
5003
50
  /// Create polyhedral description of scops for all the valid regions of a
5004
50
  /// function.
5005
50
  for (auto &It : SD) {
5006
49
    Region *R = const_cast<Region *>(It);
5007
49
    if (!SD.isMaxRegionInScop(*R))
5008
0
      continue;
5009
49
5010
49
    ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
5011
49
    std::unique_ptr<Scop> S = SB.getScop();
5012
49
    if (!S)
5013
3
      continue;
5014
#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
5015
    ScopDetection::LoopStats Stats =
5016
        ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
5017
    updateLoopCountStatistic(Stats, S->getStatistics());
5018
#endif
5019
46
    bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second;
5020
46
    assert(Inserted && "Building Scop for the same region twice!");
5021
46
    (void)Inserted;
5022
46
  }
5023
50
}
5024
5025
bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
5026
0
                          FunctionAnalysisManager::Invalidator &Inv) {
5027
0
  // Check whether the analysis, all analyses on functions have been preserved
5028
0
  // or anything we're holding references to is being invalidated
5029
0
  auto PAC = PA.getChecker<ScopInfoAnalysis>();
5030
0
  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
5031
0
         Inv.invalidate<ScopAnalysis>(F, PA) ||
5032
0
         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
5033
0
         Inv.invalidate<LoopAnalysis>(F, PA) ||
5034
0
         Inv.invalidate<AAManager>(F, PA) ||
5035
0
         Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
5036
0
         Inv.invalidate<AssumptionAnalysis>(F, PA);
5037
0
}
5038
5039
AnalysisKey ScopInfoAnalysis::Key;
5040
5041
ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
5042
1
                                               FunctionAnalysisManager &FAM) {
5043
1
  auto &SD = FAM.getResult<ScopAnalysis>(F);
5044
1
  auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
5045
1
  auto &LI = FAM.getResult<LoopAnalysis>(F);
5046
1
  auto &AA = FAM.getResult<AAManager>(F);
5047
1
  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
5048
1
  auto &AC = FAM.getResult<AssumptionAnalysis>(F);
5049
1
  auto &DL = F.getParent()->getDataLayout();
5050
1
  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
5051
1
  return {DL, SD, SE, LI, AA, DT, AC, ORE};
5052
1
}
5053
5054
PreservedAnalyses ScopInfoPrinterPass::run(Function &F,
5055
0
                                           FunctionAnalysisManager &FAM) {
5056
0
  auto &SI = FAM.getResult<ScopInfoAnalysis>(F);
5057
0
  // Since the legacy PM processes Scops in bottom up, we print them in reverse
5058
0
  // order here to keep the output persistent
5059
0
  for (auto &It : reverse(SI)) {
5060
0
    if (It.second)
5061
0
      It.second->print(Stream, PollyPrintInstructions);
5062
0
    else
5063
0
      Stream << "Invalid Scop!\n";
5064
0
  }
5065
0
  return PreservedAnalyses::all();
5066
0
}
5067
5068
44
void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
5069
44
  AU.addRequired<LoopInfoWrapperPass>();
5070
44
  AU.addRequired<RegionInfoPass>();
5071
44
  AU.addRequired<DominatorTreeWrapperPass>();
5072
44
  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
5073
44
  AU.addRequiredTransitive<ScopDetectionWrapperPass>();
5074
44
  AU.addRequired<AAResultsWrapperPass>();
5075
44
  AU.addRequired<AssumptionCacheTracker>();
5076
44
  AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
5077
44
  AU.setPreservesAll();
5078
44
}
5079
5080
49
bool ScopInfoWrapperPass::runOnFunction(Function &F) {
5081
49
  auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
5082
49
  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
5083
49
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
5084
49
  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
5085
49
  auto const &DL = F.getParent()->getDataLayout();
5086
49
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
5087
49
  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
5088
49
  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
5089
49
5090
49
  Result.reset(new ScopInfo{DL, SD, SE, LI, AA, DT, AC, ORE});
5091
49
  return false;
5092
49
}
5093
5094
23
void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
5095
23
  for (auto &It : *Result) {
5096
21
    if (It.second)
5097
21
      It.second->print(OS, PollyPrintInstructions);
5098
0
    else
5099
0
      OS << "Invalid Scop!\n";
5100
21
  }
5101
23
}
5102
5103
char ScopInfoWrapperPass::ID = 0;
5104
5105
0
Pass *polly::createScopInfoWrapperPassPass() {
5106
0
  return new ScopInfoWrapperPass();
5107
0
}
5108
5109
47.0k
INITIALIZE_PASS_BEGIN(
5110
47.0k
    ScopInfoWrapperPass, "polly-function-scops",
5111
47.0k
    "Polly - Create polyhedral description of all Scops of a function", false,
5112
47.0k
    false);
5113
47.0k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
5114
47.0k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
5115
47.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
5116
47.0k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
5117
47.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
5118
47.0k
INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
5119
47.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
5120
47.0k
INITIALIZE_PASS_END(
5121
    ScopInfoWrapperPass, "polly-function-scops",
5122
    "Polly - Create polyhedral description of all Scops of a function", false,
5123
    false)