Coverage Report

Created: 2018-06-19 22:08

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