Coverage Report

Created: 2017-08-18 19:41

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