Coverage Report

Created: 2017-06-23 12:40

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