Coverage Report

Created: 2017-11-23 03:11

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