Coverage Report

Created: 2017-06-23 12:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Analysis/ScopBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScopBuilder.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
//===----------------------------------------------------------------------===//
16
17
#include "polly/ScopBuilder.h"
18
#include "polly/Options.h"
19
#include "polly/Support/GICHelper.h"
20
#include "polly/Support/SCEVValidator.h"
21
#include "polly/Support/VirtualInstruction.h"
22
#include "llvm/Analysis/RegionIterator.h"
23
#include "llvm/IR/DiagnosticInfo.h"
24
25
using namespace llvm;
26
using namespace polly;
27
28
2.05k
#define DEBUG_TYPE "polly-scops"
29
30
STATISTIC(ScopFound, "Number of valid Scops");
31
STATISTIC(RichScopFound, "Number of Scops containing a loop");
32
STATISTIC(InfeasibleScops,
33
          "Number of SCoPs with statically infeasible context.");
34
35
static cl::opt<bool> ModelReadOnlyScalars(
36
    "polly-analyze-read-only-scalars",
37
    cl::desc("Model read-only scalar values in the scop description"),
38
    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
39
40
static cl::opt<bool> UnprofitableScalarAccs(
41
    "polly-unprofitable-scalar-accs",
42
    cl::desc("Count statements with scalar accesses as not optimizable"),
43
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
44
45
static cl::opt<bool> DetectFortranArrays(
46
    "polly-detect-fortran-arrays",
47
    cl::desc("Detect Fortran arrays and use this for code generation"),
48
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
49
50
void ScopBuilder::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
51
1.67k
                                   bool IsExitBlock) {
52
1.67k
53
1.67k
  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
54
1.67k
  // true, are not modeled as ordinary PHI nodes as they are not part of the
55
1.67k
  // region. However, we model the operands in the predecessor blocks that are
56
1.67k
  // part of the region as regular scalar accesses.
57
1.67k
58
1.67k
  // If we can synthesize a PHI we can skip it, however only if it is in
59
1.67k
  // the region. If it is not it can only be in the exit block of the region.
60
1.67k
  // In this case we model the operands but not the PHI itself.
61
1.67k
  auto *Scope = LI.getLoopFor(PHI->getParent());
62
1.67k
  if (
!IsExitBlock && 1.67k
canSynthesize(PHI, *scop, &SE, Scope)1.63k
)
63
1.45k
    return;
64
1.67k
65
1.67k
  // PHI nodes are modeled as if they had been demoted prior to the SCoP
66
1.67k
  // detection. Hence, the PHI is a load of a new memory location in which the
67
1.67k
  // incoming value was written at the end of the incoming basic block.
68
219
  bool OnlyNonAffineSubRegionOperands = true;
69
708
  for (unsigned u = 0; 
u < PHI->getNumIncomingValues()708
;
u++489
)
{489
70
489
    Value *Op = PHI->getIncomingValue(u);
71
489
    BasicBlock *OpBB = PHI->getIncomingBlock(u);
72
489
73
489
    // Do not build PHI dependences inside a non-affine subregion, but make
74
489
    // sure that the necessary scalar values are still made available.
75
489
    if (
NonAffineSubRegion && 489
NonAffineSubRegion->contains(OpBB)79
)
{19
76
19
      auto *OpInst = dyn_cast<Instruction>(Op);
77
19
      if (
!OpInst || 19
!NonAffineSubRegion->contains(OpInst)10
)
78
10
        ensureValueRead(Op, OpBB);
79
19
      continue;
80
19
    }
81
489
82
470
    OnlyNonAffineSubRegionOperands = false;
83
470
    ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
84
470
  }
85
219
86
219
  if (
!OnlyNonAffineSubRegionOperands && 219
!IsExitBlock213
)
{171
87
171
    addPHIReadAccess(PHI);
88
171
  }
89
219
}
90
91
12.3k
void ScopBuilder::buildScalarDependences(Instruction *Inst) {
92
12.3k
  assert(!isa<PHINode>(Inst));
93
12.3k
94
12.3k
  // Pull-in required operands.
95
12.3k
  for (Use &Op : Inst->operands())
96
23.1k
    ensureValueRead(Op.get(), Inst->getParent());
97
12.3k
}
98
99
18.8k
void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
100
18.8k
  // Check for uses of this instruction outside the scop. Because we do not
101
18.8k
  // iterate over such instructions and therefore did not "ensure" the existence
102
18.8k
  // of a write, we must determine such use here.
103
16.5k
  for (Use &U : Inst->uses()) {
104
16.5k
    Instruction *UI = dyn_cast<Instruction>(U.getUser());
105
16.5k
    if (!UI)
106
0
      continue;
107
16.5k
108
16.5k
    BasicBlock *UseParent = getUseBlock(U);
109
16.5k
    BasicBlock *UserParent = UI->getParent();
110
16.5k
111
16.5k
    // An escaping value is either used by an instruction not within the scop,
112
16.5k
    // or (when the scop region's exit needs to be simplified) by a PHI in the
113
16.5k
    // scop's exit block. This is because region simplification before code
114
16.5k
    // generation inserts new basic blocks before the PHI such that its incoming
115
16.5k
    // blocks are not in the scop anymore.
116
16.5k
    if (!scop->contains(UseParent) ||
117
16.5k
        
(isa<PHINode>(UI) && 16.5k
scop->isExit(UserParent)1.69k
&&
118
89
         
scop->hasSingleExitEdge()55
))
{89
119
89
      // At least one escaping use found.
120
89
      ensureValueWrite(Inst);
121
89
      break;
122
89
    }
123
16.5k
  }
124
18.8k
}
125
126
/// Check that a value is a Fortran Array descriptor.
127
///
128
/// We check if V has the following structure:
129
/// %"struct.array1_real(kind=8)" = type { i8*, i<zz>, i<zz>,
130
///                                   [<num> x %struct.descriptor_dimension] }
131
///
132
///
133
/// %struct.descriptor_dimension = type { i<zz>, i<zz>, i<zz> }
134
///
135
/// 1. V's type name starts with "struct.array"
136
/// 2. V's type has layout as shown.
137
/// 3. Final member of V's type has name "struct.descriptor_dimension",
138
/// 4. "struct.descriptor_dimension" has layout as shown.
139
/// 5. Consistent use of i<zz> where <zz> is some fixed integer number.
140
///
141
/// We are interested in such types since this is the code that dragonegg
142
/// generates for Fortran array descriptors.
143
///
144
/// @param V the Value to be checked.
145
///
146
/// @returns True if V is a Fortran array descriptor, False otherwise.
147
10
bool isFortranArrayDescriptor(Value *V) {
148
10
  PointerType *PTy = dyn_cast<PointerType>(V->getType());
149
10
150
10
  if (!PTy)
151
0
    return false;
152
10
153
10
  Type *Ty = PTy->getElementType();
154
10
  assert(Ty && "Ty expected to be initialized");
155
10
  auto *StructArrTy = dyn_cast<StructType>(Ty);
156
10
157
10
  if (
!(StructArrTy && 10
StructArrTy->hasName()10
))
158
0
    return false;
159
10
160
10
  
if (10
!StructArrTy->getName().startswith("struct.array")10
)
161
0
    return false;
162
10
163
10
  
if (10
StructArrTy->getNumElements() != 410
)
164
0
    return false;
165
10
166
10
  const ArrayRef<Type *> ArrMemberTys = StructArrTy->elements();
167
10
168
10
  // i8* match
169
10
  if (ArrMemberTys[0] != Type::getInt8PtrTy(V->getContext()))
170
0
    return false;
171
10
172
10
  // Get a reference to the int type and check that all the members
173
10
  // share the same int type
174
10
  Type *IntTy = ArrMemberTys[1];
175
10
  if (ArrMemberTys[2] != IntTy)
176
0
    return false;
177
10
178
10
  // type: [<num> x %struct.descriptor_dimension]
179
10
  ArrayType *DescriptorDimArrayTy = dyn_cast<ArrayType>(ArrMemberTys[3]);
180
10
  if (!DescriptorDimArrayTy)
181
0
    return false;
182
10
183
10
  // type: %struct.descriptor_dimension := type { ixx, ixx, ixx }
184
10
  StructType *DescriptorDimTy =
185
10
      dyn_cast<StructType>(DescriptorDimArrayTy->getElementType());
186
10
187
10
  if (
!(DescriptorDimTy && 10
DescriptorDimTy->hasName()10
))
188
0
    return false;
189
10
190
10
  
if (10
DescriptorDimTy->getName() != "struct.descriptor_dimension"10
)
191
0
    return false;
192
10
193
10
  
if (10
DescriptorDimTy->getNumElements() != 310
)
194
0
    return false;
195
10
196
30
  
for (auto MemberTy : DescriptorDimTy->elements()) 10
{30
197
30
    if (MemberTy != IntTy)
198
0
      return false;
199
30
  }
200
10
201
10
  return true;
202
10
}
203
204
5
Value *ScopBuilder::findFADAllocationVisible(MemAccInst Inst) {
205
5
  // match: 4.1 & 4.2 store/load
206
5
  if (
!isa<LoadInst>(Inst) && 5
!isa<StoreInst>(Inst)1
)
207
0
    return nullptr;
208
5
209
5
  // match: 4
210
5
  
if (5
Inst.getAlignment() != 85
)
211
1
    return nullptr;
212
5
213
4
  Value *Address = Inst.getPointerOperand();
214
4
215
4
  const BitCastInst *Bitcast = nullptr;
216
4
  // [match: 3]
217
4
  if (auto *
Slot4
= dyn_cast<GetElementPtrInst>(Address))
{3
218
3
    Value *TypedMem = Slot->getPointerOperand();
219
3
    // match: 2
220
3
    Bitcast = dyn_cast<BitCastInst>(TypedMem);
221
1
  } else {
222
1
    // match: 2
223
1
    Bitcast = dyn_cast<BitCastInst>(Address);
224
1
  }
225
4
226
4
  if (!Bitcast)
227
1
    return nullptr;
228
4
229
3
  auto *MallocMem = Bitcast->getOperand(0);
230
3
231
3
  // match: 1
232
3
  auto *MallocCall = dyn_cast<CallInst>(MallocMem);
233
3
  if (!MallocCall)
234
1
    return nullptr;
235
3
236
2
  Function *MallocFn = MallocCall->getCalledFunction();
237
2
  if (
!(MallocFn && 2
MallocFn->hasName()2
&&
MallocFn->getName() == "malloc"2
))
238
0
    return nullptr;
239
2
240
2
  // Find all uses the malloc'd memory.
241
2
  // We are looking for a "store" into a struct with the type being the Fortran
242
2
  // descriptor type
243
4
  
for (auto user : MallocMem->users()) 2
{4
244
4
245
4
    /// match: 5
246
4
    auto *MallocStore = dyn_cast<StoreInst>(user);
247
4
    if (!MallocStore)
248
2
      continue;
249
4
250
2
    auto *DescriptorGEP =
251
2
        dyn_cast<GEPOperator>(MallocStore->getPointerOperand());
252
2
    if (!DescriptorGEP)
253
0
      continue;
254
2
255
2
    // match: 5
256
2
    auto DescriptorType =
257
2
        dyn_cast<StructType>(DescriptorGEP->getSourceElementType());
258
2
    if (
!(DescriptorType && 2
DescriptorType->hasName()2
))
259
0
      continue;
260
2
261
2
    Value *Descriptor = dyn_cast<Value>(DescriptorGEP->getPointerOperand());
262
2
263
2
    if (!Descriptor)
264
0
      continue;
265
2
266
2
    
if (2
!isFortranArrayDescriptor(Descriptor)2
)
267
0
      continue;
268
2
269
2
    return Descriptor;
270
2
  }
271
2
272
0
  return nullptr;
273
2
}
274
275
13
Value *ScopBuilder::findFADAllocationInvisible(MemAccInst Inst) {
276
13
  // match: 3
277
13
  if (
!isa<LoadInst>(Inst) && 13
!isa<StoreInst>(Inst)5
)
278
0
    return nullptr;
279
13
280
13
  Value *Slot = Inst.getPointerOperand();
281
13
282
13
  LoadInst *MemLoad = nullptr;
283
13
  // [match: 2]
284
13
  if (auto *
SlotGEP13
= dyn_cast<GetElementPtrInst>(Slot))
{11
285
11
    // match: 1
286
11
    MemLoad = dyn_cast<LoadInst>(SlotGEP->getPointerOperand());
287
2
  } else {
288
2
    // match: 1
289
2
    MemLoad = dyn_cast<LoadInst>(Slot);
290
2
  }
291
13
292
13
  if (!MemLoad)
293
5
    return nullptr;
294
13
295
8
  auto *BitcastOperator =
296
8
      dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
297
8
  if (!BitcastOperator)
298
0
    return nullptr;
299
8
300
8
  Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
301
8
  if (!Descriptor)
302
0
    return nullptr;
303
8
304
8
  
if (8
!isFortranArrayDescriptor(Descriptor)8
)
305
0
    return nullptr;
306
8
307
8
  return Descriptor;
308
8
}
309
310
3.11k
bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
311
3.11k
  Value *Val = Inst.getValueOperand();
312
3.11k
  Type *ElementType = Val->getType();
313
3.11k
  Value *Address = Inst.getPointerOperand();
314
3.11k
  const SCEV *AccessFunction =
315
3.11k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
316
3.11k
  const SCEVUnknown *BasePointer =
317
3.11k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
318
3.11k
  enum MemoryAccess::AccessType AccType =
319
1.61k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.61k
:
MemoryAccess::MUST_WRITE1.50k
;
320
3.11k
321
3.11k
  if (auto *
BitCast3.11k
= dyn_cast<BitCastInst>(Address))
{78
322
78
    auto *Src = BitCast->getOperand(0);
323
78
    auto *SrcTy = Src->getType();
324
78
    auto *DstTy = BitCast->getType();
325
78
    // Do not try to delinearize non-sized (opaque) pointers.
326
78
    if (
(SrcTy->isPointerTy() && 78
!SrcTy->getPointerElementType()->isSized()78
) ||
327
77
        
(DstTy->isPointerTy() && 77
!DstTy->getPointerElementType()->isSized()77
))
{1
328
1
      return false;
329
1
    }
330
77
    
if (77
SrcTy->isPointerTy() && 77
DstTy->isPointerTy()77
&&
331
77
        DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
332
77
            DL.getTypeAllocSize(DstTy->getPointerElementType()))
333
35
      Address = Src;
334
77
  }
335
3.11k
336
3.11k
  auto *GEP = dyn_cast<GetElementPtrInst>(Address);
337
3.11k
  if (!GEP)
338
725
    return false;
339
3.11k
340
2.38k
  std::vector<const SCEV *> Subscripts;
341
2.38k
  std::vector<int> Sizes;
342
2.38k
  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
343
2.38k
  auto *BasePtr = GEP->getOperand(0);
344
2.38k
345
2.38k
  if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
346
16
    BasePtr = BasePtrCast->getOperand(0);
347
2.38k
348
2.38k
  // Check for identical base pointers to ensure that we do not miss index
349
2.38k
  // offsets that have been added before this GEP is applied.
350
2.38k
  if (BasePtr != BasePointer->getValue())
351
79
    return false;
352
2.38k
353
2.30k
  std::vector<const SCEV *> SizesSCEV;
354
2.30k
355
2.30k
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
356
2.30k
357
2.30k
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
358
2.38k
  for (auto *Subscript : Subscripts) {
359
2.38k
    InvariantLoadsSetTy AccessILS;
360
2.38k
    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
361
2.38k
                      &AccessILS))
