Coverage Report

Created: 2018-04-24 22:41

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