Coverage Report

Created: 2017-10-03 07:32

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