362
150
      return false;
363
2.38k
364
2.23k
    for (LoadInst *LInst : AccessILS)
365
45
      
if (45
!ScopRIL.count(LInst)45
)
366
3
        return false;
367
2.23k
  }
368
2.30k
369
2.15k
  
if (2.15k
Sizes.empty()2.15k
)
370
1.96k
    return false;
371
2.15k
372
193
  SizesSCEV.push_back(nullptr);
373
193
374
193
  for (auto V : Sizes)
375
212
    SizesSCEV.push_back(SE.getSCEV(
376
212
        ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
377
193
378
193
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
379
193
                 Subscripts, SizesSCEV, Val);
380
193
  return true;
381
2.15k
}
382
383
2.92k
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
384
2.92k
  if (!PollyDelinearize)
385
6
    return false;
386
2.92k
387
2.91k
  Value *Address = Inst.getPointerOperand();
388
2.91k
  Value *Val = Inst.getValueOperand();
389
2.91k
  Type *ElementType = Val->getType();
390
2.91k
  unsigned ElementSize = DL.getTypeAllocSize(ElementType);
391
2.91k
  enum MemoryAccess::AccessType AccType =
392
1.51k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.51k
:
MemoryAccess::MUST_WRITE1.40k
;
393
2.91k
394
2.91k
  const SCEV *AccessFunction =
