Coverage Report

Created: 2017-08-21 19:50

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