Coverage Report

Created: 2018-12-13 20:48

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