395
2.91k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
396
2.91k
  const SCEVUnknown *BasePointer =
397
2.91k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
398
2.91k
399
2.91k
  assert(BasePointer && "Could not find base pointer");
400
2.91k
401
2.91k
  auto &InsnToMemAcc = scop->getInsnToMemAccMap();
402
2.91k
  auto AccItr = InsnToMemAcc.find(Inst);
403
2.91k
  if (AccItr == InsnToMemAcc.end())
404
2.74k
    return false;
405
2.91k
406
173
  std::vector<const SCEV *> Sizes = {nullptr};
407
173
408
173
  Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
409
173
               AccItr->second.Shape->DelinearizedSizes.end());
410
173
411
173
  // In case only the element size is contained in the 'Sizes' array, the
412
173
  // access does not access a real multi-dimensional array. Hence, we allow
413
173
  // the normal single-dimensional access construction to handle this.
414
173
  if (Sizes.size() == 1)
415
1
    return false;
416
173
417
173
  // Remove the element size. This information is already provided by the
418
173
  // ElementSize parameter. In case the element size of this access and the
419
173
  // element size used for delinearization differs the delinearization is
420
173
  // incorrect. Hence, we invalidate the scop.
421
173
  //
422
173
  // TODO: Handle delinearization with differing element sizes.
423
172
  auto DelinearizedSize =
424
172
      cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
425
172
  Sizes.pop_back();
426
172
  if (ElementSize != DelinearizedSize)
427
2
    scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
428
172
429
172
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
430
172
                 AccItr->second.DelinearizedSubscripts, Sizes, Val);
431
172
  return true;
432
173
}
433
434
3.18k
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
435
3.18k
  auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
436
3.18k
437
3.18k
  if (MemIntr == nullptr)
438
3.16k
    return false;
439
3.18k
440
13
  auto *L = LI.getLoopFor(Inst->getParent());
441
13
  auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
442
13
  assert(LengthVal);
443
13
444
13
  // Check if the length val is actually affine or if we overapproximate it
445
13
  InvariantLoadsSetTy AccessILS;
446
13
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
447
13
448
13
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
449
13
  bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
450
13
                                     LengthVal, SE, &AccessILS);
451
13
  for (LoadInst *LInst : AccessILS)
452
0
    
if (0
!ScopRIL.count(LInst)0
)
453
0
      LengthIsAffine = false;
454
13
  if (!LengthIsAffine)
455
2
    LengthVal = nullptr;
456
13
457
13
  auto *DestPtrVal = MemIntr->getDest();
458
13
  assert(DestPtrVal);
459
13
460
13
  auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
461
13
  assert(DestAccFunc);
462
13
  // Ignore accesses to "NULL".
463
13
  // TODO: We could use this to optimize the region further, e.g., intersect
464
13
  //       the context with
465
13
  //          isl_set_complement(isl_set_params(getDomain()))
466
13
  //       as we know it would be undefined to execute this instruction anyway.
467
13
  if (DestAccFunc->isZero())
468
2
    return true;
469
13
470
11
  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
471
11
  assert(DestPtrSCEV);
472
11
  DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
473
11
  addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
474
11
                 IntegerType::getInt8Ty(DestPtrVal->getContext()),
475
11
                 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
476
11
                 Inst.getValueOperand());
477
11
478
11
  auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
479
11
  if (!MemTrans)
480
5
    return true;
481
11
482
6
  auto *SrcPtrVal = MemTrans->getSource();
483
6
  assert(SrcPtrVal);
484
6
485
6
  auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
486
6
  assert(SrcAccFunc);
487
6
  // Ignore accesses to "NULL".
488
6
  // TODO: See above TODO
489
6
  if (SrcAccFunc->isZero())
490
0
    return true;
491
6
492
6
  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
493
6
  assert(SrcPtrSCEV);
494
6
  SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
495
6
  addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
496
6
                 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
497
6
                 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
498
6
                 Inst.getValueOperand());
499
6
500
6
  return true;
501
6
}
502
503
3.16k
bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
504
3.16k
  auto *CI = dyn_cast_or_null<CallInst>(Inst);
505
3.16k
506
3.16k
  if (CI == nullptr)
507
3.11k
    return false;
508
3.16k
509
54
  
if (54
CI->doesNotAccessMemory() || 54
isIgnoredIntrinsic(CI)25
)
510
40
    return true;
511
54
512
14
  bool ReadOnly = false;
513
14
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
514
14
  auto *CalledFunction = CI->getCalledFunction();
515
14
  switch (AA.getModRefBehavior(CalledFunction)) {
516
0
  case FMRB_UnknownModRefBehavior:
517
0
    llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
518
0
  case FMRB_DoesNotAccessMemory:
519
0
    return true;
520
0
  case FMRB_DoesNotReadMemory:
521
0
  case FMRB_OnlyAccessesInaccessibleMem:
522
0
  case FMRB_OnlyAccessesInaccessibleOrArgMem:
523
0
    return false;
524
8
  case FMRB_OnlyReadsMemory:
525
8
    GlobalReads.push_back(CI);
526
8
    return true;
527
4
  case FMRB_OnlyReadsArgumentPointees:
528
4
    ReadOnly = true;
529
4
  // Fall through
530
6
  case FMRB_OnlyAccessesArgumentPointees:
531
4
    auto AccType = ReadOnly ? 
MemoryAccess::READ4
:
MemoryAccess::MAY_WRITE2
;
532
6
    Loop *L = LI.getLoopFor(Inst->getParent());
533
16
    for (const auto &Arg : CI->arg_operands()) {
534
16
      if (!Arg->getType()->isPointerTy())
535
6
        continue;
536
16
537
10
      auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
538
10
      if (ArgSCEV->isZero())
539
4
        continue;
540
10
541
6
      auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
542
6
      addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
543
6
                     ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
544
6
    }
545
6
    return true;
546
14
  }
547
14
548
0
  return true;
549
14
}
550
551
2.74k
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
552
2.74k
  Value *Address = Inst.getPointerOperand();
553
2.74k
  Value *Val = Inst.getValueOperand();
554
2.74k
  Type *ElementType = Val->getType();
555
2.74k
  enum MemoryAccess::AccessType AccType =
556
1.41k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.41k
:
MemoryAccess::MUST_WRITE1.33k
;
557
2.74k
558
2.74k
  const SCEV *AccessFunction =
559
2.74k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
560
2.74k
  const SCEVUnknown *BasePointer =
561
2.74k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
562
2.74k
563
2.74k
  assert(BasePointer && "Could not find base pointer");
564
2.74k
  AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
565
2.74k
566
2.74k
  // Check if the access depends on a loop contained in a non-affine subregion.
567
2.74k
  bool isVariantInNonAffineLoop = false;
568
2.74k
  SetVector<const Loop *> Loops;
569
2.74k
  findLoops(AccessFunction, Loops);
570
2.74k
  for (const Loop *L : Loops)
571
1.59k
    
if (1.59k
Stmt->contains(L)1.59k
)
{8
572
8
      isVariantInNonAffineLoop = true;
573
8
      break;
574
8
    }
575
2.74k
576
2.74k
  InvariantLoadsSetTy AccessILS;
577
2.74k
578
2.74k
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
579
2.74k
  bool IsAffine = !isVariantInNonAffineLoop &&
580
2.74k
                  isAffineExpr(&scop->getRegion(), SurroundingLoop,
581
2.74k
                               AccessFunction, SE, &AccessILS);
582
2.74k
583
2.74k
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
584
2.74k
  for (LoadInst *LInst : AccessILS)
585
49
    
if (49
!ScopRIL.count(LInst)49
)
586
7
      IsAffine = false;
587
2.74k
588
2.74k
  if (
!IsAffine && 2.74k
AccType == MemoryAccess::MUST_WRITE40
)
589
25
    AccType = MemoryAccess::MAY_WRITE;
590
2.74k
591
2.74k
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
592
2.74k
                 {AccessFunction}, {nullptr}, Val);
593
2.74k
}
594
595
3.18k
void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
596
3.18k
597
3.18k
  if (buildAccessMemIntrinsic(Inst, Stmt))
598
13
    return;
599
3.18k
600
3.16k
  
if (3.16k
buildAccessCallInst(Inst, Stmt)3.16k
)
601
54
    return;
602
3.16k
603
3.11k
  
if (3.11k
buildAccessMultiDimFixed(Inst, Stmt)3.11k
)
604
193
    return;
605
3.11k
606
2.92k
  
if (2.92k
buildAccessMultiDimParam(Inst, Stmt)2.92k
)
607
172
    return;
608
2.92k
609
2.74k
  buildAccessSingleDim(Inst, Stmt);
610
2.74k
}
611
612
2.15k
void ScopBuilder::buildAccessFunctions(Region &SR) {
613
2.15k
614
2.15k
  if (
scop->isNonAffineSubRegion(&SR)2.15k
)
{103
615
103
    for (BasicBlock *BB : SR.blocks())
616
290
      buildAccessFunctions(*BB, &SR);
617
103
    return;
618
103
  }
619
2.15k
620
8.00k
  
for (auto I = SR.element_begin(), E = SR.element_end(); 2.05k
I != E8.00k
;
++I5.94k
)
621
5.94k
    
if (5.94k
I->isSubRegion()5.94k
)
622
1.12k
      buildAccessFunctions(*I->getNodeAs<Region>());
623
5.94k
    else
624
4.82k
      buildAccessFunctions(*I->getNodeAs<BasicBlock>());
625
2.05k
}
626
627
2.15k
void ScopBuilder::buildStmts(Region &SR) {
628
2.15k
629
2.15k
  if (
scop->isNonAffineSubRegion(&SR)2.15k
)
{103
630
103
    Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
631
103
    auto &BoxedLoops = scop->getBoxedLoops();
632
115
    while (BoxedLoops.count(SurroundingLoop))
633
12
      SurroundingLoop = SurroundingLoop->getParentLoop();
634
103
    scop->addScopStmt(&SR, SurroundingLoop);
635
103
    return;
636
103
  }
637
2.15k
638
8.00k
  
for (auto I = SR.element_begin(), E = SR.element_end(); 2.05k
I != E8.00k
;
++I5.94k
)
639
5.94k
    
if (5.94k
I->isSubRegion()5.94k
)
640
1.12k
      buildStmts(*I->getNodeAs<Region>());
641
4.82k
    else {
642
4.82k
      std::vector<Instruction *> Instructions;
643
17.7k
      for (Instruction &Inst : *I->getNodeAs<BasicBlock>()) {
644
17.7k
        Loop *L = LI.getLoopFor(Inst.getParent());
645
17.7k
        if (
!isa<TerminatorInst>(&Inst) && 17.7k
!isIgnoredIntrinsic(&Inst)12.9k
&&
646
12.9k
            !canSynthesize(&Inst, *scop, &SE, L))
647
6.58k
          Instructions.push_back(&Inst);
648
17.7k
      }
649
4.82k
      Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
650
4.82k
      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
651
4.82k
                        Instructions);
652
4.82k
    }
653
2.05k
}
654
655
void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
656
                                       Region *NonAffineSubRegion,
657
5.26k
                                       bool IsExitBlock) {
658
5.26k
  // We do not build access functions for error blocks, as they may contain
659
5.26k
  // instructions we can not model.
660
5.26k
  if (
isErrorBlock(BB, scop->getRegion(), LI, DT) && 5.26k
!IsExitBlock41
)
661
41
    return;
662
5.26k
663
5.22k
  ScopStmt *Stmt = scop->getStmtFor(&BB);
664
5.22k
665
19.0k
  for (Instruction &Inst : BB) {
666
19.0k
    PHINode *PHI = dyn_cast<PHINode>(&Inst);
667
19.0k
    if (PHI)
668
1.67k
      buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
669
19.0k
670
19.0k
    // For the exit block we stop modeling after the last PHI node.
671
19.0k
    if (
!PHI && 19.0k
IsExitBlock17.3k
)
672
151
      break;
673
19.0k
674
18.8k
    
if (auto 18.8k
MemInst18.8k
= MemAccInst::dyn_cast(Inst))
{3.18k
675
3.18k
      assert(Stmt && "Cannot build access function in non-existing statement");
676
3.18k
      buildMemoryAccess(MemInst, Stmt);
677
3.18k
    }
678
18.8k
679
18.8k
    if (isIgnoredIntrinsic(&Inst))
680
28
      continue;
681
18.8k
682
18.8k
    // PHI nodes have already been modeled above and TerminatorInsts that are
683
18.8k
    // not part of a non-affine subregion are fully modeled and regenerated
684
18.8k
    // from the polyhedral domains. Hence, they do not need to be modeled as
685
18.8k
    // explicit data dependences.
686
18.8k
    
if (18.8k
!PHI && 18.8k
(!isa<TerminatorInst>(&Inst) || 17.1k
NonAffineSubRegion5.06k
))
687
12.3k
      buildScalarDependences(&Inst);
688
18.8k
689
18.8k
    if (!IsExitBlock)
690
18.8k
      buildEscapingDependences(&Inst);
691
18.8k
  }
692
5.22k
}
693
694
MemoryAccess *ScopBuilder::addMemoryAccess(
695
    BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
696
    Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
697
    ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
698
4.27k
    MemoryKind Kind) {
699
4.27k
  ScopStmt *Stmt = scop->getStmtFor(BB);
700
4.27k
701
4.27k
  // Do not create a memory access for anything not in the SCoP. It would be
702
4.27k
  // ignored anyway.
703
4.27k
  if (!Stmt)
704
0
    return nullptr;
705
4.27k
706
4.27k
  bool isKnownMustAccess = false;
707
4.27k
708
4.27k
  // Accesses in single-basic block statements are always executed.
709
4.27k
  if (Stmt->isBlockStmt())
710
3.89k
    isKnownMustAccess = true;
711
4.27k
712
4.27k
  if (
Stmt->isRegionStmt()4.27k
)
{374
713
374
    // Accesses that dominate the exit block of a non-affine region are always
714
374
    // executed. In non-affine regions there may exist MemoryKind::Values that
715
374
    // do not dominate the exit. MemoryKind::Values will always dominate the
716
374
    // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
717
374
    // non-affine region.
718
374
    if (DT.dominates(BB, Stmt->getRegion()->getExit()))
719
241
      isKnownMustAccess = true;
720
374
  }
721
4.27k
722
4.27k
  // Non-affine PHI writes do not "happen" at a particular instruction, but
723
4.27k
  // after exiting the statement. Therefore they are guaranteed to execute and
724
4.27k
  // overwrite the old value.
725
4.27k
  if (
Kind == MemoryKind::PHI || 4.27k
Kind == MemoryKind::ExitPHI3.84k
)
726
534
    isKnownMustAccess = true;
727
4.27k
728
4.27k
  if (
!isKnownMustAccess && 4.27k
AccType == MemoryAccess::MUST_WRITE124
)
729
65
    AccType = MemoryAccess::MAY_WRITE;
730
4.27k
731
4.27k
  auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
732
4.27k
                                  Affine, Subscripts, Sizes, AccessValue, Kind);
733
4.27k
734
4.27k
  scop->addAccessFunction(Access);
735
4.27k
  Stmt->addAccess(Access);
736
4.27k
  return Access;
737
4.27k
}
738
739
void ScopBuilder::addArrayAccess(
740
    MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
741
    Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
742
3.15k
    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
743
3.15k
  ArrayBasePointers.insert(BaseAddress);
744
3.15k
  auto *MemAccess = addMemoryAccess(
745
3.15k
      MemAccInst->getParent(), MemAccInst, AccType, BaseAddress, ElementType,
746
3.15k
      IsAffine, AccessValue, Subscripts, Sizes, MemoryKind::Array);
747
3.15k
748
3.15k
  if (!DetectFortranArrays)
749
3.14k
    return;
750
3.15k
751
13
  
if (Value *13
FAD13
= findFADAllocationInvisible(MemAccInst))
752
8
    MemAccess->setFortranArrayDescriptor(FAD);
753
5
  else 
if (Value *5
FAD5
= findFADAllocationVisible(MemAccInst))
754
2
    MemAccess->setFortranArrayDescriptor(FAD);
755
13
}
756
757
345
void ScopBuilder::ensureValueWrite(Instruction *Inst) {
758
345
  ScopStmt *Stmt = scop->getStmtFor(Inst);
759
345
760
345
  // Inst not defined within this SCoP.
761
345
  if (!Stmt)
762
0
    return;
763
345
764
345
  // Do not process further if the instruction is already written.
765
345
  
if (345
Stmt->lookupValueWriteOf(Inst)345
)
766
58
    return;
767
345
768
287
  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
769
287
                  Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
770
287
                  ArrayRef<const SCEV *>(), MemoryKind::Value);
771
287
}
772
773
23.6k
void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
774
23.6k
  ScopStmt *UserStmt = scop->getStmtFor(UserBB);
775
23.6k
  auto *Scope = LI.getLoopFor(UserBB);
776
23.6k
  auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
777
23.6k
  switch (VUse.getKind()) {
778
23.2k
  case VirtualUse::Constant:
779
23.2k
  case VirtualUse::Block:
780
23.2k
  case VirtualUse::Synthesizable:
781
23.2k
  case VirtualUse::Hoisted:
782
23.2k
  case VirtualUse::Intra:
783
23.2k
    // Uses of these kinds do not need a MemoryAccess.
784
23.2k
    break;
785
23.2k
786
49
  case VirtualUse::ReadOnly:
787
49
    // Add MemoryAccess for invariant values only if requested.
788
49
    if (!ModelReadOnlyScalars)
789
3
      break;
790
49
791
46
    
LLVM_FALLTHROUGH46
;46
792
326
  case VirtualUse::Inter:
793
326
794
326
    // Do not create another MemoryAccess for reloading the value if one already
795
326
    // exists.
796
326
    if (UserStmt->lookupValueReadOf(V))
797
28
      break;
798
326
799
298
    addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true,
800
298
                    V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
801
298
                    MemoryKind::Value);
802
298
803
298
    // Inter-statement uses need to write the value in their defining statement.
804
298
    if (VUse.isInter())
805
256
      ensureValueWrite(cast<Instruction>(V));
806
298
    break;
807
23.6k
  }
808
23.6k
}
809
810
void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
811
470
                                 Value *IncomingValue, bool IsExitBlock) {
812
470
  // As the incoming block might turn out to be an error statement ensure we
813
470
  // will create an exit PHI SAI object. It is needed during code generation
814
470
  // and would be created later anyway.
815
470
  if (IsExitBlock)
816
138
    scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
817
138
                                   MemoryKind::ExitPHI);
818
470
819
470
  ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
820
470
  if (!IncomingStmt)
821
55
    return;
822
470
823
470
  // Take care for the incoming value being available in the incoming block.
824
470
  // This must be done before the check for multiple PHI writes because multiple
825
470
  // exiting edges from subregion each can be the effective written value of the
826
470
  // subregion. As such, all of them must be made available in the subregion
827
470
  // statement.
828
415
  ensureValueRead(IncomingValue, IncomingBlock);
829
415
830
415
  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
831
415
  if (MemoryAccess *
Acc415
= IncomingStmt->lookupPHIWriteOf(PHI))
{52
832
52
    assert(Acc->getAccessInstruction() == PHI);
833
52
    Acc->addIncoming(IncomingBlock, IncomingValue);
834
52
    return;
835
52
  }
836
415
837
363
  MemoryAccess *Acc =
838
363
      addMemoryAccess(IncomingStmt->getEntryBlock(), PHI,
839
363
                      MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
840
363
                      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
841
259
                      IsExitBlock ? 
MemoryKind::ExitPHI104
:
MemoryKind::PHI259
);
842
363
  assert(Acc);
843
363
  Acc->addIncoming(IncomingBlock, IncomingValue);
844
363
}
845
846
171
void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
847
171
  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
848
171
                  PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
849
171
                  ArrayRef<const SCEV *>(), MemoryKind::PHI);
850
171
}
851
852
#ifndef NDEBUG
853
static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
854
  auto PhysUse = VirtualUse::create(S, Op, &LI, false);
855
  auto VirtUse = VirtualUse::create(S, Op, &LI, true);
856
  assert(PhysUse.getKind() == VirtUse.getKind());
857
}
858
859
/// Check the consistency of every statement's MemoryAccesses.
860
///
861
/// The check is carried out by expecting the "physical" kind of use (derived
862
/// from the BasicBlocks instructions resides in) to be same as the "virtual"
863
/// kind of use (derived from a statement's MemoryAccess).
864
///
865
/// The "physical" uses are taken by ensureValueRead to determine whether to
866
/// create MemoryAccesses. When done, the kind of scalar access should be the
867
/// same no matter which way it was derived.
868
///
869
/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
870
/// can intentionally influence on the kind of uses (not corresponding to the
871
/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
872
/// to pick up the virtual uses. But here in the code generator, this has not
873
/// happened yet, such that virtual and physical uses are equivalent.
874
static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
875
  for (auto *BB : S->getRegion().blocks()) {
876
    auto *Stmt = S->getStmtFor(BB);
877
    if (!Stmt)
878
      continue;
879
880
    for (auto &Inst : *BB) {
881
      if (isIgnoredIntrinsic(&Inst))
882
        continue;
883
884
      // Branch conditions are encoded in the statement domains.
885
      if (isa<TerminatorInst>(&Inst) && Stmt->isBlockStmt())
886
        continue;
887
888
      // Verify all uses.
889
      for (auto &Op : Inst.operands())
890
        verifyUse(S, Op, LI);
891
892
      // Stores do not produce values used by other statements.
893
      if (isa<StoreInst>(Inst))
894
        continue;
895
896
      // For every value defined in the block, also check that a use of that
897
      // value in the same statement would not be an inter-statement use. It can
898
      // still be synthesizable or load-hoisted, but these kind of instructions
899
      // are not directly copied in code-generation.
900
      auto VirtDef =
901
          VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);
902
      assert(VirtDef.getKind() == VirtualUse::Synthesizable ||
903
             VirtDef.getKind() == VirtualUse::Intra ||
904
             VirtDef.getKind() == VirtualUse::Hoisted);
905
    }
906
  }
907
908
  if (S->hasSingleExitEdge())
909
    return;
910
911
  // PHINodes in the SCoP region's exit block are also uses to be checked.
912
  if (!S->getRegion().isTopLevelRegion()) {
913
    for (auto &Inst : *S->getRegion().getExit()) {
914
      if (!isa<PHINode>(Inst))
915
        break;
916
917
      for (auto &Op : Inst.operands())
918
        verifyUse(S, Op, LI);
919
    }
920
  }
921
}
922
#endif
923
924
1.02k
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
925
1.02k
  scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
926
1.02k
927
1.02k
  buildStmts(R);
928
1.02k
  buildAccessFunctions(R);
929
1.02k
930
1.02k
  // In case the region does not have an exiting block we will later (during
931
1.02k
  // code generation) split the exit block. This will move potential PHI nodes
932
1.02k
  // from the current exit block into the new region exiting block. Hence, PHI
933
1.02k
  // nodes that are at this point not part of the region will be.
934
1.02k
  // To handle these PHI nodes later we will now model their operands as scalar
935
1.02k
  // accesses. Note that we do not model anything in the exit block if we have
936
1.02k
  // an exiting block in the region, as there will not be any splitting later.
937
1.02k
  if (
!R.isTopLevelRegion() && 1.02k
!scop->hasSingleExitEdge()1.02k
)
938
151
    buildAccessFunctions(*R.getExit(), nullptr,
939
151
                         /* IsExitBlock */ true);
940
1.02k
941
1.02k
  // Create memory accesses for global reads since all arrays are now known.
942
1.02k
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
943
1.02k
  for (auto *GlobalRead : GlobalReads)
944
8
    for (auto *BP : ArrayBasePointers)
945
16
      addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
946
16
                     BP->getType(), false, {AF}, {nullptr}, GlobalRead);
947
1.02k
948
1.02k
  scop->buildInvariantEquivalenceClasses();
949
1.02k
950
1.02k
  if (!scop->buildDomains(&R, DT, LI))
951
7
    return;
952
1.02k
953
1.01k
  scop->addUserAssumptions(AC, DT, LI);
954
1.01k
955
1.01k
  // Remove empty statements.
956
1.01k
  // Exit early in case there are no executable statements left in this scop.
957
1.01k
  scop->simplifySCoP(false);
958
1.01k
  if (scop->isEmpty())
959
28
    return;
960
1.01k
961
1.01k
  // The ScopStmts now have enough information to initialize themselves.
962
991
  for (ScopStmt &Stmt : *scop)
963
1.78k
    Stmt.init(LI);
964
991
965
991
  // Check early for a feasible runtime context.
966
991
  if (!scop->hasFeasibleRuntimeContext())
967
3
    return;
968
991
969
991
  // Check early for profitability. Afterwards it cannot change anymore,
970
991
  // only the runtime context could become infeasible.
971
988
  
if (988
!scop->isProfitable(UnprofitableScalarAccs)988
)
{2
972
2
    scop->invalidate(PROFITABLE, DebugLoc());
973
2
    return;
974
2
  }
975
988
976
986
  scop->buildSchedule(LI);
977
986
978
986
  scop->finalizeAccesses();
979
986
980
986
  scop->realignParams();
981
986
  scop->addUserContext();
982
986
983
986
  // After the context was fully constructed, thus all our knowledge about
984
986
  // the parameters is in there, we add all recorded assumptions to the
985
986
  // assumed/invalid context.
986
986
  scop->addRecordedAssumptions();
987
986
988
986
  scop->simplifyContexts();
989
986
  if (!scop->buildAliasChecks(AA))
990
5
    return;
991
986
992
981
  scop->hoistInvariantLoads();
993
981
  scop->canonicalizeDynamicBasePtrs();
994
981
  scop->verifyInvariantLoads();
995
981
  scop->simplifySCoP(true);
996
981
997
981
  // Check late for a feasible runtime context because profitability did not
998
981
  // change.
999
981
  if (!scop->hasFeasibleRuntimeContext())
1000
14
    return;
1001
981
1002
981
#ifndef NDEBUG
1003
  verifyUses(scop.get(), LI, DT);
1004
#endif
1005
981
}
1006
1007
ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
1008
                         const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
1009
                         ScopDetection &SD, ScalarEvolution &SE)
1010
1.02k
    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
1011
1.02k
1012
1.02k
  Function *F = R->getEntry()->getParent();
1013
1.02k
1014
1.02k
  DebugLoc Beg, End;
1015
1.02k
  getDebugLocations(getBBPairForRegion(R), Beg, End);
1016
1.02k
  std::string Msg = "SCoP begins here.";
1017
1.02k
  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
1018
1.02k
1019
1.02k
  buildScop(*R, AC);
1020
1.02k
1021
1.02k
  DEBUG(scop->print(dbgs()));
1022
1.02k
1023
1.02k
  if (
!scop->hasFeasibleRuntimeContext()1.02k
)
{59
1024
59
    InfeasibleScops++;
1025
59
    Msg = "SCoP ends here but was dismissed.";
1026
59
    scop.reset();
1027
967
  } else {
1028
967
    Msg = "SCoP ends here.";
1029
967
    ++ScopFound;
1030
967
    if (scop->getMaxLoopDepth() > 0)
1031
903
      ++RichScopFound;
1032
967
  }
1033
1.02k
1034
1.02k
  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
1035
1.02k
}