Coverage Report

Created: 2017-11-21 16:49

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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/ScopDetection.h"
20
#include "polly/ScopDetectionDiagnostic.h"
21
#include "polly/ScopInfo.h"
22
#include "polly/Support/SCEVValidator.h"
23
#include "polly/Support/ScopHelper.h"
24
#include "polly/Support/VirtualInstruction.h"
25
#include "llvm/ADT/APInt.h"
26
#include "llvm/ADT/ArrayRef.h"
27
#include "llvm/ADT/DenseMap.h"
28
#include "llvm/ADT/EquivalenceClasses.h"
29
#include "llvm/ADT/SetVector.h"
30
#include "llvm/ADT/Statistic.h"
31
#include "llvm/Analysis/AliasAnalysis.h"
32
#include "llvm/Analysis/LoopInfo.h"
33
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
34
#include "llvm/Analysis/RegionInfo.h"
35
#include "llvm/Analysis/RegionIterator.h"
36
#include "llvm/Analysis/ScalarEvolution.h"
37
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
38
#include "llvm/IR/BasicBlock.h"
39
#include "llvm/IR/Constants.h"
40
#include "llvm/IR/DataLayout.h"
41
#include "llvm/IR/DebugLoc.h"
42
#include "llvm/IR/DerivedTypes.h"
43
#include "llvm/IR/DiagnosticInfo.h"
44
#include "llvm/IR/Dominators.h"
45
#include "llvm/IR/Function.h"
46
#include "llvm/IR/InstrTypes.h"
47
#include "llvm/IR/Instruction.h"
48
#include "llvm/IR/Instructions.h"
49
#include "llvm/IR/IntrinsicInst.h"
50
#include "llvm/IR/Operator.h"
51
#include "llvm/IR/Type.h"
52
#include "llvm/IR/Use.h"
53
#include "llvm/IR/Value.h"
54
#include "llvm/Support/Casting.h"
55
#include "llvm/Support/CommandLine.h"
56
#include "llvm/Support/Compiler.h"
57
#include "llvm/Support/Debug.h"
58
#include "llvm/Support/ErrorHandling.h"
59
#include "llvm/Support/raw_ostream.h"
60
#include <cassert>
61
#include <string>
62
#include <tuple>
63
#include <vector>
64
65
using namespace llvm;
66
using namespace polly;
67
68
746
#define DEBUG_TYPE "polly-scops"
69
70
STATISTIC(ScopFound, "Number of valid Scops");
71
STATISTIC(RichScopFound, "Number of Scops containing a loop");
72
STATISTIC(InfeasibleScops,
73
          "Number of SCoPs with statically infeasible context.");
74
75
bool polly::ModelReadOnlyScalars;
76
77
static cl::opt<bool, true> XModelReadOnlyScalars(
78
    "polly-analyze-read-only-scalars",
79
    cl::desc("Model read-only scalar values in the scop description"),
80
    cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
81
    cl::init(true), cl::cat(PollyCategory));
82
83
static cl::opt<bool> UnprofitableScalarAccs(
84
    "polly-unprofitable-scalar-accs",
85
    cl::desc("Count statements with scalar accesses as not optimizable"),
86
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
87
88
static cl::opt<bool> DetectFortranArrays(
89
    "polly-detect-fortran-arrays",
90
    cl::desc("Detect Fortran arrays and use this for code generation"),
91
    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
92
93
static cl::opt<bool> DetectReductions("polly-detect-reductions",
94
                                      cl::desc("Detect and exploit reductions"),
95
                                      cl::Hidden, cl::ZeroOrMore,
96
                                      cl::init(true), cl::cat(PollyCategory));
97
98
// Multiplicative reductions can be disabled separately as these kind of
99
// operations can overflow easily. Additive reductions and bit operations
100
// are in contrast pretty stable.
101
static cl::opt<bool> DisableMultiplicativeReductions(
102
    "polly-disable-multiplicative-reductions",
103
    cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
104
    cl::init(false), cl::cat(PollyCategory));
105
106
enum class GranularityChoice { BasicBlocks, ScalarIndepependence };
107
108
static cl::opt<GranularityChoice> StmtGranularity(
109
    "polly-stmt-granularity",
110
    cl::desc(
111
        "Algorithm to use for splitting basic blocks into multiple statements"),
112
    cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
113
                          "One statement per basic block"),
114
               clEnumValN(GranularityChoice::ScalarIndepependence,
115
                          "scalar-indep", "Scalar independence heuristic")),
116
    cl::init(GranularityChoice::BasicBlocks), cl::cat(PollyCategory));
117
118
void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
119
                                   Region *NonAffineSubRegion,
120
90
                                   bool IsExitBlock) {
121
90
  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
122
90
  // true, are not modeled as ordinary PHI nodes as they are not part of the
123
90
  // region. However, we model the operands in the predecessor blocks that are
124
90
  // part of the region as regular scalar accesses.
125
90
126
90
  // If we can synthesize a PHI we can skip it, however only if it is in
127
90
  // the region. If it is not it can only be in the exit block of the region.
128
90
  // In this case we model the operands but not the PHI itself.
129
90
  auto *Scope = LI.getLoopFor(PHI->getParent());
130
90
  if (!IsExitBlock && 
canSynthesize(PHI, *scop, &SE, Scope)74
)
131
2
    return;
132
88
133
88
  // PHI nodes are modeled as if they had been demoted prior to the SCoP
134
88
  // detection. Hence, the PHI is a load of a new memory location in which the
135
88
  // incoming value was written at the end of the incoming basic block.
136
88
  bool OnlyNonAffineSubRegionOperands = true;
137
262
  for (unsigned u = 0; u < PHI->getNumIncomingValues(); 
u++174
) {
138
174
    Value *Op = PHI->getIncomingValue(u);
139
174
    BasicBlock *OpBB = PHI->getIncomingBlock(u);
140
174
    ScopStmt *OpStmt = scop->getLastStmtFor(OpBB);
141
174
142
174
    // Do not build PHI dependences inside a non-affine subregion, but make
143
174
    // sure that the necessary scalar values are still made available.
144
174
    if (NonAffineSubRegion && 
NonAffineSubRegion->contains(OpBB)3
) {
145
2
      auto *OpInst = dyn_cast<Instruction>(Op);
146
2
      if (!OpInst || 
!NonAffineSubRegion->contains(OpInst)1
)
147
1
        ensureValueRead(Op, OpStmt);
148
2
      continue;
149
2
    }
150
172
151
172
    OnlyNonAffineSubRegionOperands = false;
152
172
    ensurePHIWrite(PHI, OpStmt, OpBB, Op, IsExitBlock);
153
172
  }
154
88
155
88
  if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
156
72
    addPHIReadAccess(PHIStmt, PHI);
157
72
  }
158
90
}
159
160
void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
161
2.14k
                                         Instruction *Inst) {
162
2.14k
  assert(!isa<PHINode>(Inst));
163
2.14k
164
2.14k
  // Pull-in required operands.
165
2.14k
  for (Use &Op : Inst->operands())
166
3.82k
    ensureValueRead(Op.get(), UserStmt);
167
2.14k
}
168
169
6.36k
void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
170
6.36k
  // Check for uses of this instruction outside the scop. Because we do not
171
6.36k
  // iterate over such instructions and therefore did not "ensure" the existence
172
6.36k
  // of a write, we must determine such use here.
173
6.36k
  if (scop->isEscaping(Inst))
174
29
    ensureValueWrite(Inst);
175
6.36k
}
176
177
/// Check that a value is a Fortran Array descriptor.
178
///
179
/// We check if V has the following structure:
180
/// %"struct.array1_real(kind=8)" = type { i8*, i<zz>, i<zz>,
181
///                                   [<num> x %struct.descriptor_dimension] }
182
///
183
///
184
/// %struct.descriptor_dimension = type { i<zz>, i<zz>, i<zz> }
185
///
186
/// 1. V's type name starts with "struct.array"
187
/// 2. V's type has layout as shown.
188
/// 3. Final member of V's type has name "struct.descriptor_dimension",
189
/// 4. "struct.descriptor_dimension" has layout as shown.
190
/// 5. Consistent use of i<zz> where <zz> is some fixed integer number.
191
///
192
/// We are interested in such types since this is the code that dragonegg
193
/// generates for Fortran array descriptors.
194
///
195
/// @param V the Value to be checked.
196
///
197
/// @returns True if V is a Fortran array descriptor, False otherwise.
198
3
bool isFortranArrayDescriptor(Value *V) {
199
3
  PointerType *PTy = dyn_cast<PointerType>(V->getType());
200
3
201
3
  if (!PTy)
202
0
    return false;
203
3
204
3
  Type *Ty = PTy->getElementType();
205
3
  assert(Ty && "Ty expected to be initialized");
206
3
  auto *StructArrTy = dyn_cast<StructType>(Ty);
207
3
208
3
  if (!(StructArrTy && StructArrTy->hasName()))
209
0
    return false;
210
3
211
3
  if (!StructArrTy->getName().startswith("struct.array"))
212
0
    return false;
213
3
214
3
  if (StructArrTy->getNumElements() != 4)
215
0
    return false;
216
3
217
3
  const ArrayRef<Type *> ArrMemberTys = StructArrTy->elements();
218
3
219
3
  // i8* match
220
3
  if (ArrMemberTys[0] != Type::getInt8PtrTy(V->getContext()))
221
0
    return false;
222
3
223
3
  // Get a reference to the int type and check that all the members
224
3
  // share the same int type
225
3
  Type *IntTy = ArrMemberTys[1];
226
3
  if (ArrMemberTys[2] != IntTy)
227
0
    return false;
228
3
229
3
  // type: [<num> x %struct.descriptor_dimension]
230
3
  ArrayType *DescriptorDimArrayTy = dyn_cast<ArrayType>(ArrMemberTys[3]);
231
3
  if (!DescriptorDimArrayTy)
232
0
    return false;
233
3
234
3
  // type: %struct.descriptor_dimension := type { ixx, ixx, ixx }
235
3
  StructType *DescriptorDimTy =
236
3
      dyn_cast<StructType>(DescriptorDimArrayTy->getElementType());
237
3
238
3
  if (!(DescriptorDimTy && DescriptorDimTy->hasName()))
239
0
    return false;
240
3
241
3
  if (DescriptorDimTy->getName() != "struct.descriptor_dimension")
242
0
    return false;
243
3
244
3
  if (DescriptorDimTy->getNumElements() != 3)
245
0
    return false;
246
3
247
9
  
for (auto MemberTy : DescriptorDimTy->elements()) 3
{
248
9
    if (MemberTy != IntTy)
249
0
      return false;
250
3
  }
251
3
252
3
  return true;
253
3
}
254
255
5
Value *ScopBuilder::findFADAllocationVisible(MemAccInst Inst) {
256
5
  // match: 4.1 & 4.2 store/load
257
5
  if (!isa<LoadInst>(Inst) && 
!isa<StoreInst>(Inst)1
)
258
0
    return nullptr;
259
5
260
5
  // match: 4
261
5
  if (Inst.getAlignment() != 8)
262
1
    return nullptr;
263
4
264
4
  Value *Address = Inst.getPointerOperand();
265
4
266
4
  const BitCastInst *Bitcast = nullptr;
267
4
  // [match: 3]
268
4
  if (auto *Slot = dyn_cast<GetElementPtrInst>(Address)) {
269
3
    Value *TypedMem = Slot->getPointerOperand();
270
3
    // match: 2
271
3
    Bitcast = dyn_cast<BitCastInst>(TypedMem);
272
3
  } else {
273
1
    // match: 2
274
1
    Bitcast = dyn_cast<BitCastInst>(Address);
275
1
  }
276
4
277
4
  if (!Bitcast)
278
1
    return nullptr;
279
3
280
3
  auto *MallocMem = Bitcast->getOperand(0);
281
3
282
3
  // match: 1
283
3
  auto *MallocCall = dyn_cast<CallInst>(MallocMem);
284
3
  if (!MallocCall)
285
1
    return nullptr;
286
2
287
2
  Function *MallocFn = MallocCall->getCalledFunction();
288
2
  if (!(MallocFn && MallocFn->hasName() && MallocFn->getName() == "malloc"))
289
0
    return nullptr;
290
2
291
2
  // Find all uses the malloc'd memory.
292
2
  // We are looking for a "store" into a struct with the type being the Fortran
293
2
  // descriptor type
294
4
  
for (auto user : MallocMem->users()) 2
{
295
4
    /// match: 5
296
4
    auto *MallocStore = dyn_cast<StoreInst>(user);
297
4
    if (!MallocStore)
298
2
      continue;
299
2
300
2
    auto *DescriptorGEP =
301
2
        dyn_cast<GEPOperator>(MallocStore->getPointerOperand());
302
2
    if (!DescriptorGEP)
303
0
      continue;
304
2
305
2
    // match: 5
306
2
    auto DescriptorType =
307
2
        dyn_cast<StructType>(DescriptorGEP->getSourceElementType());
308
2
    if (!(DescriptorType && DescriptorType->hasName()))
309
0
      continue;
310
2
311
2
    Value *Descriptor = dyn_cast<Value>(DescriptorGEP->getPointerOperand());
312
2
313
2
    if (!Descriptor)
314
0
      continue;
315
2
316
2
    if (!isFortranArrayDescriptor(Descriptor))
317
0
      continue;
318
2
319
2
    return Descriptor;
320
2
  }
321
0
322
0
  return nullptr;
323
0
}
324
325
6
Value *ScopBuilder::findFADAllocationInvisible(MemAccInst Inst) {
326
6
  // match: 3
327
6
  if (!isa<LoadInst>(Inst) && 
!isa<StoreInst>(Inst)2
)
328
0
    return nullptr;
329
6
330
6
  Value *Slot = Inst.getPointerOperand();
331
6
332
6
  LoadInst *MemLoad = nullptr;
333
6
  // [match: 2]
334
6
  if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
335
4
    // match: 1
336
4
    MemLoad = dyn_cast<LoadInst>(SlotGEP->getPointerOperand());
337
4
  } else {
338
2
    // match: 1
339
2
    MemLoad = dyn_cast<LoadInst>(Slot);
340
2
  }
341
6
342
6
  if (!MemLoad)
343
5
    return nullptr;
344
1
345
1
  auto *BitcastOperator =
346
1
      dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
347
1
  if (!BitcastOperator)
348
0
    return nullptr;
349
1
350
1
  Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
351
1
  if (!Descriptor)
352
0
    return nullptr;
353
1
354
1
  if (!isFortranArrayDescriptor(Descriptor))
355
0
    return nullptr;
356
1
357
1
  return Descriptor;
358
1
}
359
360
999
bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
361
999
  Value *Val = Inst.getValueOperand();
362
999
  Type *ElementType = Val->getType();
363
999
  Value *Address = Inst.getPointerOperand();
364
999
  const SCEV *AccessFunction =
365
999
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
366
999
  const SCEVUnknown *BasePointer =
367
999
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
368
999
  enum MemoryAccess::AccessType AccType =
369
999
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ475
:
MemoryAccess::MUST_WRITE524
;
370
999
371
999
  if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
372
25
    auto *Src = BitCast->getOperand(0);
373
25
    auto *SrcTy = Src->getType();
374
25
    auto *DstTy = BitCast->getType();
375
25
    // Do not try to delinearize non-sized (opaque) pointers.
376
25
    if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
377
25
        
(24
DstTy->isPointerTy()24
&&
!DstTy->getPointerElementType()->isSized()24
)) {
378
1
      return false;
379
1
    }
380
24
    if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
381
24
        DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
382
24
            DL.getTypeAllocSize(DstTy->getPointerElementType()))
383
13
      Address = Src;
384
25
  }
385
999
386
999
  auto *GEP = dyn_cast<GetElementPtrInst>(Address);
387
998
  if (!GEP)
388
223
    return false;
389
775
390
775
  std::vector<const SCEV *> Subscripts;
391
775
  std::vector<int> Sizes;
392
775
  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
393
775
  auto *BasePtr = GEP->getOperand(0);
394
775
395
775
  if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
396
5
    BasePtr = BasePtrCast->getOperand(0);
397
775
398
775
  // Check for identical base pointers to ensure that we do not miss index
399
775
  // offsets that have been added before this GEP is applied.
400
775
  if (BasePtr != BasePointer->getValue())
401
37
    return false;
402
738
403
738
  std::vector<const SCEV *> SizesSCEV;
404
738
405
738
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
406
738
407
738
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
408
789
  for (auto *Subscript : Subscripts) {
409
789
    InvariantLoadsSetTy AccessILS;
410
789
    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
411
789
                      &AccessILS))
412
28
      return false;
413
761
414
761
    for (LoadInst *LInst : AccessILS)
415
761
      
if (5
!ScopRIL.count(LInst)5
)
416
2
        return false;
417
708
  }
418
708
419
708
  if (Sizes.empty())
420
615
    return false;
421
93
422
93
  SizesSCEV.push_back(nullptr);
423
93
424
93
  for (auto V : Sizes)
425
98
    SizesSCEV.push_back(SE.getSCEV(
426
98
        ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
427
999
428
999
  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
429
999
                 true, Subscripts, SizesSCEV, Val);
430
999
  return true;
431
999
}
432
433
906
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
434
906
  if (!PollyDelinearize)
435
2
    return false;
436
904
437
904
  Value *Address = Inst.getPointerOperand();
438
904
  Value *Val = Inst.getValueOperand();
439
904
  Type *ElementType = Val->getType();
440
904
  unsigned ElementSize = DL.getTypeAllocSize(ElementType);
441
904
  enum MemoryAccess::AccessType AccType =
442
904
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ421
:
MemoryAccess::MUST_WRITE483
;
443
904
444
904
  const SCEV *AccessFunction =
445
904
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
446
904
  const SCEVUnknown *BasePointer =
447
904
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
448
904
449
904
  assert(BasePointer && "Could not find base pointer");
450
904
451
904
  auto &InsnToMemAcc = scop->getInsnToMemAccMap();
452
904
  auto AccItr = InsnToMemAcc.find(Inst);
453
904
  if (AccItr == InsnToMemAcc.end())
454
853
    return false;
455
51
456
51
  std::vector<const SCEV *> Sizes = {nullptr};
457
51
458
51
  Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
459
51
               AccItr->second.Shape->DelinearizedSizes.end());
460
51
461
51
  // In case only the element size is contained in the 'Sizes' array, the
462
51
  // access does not access a real multi-dimensional array. Hence, we allow
463
51
  // the normal single-dimensional access construction to handle this.
464
51
  if (Sizes.size() == 1)
465
0
    return false;
466
51
467
51
  // Remove the element size. This information is already provided by the
468
51
  // ElementSize parameter. In case the element size of this access and the
469
51
  // element size used for delinearization differs the delinearization is
470
51
  // incorrect. Hence, we invalidate the scop.
471
51
  //
472
51
  // TODO: Handle delinearization with differing element sizes.
473
51
  auto DelinearizedSize =
474
51
      cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
475
51
  Sizes.pop_back();
476
51
  if (ElementSize != DelinearizedSize)
477
1
    scop->invalidate(DELINEARIZATION, Inst->getDebugLoc(), Inst->getParent());
478
906
479
906
  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
480
906
                 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);
481
906
  return true;
482
906
}
483
484
1.01k
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
485
1.01k
  auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
486
1.01k
487
1.01k
  if (MemIntr == nullptr)
488
1.00k
    return false;
489
6
490
6
  auto *L = LI.getLoopFor(Inst->getParent());
491
6
  auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
492
6
  assert(LengthVal);
493
6
494
6
  // Check if the length val is actually affine or if we overapproximate it
495
6
  InvariantLoadsSetTy AccessILS;
496
6
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
497
6
498
6
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
499
6
  bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
500
6
                                     LengthVal, SE, &AccessILS);
501
6
  for (LoadInst *LInst : AccessILS)
502
6
    
if (0
!ScopRIL.count(LInst)0
)
503
0
      LengthIsAffine = false;
504
6
  if (!LengthIsAffine)
505
1
    LengthVal = nullptr;
506
6
507
6
  auto *DestPtrVal = MemIntr->getDest();
508
6
  assert(DestPtrVal);
509
6
510
6
  auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
511
6
  assert(DestAccFunc);
512
6
  // Ignore accesses to "NULL".
513
6
  // TODO: We could use this to optimize the region further, e.g., intersect
514
6
  //       the context with
515
6
  //          isl_set_complement(isl_set_params(getDomain()))
516
6
  //       as we know it would be undefined to execute this instruction anyway.
517
6
  if (DestAccFunc->isZero())
518
1
    return true;
519
5
520
5
  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
521
5
  assert(DestPtrSCEV);
522
5
  DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
523
5
  addArrayAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
524
5
                 IntegerType::getInt8Ty(DestPtrVal->getContext()),
525
5
                 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
526
5
                 Inst.getValueOperand());
527
5
528
5
  auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
529
5
  if (!MemTrans)
530
1
    return true;
531
4
532
4
  auto *SrcPtrVal = MemTrans->getSource();
533
4
  assert(SrcPtrVal);
534
4
535
4
  auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
536
4
  assert(SrcAccFunc);
537
4
  // Ignore accesses to "NULL".
538
4
  // TODO: See above TODO
539
4
  if (SrcAccFunc->isZero())
540
0
    return true;
541
4
542
4
  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
543
4
  assert(SrcPtrSCEV);
544
4
  SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
545
4
  addArrayAccess(Stmt, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
546
4
                 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
547
4
                 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
548
4
                 Inst.getValueOperand());
549
4
550
4
  return true;
551
4
}
552
553
1.00k
bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
554
1.00k
  auto *CI = dyn_cast_or_null<CallInst>(Inst);
555
1.00k
556
1.00k
  if (CI == nullptr)
557
999
    return false;
558
8
559
8
  if (CI->doesNotAccessMemory() || 
isIgnoredIntrinsic(CI)4
)
560
4
    return true;
561
4
562
4
  bool ReadOnly = false;
563
4
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
564
4
  auto *CalledFunction = CI->getCalledFunction();
565
4
  switch (AA.getModRefBehavior(CalledFunction)) {
566
4
  case FMRB_UnknownModRefBehavior:
567
0
    llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
568
4
  case FMRB_DoesNotAccessMemory:
569
0
    return true;
570
4
  case FMRB_DoesNotReadMemory:
571
0
  case FMRB_OnlyAccessesInaccessibleMem:
572
0
  case FMRB_OnlyAccessesInaccessibleOrArgMem:
573
0
    return false;
574
2
  case FMRB_OnlyReadsMemory:
575
2
    GlobalReads.emplace_back(Stmt, CI);
576
2
    return true;
577
1
  case FMRB_OnlyReadsArgumentPointees:
578
1
    ReadOnly = true;
579
1
  // Fall through
580
2
  case FMRB_OnlyAccessesArgumentPointees: {
581
2
    auto AccType = ReadOnly ? 
MemoryAccess::READ1
:
MemoryAccess::MAY_WRITE1
;
582
2
    Loop *L = LI.getLoopFor(Inst->getParent());
583
6
    for (const auto &Arg : CI->arg_operands()) {
584
6
      if (!Arg->getType()->isPointerTy())
585
3
        continue;
586
3
587
3
      auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
588
3
      if (ArgSCEV->isZero())
589
1
        continue;
590
2
591
2
      auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
592
2
      addArrayAccess(Stmt, Inst, AccType, ArgBasePtr->getValue(),
593
2
                     ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
594
2
    }
595
2
    return true;
596
0
  }
597
0
  }
598
0
599
0
  return true;
600
0
}
601
602
855
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
603
855
  Value *Address = Inst.getPointerOperand();
604
855
  Value *Val = Inst.getValueOperand();
605
855
  Type *ElementType = Val->getType();
606
855
  enum MemoryAccess::AccessType AccType =
607
855
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ399
:
MemoryAccess::MUST_WRITE456
;
608
855
609
855
  const SCEV *AccessFunction =
610
855
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
611
855
  const SCEVUnknown *BasePointer =
612
855
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
613
855
614
855
  assert(BasePointer && "Could not find base pointer");
615
855
  AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
616
855
617
855
  // Check if the access depends on a loop contained in a non-affine subregion.
618
855
  bool isVariantInNonAffineLoop = false;
619
855
  SetVector<const Loop *> Loops;
620
855
  findLoops(AccessFunction, Loops);
621
855
  for (const Loop *L : Loops)
622
855
    
if (496
Stmt->contains(L)496
) {
623
4
      isVariantInNonAffineLoop = true;
624
4
      break;
625
4
    }
626
855
627
855
  InvariantLoadsSetTy AccessILS;
628
855
629
855
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
630
855
  bool IsAffine = !isVariantInNonAffineLoop &&
631
855
                  isAffineExpr(&scop->getRegion(), SurroundingLoop,
632
851
                               AccessFunction, SE, &AccessILS);
633
855
634
855
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
635
855
  for (LoadInst *LInst : AccessILS)
636
855
    
if (7
!ScopRIL.count(LInst)7
)
637
4
      IsAffine = false;
638
855
639
855
  if (!IsAffine && 
AccType == MemoryAccess::MUST_WRITE11
)
640
8
    AccType = MemoryAccess::MAY_WRITE;
641
855
642
855
  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
643
855
                 IsAffine, {AccessFunction}, {nullptr}, Val);
644
855
}
645
646
1.01k
void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
647
1.01k
  if (buildAccessMemIntrinsic(Inst, Stmt))
648
6
    return;
649
1.00k
650
1.00k
  if (buildAccessCallInst(Inst, Stmt))
651
8
    return;
652
999
653
999
  if (buildAccessMultiDimFixed(Inst, Stmt))
654
93
    return;
655
906
656
906
  if (buildAccessMultiDimParam(Inst, Stmt))
657
51
    return;
658
855
659
855
  buildAccessSingleDim(Inst, Stmt);
660
855
}
661
662
373
void ScopBuilder::buildAccessFunctions() {
663
1.87k
  for (auto &Stmt : *scop) {
664
1.87k
    if (Stmt.isBlockStmt()) {
665
1.85k
      buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());
666
1.85k
      continue;
667
1.85k
    }
668
27
669
27
    Region *R = Stmt.getRegion();
670
27
    for (BasicBlock *BB : R->blocks())
671
77
      buildAccessFunctions(&Stmt, *BB, R);
672
1.87k
  }
673
373
674
373
  // Build write accesses for values that are used after the SCoP.
675
373
  // The instructions defining them might be synthesizable and therefore not
676
373
  // contained in any statement, hence we iterate over the original instructions
677
373
  // to identify all escaping values.
678
1.91k
  for (BasicBlock *BB : scop->getRegion().blocks()) {
679
1.91k
    for (Instruction &Inst : *BB)
680
6.36k
      buildEscapingDependences(&Inst);
681
1.91k
  }
682
373
}
683
684
6.24k
bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {
685
6.24k
  return !isa<TerminatorInst>(Inst) && 
!isIgnoredIntrinsic(Inst)4.37k
&&
686
6.24k
         
!canSynthesize(Inst, *scop, &SE, L)4.36k
;
687
6.24k
}
688
689
1.82k
void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB) {
690
1.82k
  Loop *SurroundingLoop = LI.getLoopFor(BB);
691
1.82k
692
1.82k
  int Count = 0;
693
1.82k
  std::vector<Instruction *> Instructions;
694
6.10k
  for (Instruction &Inst : *BB) {
695
6.10k
    if (shouldModelInst(&Inst, SurroundingLoop))
696
2.00k
      Instructions.push_back(&Inst);
697
6.10k
    if (Inst.getMetadata("polly_split_after")) {
698
3
      scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
699
3
      Count++;
700
3
      Instructions.clear();
701
3
    }
702
6.10k
  }
703
1.82k
704
1.82k
  scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
705
1.82k
}
706
707
/// Is @p Inst an ordered instruction?
708
///
709
/// An unordered instruction is an instruction, such that a sequence of
710
/// unordered instructions can be permuted without changing semantics. Any
711
/// instruction for which this is not always the case is ordered.
712
26
static bool isOrderedInstruction(Instruction *Inst) {
713
26
  return Inst->mayHaveSideEffects() || 
Inst->mayReadOrWriteMemory()18
;
714
26
}
715
716
/// Join instructions to the same statement if one uses the scalar result of the
717
/// other.
718
static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,
719
14
                            ArrayRef<Instruction *> ModeledInsts) {
720
14
  for (Instruction *Inst : ModeledInsts) {
721
13
    if (isa<PHINode>(Inst))
722
2
      continue;
723
11
724
19
    
for (Use &Op : Inst->operands()) 11
{
725
19
      Instruction *OpInst = dyn_cast<Instruction>(Op.get());
726
19
      if (!OpInst)
727
12
        continue;
728
7
729
7
      // Check if OpInst is in the BB and is a modeled instruction.
730
7
      auto OpVal = UnionFind.findValue(OpInst);
731
7
      if (OpVal == UnionFind.end())
732
3
        continue;
733
4
734
4
      UnionFind.unionSets(Inst, OpInst);
735
4
    }
736
13
  }
737
14
}
738
739
/// Join instructions that are used as incoming value in successor PHIs into the
740
/// epilogue.
741
static void
742
joinIncomingPHIValuesIntoEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
743
                                  ArrayRef<Instruction *> ModeledInsts,
744
14
                                  BasicBlock *BB) {
745
17
  for (BasicBlock *Succ : successors(BB)) {
746
22
    for (Instruction &SuccInst : *Succ) {
747
22
      PHINode *SuccPHI = dyn_cast<PHINode>(&SuccInst);
748
22
      if (!SuccPHI)
749
17
        break;
750
5
751
5
      Value *IncomingVal = SuccPHI->getIncomingValueForBlock(BB);
752
5
      Instruction *IncomingInst = dyn_cast<Instruction>(IncomingVal);
753
5
      if (!IncomingInst)
754
1
        continue;
755
4
      if (IncomingInst->getParent() != BB)
756
0
        continue;
757
4
      if (UnionFind.findValue(IncomingInst) == UnionFind.end())
758
3
        continue;
759
1
760
1
      UnionFind.unionSets(nullptr, IncomingInst);
761
1
    }
762
17
  }
763
14
}
764
765
/// Ensure that the order of ordered instructions does not change.
766
///
767
/// If we encounter an ordered instruction enclosed in instructions belonging to
768
/// a different statement (which might as well contain ordered instructions, but
769
/// this is not tested here), join them.
770
static void
771
joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
772
14
                        ArrayRef<Instruction *> ModeledInsts) {
773
14
  SetVector<Instruction *> SeenLeaders;
774
14
  for (Instruction *Inst : ModeledInsts) {
775
13
    if (!isOrderedInstruction(Inst))
776
6
      continue;
777
7
778
7
    Instruction *Leader = UnionFind.getLeaderValue(Inst);
779
7
    bool Inserted = SeenLeaders.insert(Leader);
780
7
    if (Inserted)
781
4
      continue;
782
3
783
3
    // Merge statements to close holes. Say, we have already seen statements A
784
3
    // and B, in this order. Then we see an instruction of A again and we would
785
3
    // see the pattern "A B A". This function joins all statements until the
786
3
    // only seen occurrence of A.
787
3
    for (Instruction *Prev : reverse(SeenLeaders)) {
788
3
      // Items added to 'SeenLeaders' are leaders, but may have lost their
789
3
      // leadership status when merged into another statement.
790
3
      Instruction *PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
791
3
      if (PrevLeader == Leader)
792
3
        break;
793
0
      UnionFind.unionSets(Prev, Leader);
794
0
    }
795
13
  }
796
14
}
797
798
/// Also ensure that the epilogue is the last statement relative to all ordered
799
/// instructions.
800
///
801
/// This is basically joinOrderedInstructions() but using the epilogue as
802
/// 'ordered instruction'.
803
static void joinAllAfterEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
804
14
                                 ArrayRef<Instruction *> ModeledInsts) {
805
14
  bool EpilogueSeen = false;
806
14
  for (Instruction *Inst : ModeledInsts) {
807
13
    auto PHIWritesLeader = UnionFind.findLeader(nullptr);
808
13
    auto InstLeader = UnionFind.findLeader(Inst);
809
13
810
13
    if (PHIWritesLeader == InstLeader)
811
2
      EpilogueSeen = true;
812
13
813
13
    if (!isOrderedInstruction(Inst))
814
6
      continue;
815
7
816
7
    if (EpilogueSeen)
817
2
      UnionFind.unionSets(PHIWritesLeader, InstLeader);
818
13
  }
819
14
}
820
821
14
void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
822
14
  Loop *L = LI.getLoopFor(BB);
823
14
824
14
  // Extracting out modeled instructions saves us from checking
825
14
  // shouldModelInst() repeatedly.
826
14
  SmallVector<Instruction *, 32> ModeledInsts;
827
14
  EquivalenceClasses<Instruction *> UnionFind;
828
33
  for (Instruction &Inst : *BB) {
829
33
    if (!shouldModelInst(&Inst, L))
830
20
      continue;
831
13
    ModeledInsts.push_back(&Inst);
832
13
    UnionFind.insert(&Inst);
833
13
  }
834
14
835
14
  // 'nullptr' represents the last statement for a basic block. It contains no
836
14
  // instructions, but holds the PHI write accesses for successor basic blocks.
837
14
  // If a PHI has an incoming value defined in this BB, it can also be merged
838
14
  // with other statements.
839
14
  // TODO: We wouldn't need this if we would add PHIWrites into the statement
840
14
  // that defines the incoming value (if in the BB) instead of always the last,
841
14
  // so we could unconditionally always add a last statement.
842
14
  UnionFind.insert(nullptr);
843
14
844
14
  joinOperandTree(UnionFind, ModeledInsts);
845
14
  joinIncomingPHIValuesIntoEpilogue(UnionFind, ModeledInsts, BB);
846
14
  joinOrderedInstructions(UnionFind, ModeledInsts);
847
14
  joinAllAfterEpilogue(UnionFind, ModeledInsts);
848
14
849
14
  // The list of instructions for statement (statement represented by the leader
850
14
  // instruction). The order of statements instructions is reversed such that
851
14
  // the epilogue is first. This makes it easier to ensure that the epilogue is
852
14
  // the last statement.
853
14
  MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
854
14
855
14
  // Ensure that the epilogue is last.
856
14
  LeaderToInstList[nullptr];
857
14
858
14
  // Collect the instructions of all leaders. UnionFind's member iterator
859
14
  // unfortunately are not in any specific order.
860
33
  for (Instruction &Inst : reverse(*BB)) {
861
33
    auto LeaderIt = UnionFind.findLeader(&Inst);
862
33
    if (LeaderIt == UnionFind.member_end())
863
20
      continue;
864
13
865
13
    std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
866
13
    InstList.push_back(&Inst);
867
13
  }
868
14
869
14
  // Finally build the statements.
870
14
  int Count = 0;
871
22
  for (auto &Instructions : reverse(LeaderToInstList)) {
872
22
    std::vector<Instruction *> &InstList = Instructions.second;
873
22
    std::reverse(InstList.begin(), InstList.end());
874
22
    scop->addScopStmt(BB, L, std::move(InstList), Count);
875
22
    Count += 1;
876
22
  }
877
14
}
878
879
819
void ScopBuilder::buildStmts(Region &SR) {
880
819
  if (scop->isNonAffineSubRegion(&SR)) {
881
27
    std::vector<Instruction *> Instructions;
882
27
    Loop *SurroundingLoop =
883
27
        getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
884
27
    for (Instruction &Inst : *SR.getEntry())
885
101
      if (shouldModelInst(&Inst, SurroundingLoop))
886
52
        Instructions.push_back(&Inst);
887
27
    scop->addScopStmt(&SR, SurroundingLoop, Instructions);
888
27
    return;
889
27
  }
890
792
891
3.07k
  
for (auto I = SR.element_begin(), E = SR.element_end(); 792
I != E;
++I2.28k
)
892
2.28k
    if (I->isSubRegion())
893
446
      buildStmts(*I->getNodeAs<Region>());
894
1.84k
    else {
895
1.84k
      BasicBlock *BB = I->getNodeAs<BasicBlock>();
896
1.84k
      switch (StmtGranularity) {
897
1.84k
      case GranularityChoice::BasicBlocks:
898
1.82k
        buildSequentialBlockStmts(BB);
899
1.82k
        break;
900
1.84k
      case GranularityChoice::ScalarIndepependence:
901
14
        buildEqivClassBlockStmts(BB);
902
14
        break;
903
2.28k
      }
904
2.28k
    }
905
819
}
906
907
void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
908
1.92k
                                       Region *NonAffineSubRegion) {
909
1.92k
  assert(
910
1.92k
      Stmt &&
911
1.92k
      "The exit BB is the only one that cannot be represented by a statement");
912
1.92k
  assert(Stmt->represents(&BB));
913
1.92k
914
1.92k
  // We do not build access functions for error blocks, as they may contain
915
1.92k
  // instructions we can not model.
916
1.92k
  if (isErrorBlock(BB, scop->getRegion(), LI, DT))
917
12
    return;
918
1.91k
919
1.91k
  auto BuildAccessesForInst = [this, Stmt,
920
2.21k
                               NonAffineSubRegion](Instruction *Inst) {
921
2.21k
    PHINode *PHI = dyn_cast<PHINode>(Inst);
922
2.21k
    if (PHI)
923
74
      buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, false);
924
2.21k
925
2.21k
    if (auto MemInst = MemAccInst::dyn_cast(*Inst)) {
926
955
      assert(Stmt && "Cannot build access function in non-existing statement");
927
955
      buildMemoryAccess(MemInst, Stmt);
928
955
    }
929
2.21k
930
2.21k
    // PHI nodes have already been modeled above and TerminatorInsts that are
931
2.21k
    // not part of a non-affine subregion are fully modeled and regenerated
932
2.21k
    // from the polyhedral domains. Hence, they do not need to be modeled as
933
2.21k
    // explicit data dependences.
934
2.21k
    if (!PHI)
935
2.14k
      buildScalarDependences(Stmt, Inst);
936
2.21k
  };
937
1.91k
938
1.91k
  const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
939
1.91k
  bool IsEntryBlock = (Stmt->getEntryBlock() == &BB);
940
1.91k
  if (IsEntryBlock) {
941
1.86k
    for (Instruction *Inst : Stmt->getInstructions())
942
2.06k
      BuildAccessesForInst(Inst);
943
1.86k
    if (Stmt->isRegionStmt())
944
27
      BuildAccessesForInst(BB.getTerminator());
945
1.86k
  } else {
946
125
    for (Instruction &Inst : BB) {
947
125
      if (isIgnoredIntrinsic(&Inst))
948
0
        continue;
949
125
950
125
      // Invariant loads already have been processed.
951
125
      if (isa<LoadInst>(Inst) && 
RIL.count(cast<LoadInst>(&Inst))13
)
952
0
        continue;
953
125
954
125
      BuildAccessesForInst(&Inst);
955
125
    }
956
49
  }
957
1.92k
}
958
959
MemoryAccess *ScopBuilder::addMemoryAccess(
960
    ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,
961
    Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
962
    ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
963
1.46k
    MemoryKind Kind) {
964
1.46k
  bool isKnownMustAccess = false;
965
1.46k
966
1.46k
  // Accesses in single-basic block statements are always executed.
967
1.46k
  if (Stmt->isBlockStmt())
968
1.39k
    isKnownMustAccess = true;
969
1.46k
970
1.46k
  if (Stmt->isRegionStmt()) {
971
72
    // Accesses that dominate the exit block of a non-affine region are always
972
72
    // executed. In non-affine regions there may exist MemoryKind::Values that
973
72
    // do not dominate the exit. MemoryKind::Values will always dominate the
974
72
    // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
975
72
    // non-affine region.
976
72
    if (Inst && 
DT.dominates(Inst->getParent(), Stmt->getRegion()->getExit())69
)
977
30
      isKnownMustAccess = true;
978
72
  }
979
1.46k
980
1.46k
  // Non-affine PHI writes do not "happen" at a particular instruction, but
981
1.46k
  // after exiting the statement. Therefore they are guaranteed to execute and
982
1.46k
  // overwrite the old value.
983
1.46k
  if (Kind == MemoryKind::PHI || 
Kind == MemoryKind::ExitPHI1.28k
)
984
212
    isKnownMustAccess = true;
985
1.46k
986
1.46k
  if (!isKnownMustAccess && 
AccType == MemoryAccess::MUST_WRITE41
)
987
22
    AccType = MemoryAccess::MAY_WRITE;
988
1.46k
989
1.46k
  auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
990
1.46k
                                  Affine, Subscripts, Sizes, AccessValue, Kind);
991
1.46k
992
1.46k
  scop->addAccessFunction(Access);
993
1.46k
  Stmt->addAccess(Access);
994
1.46k
  return Access;
995
1.46k
}
996
997
void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
998
                                 MemoryAccess::AccessType AccType,
999
                                 Value *BaseAddress, Type *ElementType,
1000
                                 bool IsAffine,
1001
                                 ArrayRef<const SCEV *> Subscripts,
1002
                                 ArrayRef<const SCEV *> Sizes,
1003
1.01k
                                 Value *AccessValue) {
1004
1.01k
  ArrayBasePointers.insert(BaseAddress);
1005
1.01k
  auto *MemAccess = addMemoryAccess(Stmt, MemAccInst, AccType, BaseAddress,
1006
1.01k
                                    ElementType, IsAffine, AccessValue,
1007
1.01k
                                    Subscripts, Sizes, MemoryKind::Array);
1008
1.01k
1009
1.01k
  if (!DetectFortranArrays)
1010
1.00k
    return;
1011
6
1012
6
  if (Value *FAD = findFADAllocationInvisible(MemAccInst))
1013
1
    MemAccess->setFortranArrayDescriptor(FAD);
1014
5
  else if (Value *FAD = findFADAllocationVisible(MemAccInst))
1015
2
    MemAccess->setFortranArrayDescriptor(FAD);
1016
1.01k
}
1017
1018
134
void ScopBuilder::ensureValueWrite(Instruction *Inst) {
1019
134
  // Find the statement that defines the value of Inst. That statement has to
1020
134
  // write the value to make it available to those statements that read it.
1021
134
  ScopStmt *Stmt = scop->getStmtFor(Inst);
1022
134
1023
134
  // It is possible that the value is synthesizable within a loop (such that it
1024
134
  // is not part of any statement), but not after the loop (where you need the
1025
134
  // number of loop round-trips to synthesize it). In LCSSA-form a PHI node will
1026
134
  // avoid this. In case the IR has no such PHI, use the last statement (where
1027
134
  // the value is synthesizable) to write the value.
1028
134
  if (!Stmt)
1029
16
    Stmt = scop->getLastStmtFor(Inst->getParent());
1030
134
1031
134
  // Inst not defined within this SCoP.
1032
134
  if (!Stmt)
1033
0
    return;
1034
134
1035
134
  // Do not process further if the instruction is already written.
1036
134
  if (Stmt->lookupValueWriteOf(Inst))
1037
17
    return;
1038
117
1039
117
  addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),
1040
117
                  true, Inst, ArrayRef<const SCEV *>(),
1041
117
                  ArrayRef<const SCEV *>(), MemoryKind::Value);
1042
117
}
1043
1044
3.97k
void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
1045
3.97k
  // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
1046
3.97k
  // to be able to replace this one. Currently, there is a split responsibility.
1047
3.97k
  // In a first step, the MemoryAccess is created, but without the
1048
3.97k
  // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
1049
3.97k
  // AccessRelation is created. At least for scalar accesses, there is no new
1050
3.97k
  // information available at ScopStmt::buildAccessRelations(), so we could
1051
3.97k
  // create the AccessRelation right away. This is what
1052
3.97k
  // ScopStmt::ensureValueRead(Value*) does.
1053
3.97k
1054
3.97k
  auto *Scope = UserStmt->getSurroundingLoop();
1055
3.97k
  auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
1056
3.97k
  switch (VUse.getKind()) {
1057
3.97k
  case VirtualUse::Constant:
1058
3.84k
  case VirtualUse::Block:
1059
3.84k
  case VirtualUse::Synthesizable:
1060
3.84k
  case VirtualUse::Hoisted:
1061
3.84k
  case VirtualUse::Intra:
1062
3.84k
    // Uses of these kinds do not need a MemoryAccess.
1063
3.84k
    break;
1064
3.84k
1065
3.84k
  case VirtualUse::ReadOnly:
1066
19
    // Add MemoryAccess for invariant values only if requested.
1067
19
    if (!ModelReadOnlyScalars)
1068
1
      break;
1069
18
1070
18
    LLVM_FALLTHROUGH;
1071
127
  case VirtualUse::Inter:
1072
127
1073
127
    // Do not create another MemoryAccess for reloading the value if one already
1074
127
    // exists.
1075
127
    if (UserStmt->lookupValueReadOf(V))
1076
5
      break;
1077
122
1078
122
    addMemoryAccess(UserStmt, nullptr, MemoryAccess::READ, V, V->getType(),
1079
122
                    true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
1080
122
                    MemoryKind::Value);
1081
122
1082
122
    // Inter-statement uses need to write the value in their defining statement.
1083
122
    if (VUse.isInter())
1084
105
      ensureValueWrite(cast<Instruction>(V));
1085
3.84k
    break;
1086
3.97k
  }
1087
3.97k
}
1088
1089
void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,
1090
                                 BasicBlock *IncomingBlock,
1091
172
                                 Value *IncomingValue, bool IsExitBlock) {
1092
172
  // As the incoming block might turn out to be an error statement ensure we
1093
172
  // will create an exit PHI SAI object. It is needed during code generation
1094
172
  // and would be created later anyway.
1095
172
  if (IsExitBlock)
1096
44
    scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
1097
44
                                   MemoryKind::ExitPHI);
1098
172
1099
172
  // This is possible if PHI is in the SCoP's entry block. The incoming blocks
1100
172
  // from outside the SCoP's region have no statement representation.
1101
172
  if (!IncomingStmt)
1102
24
    return;
1103
148
1104
148
  // Take care for the incoming value being available in the incoming block.
1105
148
  // This must be done before the check for multiple PHI writes because multiple
1106
148
  // exiting edges from subregion each can be the effective written value of the
1107
148
  // subregion. As such, all of them must be made available in the subregion
1108
148
  // statement.
1109
148
  ensureValueRead(IncomingValue, IncomingStmt);
1110
148
1111
148
  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
1112
148
  if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
1113
8
    assert(Acc->getAccessInstruction() == PHI);
1114
8
    Acc->addIncoming(IncomingBlock, IncomingValue);
1115
8
    return;
1116
8
  }
1117
140
1118
140
  MemoryAccess *Acc = addMemoryAccess(
1119
140
      IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true,
1120
140
      PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
1121
140
      IsExitBlock ? 
MemoryKind::ExitPHI31
:
MemoryKind::PHI109
);
1122
172
  assert(Acc);
1123
172
  Acc->addIncoming(IncomingBlock, IncomingValue);
1124
172
}
1125
1126
72
void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {
1127
72
  addMemoryAccess(PHIStmt, PHI, MemoryAccess::READ, PHI, PHI->getType(), true,
1128
72
                  PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
1129
72
                  MemoryKind::PHI);
1130
72
}
1131
1132
690
void ScopBuilder::buildDomain(ScopStmt &Stmt) {
1133
690
  isl::id Id = isl::id::alloc(scop->getIslCtx(), Stmt.getBaseName(), &Stmt);
1134
690
1135
690
  Stmt.Domain = scop->getDomainConditions(&Stmt);
1136
690
  Stmt.Domain = Stmt.Domain.set_tuple_id(Id);
1137
690
}
1138
1139
690
void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) {
1140
690
  isl::set Domain = Stmt.getDomain();
1141
1.52k
  for (unsigned u = 0, e = Domain.dim(isl::dim::set); u < e; 
u++839
) {
1142
839
    isl::id DimId = Domain.get_dim_id(isl::dim::set, u);
1143
839
    Stmt.NestLoops.push_back(static_cast<Loop *>(DimId.get_user()));
1144
839
  }
1145
690
}
1146
1147
/// Return the reduction type for a given binary operator.
1148
static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
1149
71
                                                    const Instruction *Load) {
1150
71
  if (!BinOp)
1151
0
    return MemoryAccess::RT_NONE;
1152
71
  switch (BinOp->getOpcode()) {
1153
71
  case Instruction::FAdd:
1154
0
    if (!BinOp->isFast())
1155
0
      return MemoryAccess::RT_NONE;
1156
0
    // Fall through
1157
70
  case Instruction::Add:
1158
70
    return MemoryAccess::RT_ADD;
1159
0
  case Instruction::Or:
1160
0
    return MemoryAccess::RT_BOR;
1161
0
  case Instruction::Xor:
1162
0
    return MemoryAccess::RT_BXOR;
1163
0
  case Instruction::And:
1164
0
    return MemoryAccess::RT_BAND;
1165
0
  case Instruction::FMul:
1166
0
    if (!BinOp->isFast())
1167
0
      return MemoryAccess::RT_NONE;
1168
0
    // Fall through
1169
1
  case Instruction::Mul:
1170
1
    if (DisableMultiplicativeReductions)
1171
0
      return MemoryAccess::RT_NONE;
1172
1
    return MemoryAccess::RT_MUL;
1173
1
  default:
1174
0
    return MemoryAccess::RT_NONE;
1175
0
  }
1176
0
}
1177
1178
689
void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
1179
689
  SmallVector<MemoryAccess *, 2> Loads;
1180
689
  SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
1181
689
1182
689
  // First collect candidate load-store reduction chains by iterating over all
1183
689
  // stores and collecting possible reduction loads.
1184
1.43k
  for (MemoryAccess *StoreMA : Stmt) {
1185
1.43k
    if (StoreMA->isRead())
1186
667
      continue;
1187
767
1188
767
    Loads.clear();
1189
767
    collectCandidateReductionLoads(StoreMA, Loads);
1190
767
    for (MemoryAccess *LoadMA : Loads)
1191
767
      
Candidates.push_back(std::make_pair(LoadMA, StoreMA))106
;
1192
1.43k
  }
1193
689
1194
689
  // Then check each possible candidate pair.
1195
689
  for (const auto &CandidatePair : Candidates) {
1196
106
    bool Valid = true;
1197
106
    isl::map LoadAccs = CandidatePair.first->getAccessRelation();
1198
106
    isl::map StoreAccs = CandidatePair.second->getAccessRelation();
1199
106
1200
106
    // Skip those with obviously unequal base addresses.
1201
106
    if (!LoadAccs.has_equal_space(StoreAccs)) {
1202
24
      continue;
1203
24
    }
1204
82
1205
82
    // And check if the remaining for overlap with other memory accesses.
1206
82
    isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
1207
82
    AllAccsRel = AllAccsRel.intersect_domain(Stmt.getDomain());
1208
82
    isl::set AllAccs = AllAccsRel.range();
1209
82
1210
223
    for (MemoryAccess *MA : Stmt) {
1211
223
      if (MA == CandidatePair.first || 
MA == CandidatePair.second141
)
1212
164
        continue;
1213
59
1214
59
      isl::map AccRel =
1215
59
          MA->getAccessRelation().intersect_domain(Stmt.getDomain());
1216
59
      isl::set Accs = AccRel.range();
1217
59
1218
59
      if (AllAccs.has_equal_space(Accs)) {
1219
17
        isl::set OverlapAccs = Accs.intersect(AllAccs);
1220
17
        Valid = Valid && 
OverlapAccs.is_empty()11
;
1221
17
      }
1222
223
    }
1223
82
1224
82
    if (!Valid)
1225
11
      continue;
1226
71
1227
71
    const LoadInst *Load =
1228
71
        dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
1229
71
    MemoryAccess::ReductionType RT =
1230
71
        getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load);
1231
71
1232
71
    // If no overlapping access was found we mark the load and store as
1233
71
    // reduction like.
1234
71
    CandidatePair.first->markAsReductionLike(RT);
1235
71
    CandidatePair.second->markAsReductionLike(RT);
1236
71
  }
1237
689
}
1238
1239
void ScopBuilder::collectCandidateReductionLoads(
1240
767
    MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
1241
767
  ScopStmt *Stmt = StoreMA->getStatement();
1242
767
1243
767
  auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
1244
767
  if (!Store)
1245
250
    return;
1246
517
1247
517
  // Skip if there is not one binary operator between the load and the store
1248
517
  auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
1249
517
  if (!BinOp)
1250
336
    return;
1251
181
1252
181
  // Skip if the binary operators has multiple uses
1253
181
  if (BinOp->getNumUses() != 1)
1254
12
    return;
1255
169
1256
169
  // Skip if the opcode of the binary operator is not commutative/associative
1257
169
  if (!BinOp->isCommutative() || 
!BinOp->isAssociative()164
)
1258
79
    return;
1259
90
1260
90
  // Skip if the binary operator is outside the current SCoP
1261
90
  if (BinOp->getParent() != Store->getParent())
1262
0
    return;
1263
90
1264
90
  // Skip if it is a multiplicative reduction and we disabled them
1265
90
  if (DisableMultiplicativeReductions &&
1266
90
      
(0
BinOp->getOpcode() == Instruction::Mul0
||
1267
0
       BinOp->getOpcode() == Instruction::FMul))
1268
0
    return;
1269
90
1270
90
  // Check the binary operator operands for a candidate load
1271
90
  auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
1272
90
  auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
1273
90
  if (!PossibleLoad0 && 
!PossibleLoad15
)
1274
2
    return;
1275
88
1276
88
  // A load is only a candidate if it cannot escape (thus has only this use)
1277
88
  if (PossibleLoad0 && 
PossibleLoad0->getNumUses() == 185
)
1278
85
    if (PossibleLoad0->getParent() == Store->getParent())
1279
85
      Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad0));
1280
88
  if (PossibleLoad1 && 
PossibleLoad1->getNumUses() == 122
)
1281
21
    if (PossibleLoad1->getParent() == Store->getParent())
1282
21
      Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad1));
1283
767
}
1284
1285
690
void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) {
1286
1.43k
  for (MemoryAccess *Access : Stmt.MemAccs) {
1287
1.43k
    Type *ElementType = Access->getElementType();
1288
1.43k
1289
1.43k
    MemoryKind Ty;
1290
1.43k
    if (Access->isPHIKind())
1291
180
      Ty = MemoryKind::PHI;
1292
1.25k
    else if (Access->isExitPHIKind())
1293
22
      Ty = MemoryKind::ExitPHI;
1294
1.23k
    else if (Access->isValueKind())
1295
235
      Ty = MemoryKind::Value;
1296
1.00k
    else
1297
1.00k
      Ty = MemoryKind::Array;
1298
1.43k
1299
1.43k
    auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
1300
1.43k
                                               ElementType, Access->Sizes, Ty);
1301
1.43k
    Access->buildAccessRelation(SAI);
1302
1.43k
    scop->addAccessData(Access);
1303
1.43k
  }
1304
690
}
1305
1306
#ifndef NDEBUG
1307
static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
1308
  auto PhysUse = VirtualUse::create(S, Op, &LI, false);
1309
  auto VirtUse = VirtualUse::create(S, Op, &LI, true);
1310
  assert(PhysUse.getKind() == VirtUse.getKind());
1311
}
1312
1313
/// Check the consistency of every statement's MemoryAccesses.
1314
///
1315
/// The check is carried out by expecting the "physical" kind of use (derived
1316
/// from the BasicBlocks instructions resides in) to be same as the "virtual"
1317
/// kind of use (derived from a statement's MemoryAccess).
1318
///
1319
/// The "physical" uses are taken by ensureValueRead to determine whether to
1320
/// create MemoryAccesses. When done, the kind of scalar access should be the
1321
/// same no matter which way it was derived.
1322
///
1323
/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
1324
/// can intentionally influence on the kind of uses (not corresponding to the
1325
/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
1326
/// to pick up the virtual uses. But here in the code generator, this has not
1327
/// happened yet, such that virtual and physical uses are equivalent.
1328
static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
1329
  for (auto *BB : S->getRegion().blocks()) {
1330
    for (auto &Inst : *BB) {
1331
      auto *Stmt = S->getStmtFor(&Inst);
1332
      if (!Stmt)
1333
        continue;
1334
1335
      if (isIgnoredIntrinsic(&Inst))
1336
        continue;
1337
1338
      // Branch conditions are encoded in the statement domains.
1339
      if (isa<TerminatorInst>(&Inst) && Stmt->isBlockStmt())
1340
        continue;
1341
1342
      // Verify all uses.
1343
      for (auto &Op : Inst.operands())
1344
        verifyUse(S, Op, LI);
1345
1346
      // Stores do not produce values used by other statements.
1347
      if (isa<StoreInst>(Inst))
1348
        continue;
1349
1350
      // For every value defined in the block, also check that a use of that
1351
      // value in the same statement would not be an inter-statement use. It can
1352
      // still be synthesizable or load-hoisted, but these kind of instructions
1353
      // are not directly copied in code-generation.
1354
      auto VirtDef =
1355
          VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);
1356
      assert(VirtDef.getKind() == VirtualUse::Synthesizable ||
1357
             VirtDef.getKind() == VirtualUse::Intra ||
1358
             VirtDef.getKind() == VirtualUse::Hoisted);
1359
    }
1360
  }
1361
1362
  if (S->hasSingleExitEdge())
1363
    return;
1364
1365
  // PHINodes in the SCoP region's exit block are also uses to be checked.
1366
  if (!S->getRegion().isTopLevelRegion()) {
1367
    for (auto &Inst : *S->getRegion().getExit()) {
1368
      if (!isa<PHINode>(Inst))
1369
        break;
1370
1371
      for (auto &Op : Inst.operands())
1372
        verifyUse(S, Op, LI);
1373
    }
1374
  }
1375
}
1376
#endif
1377
1378
/// Return the block that is the representing block for @p RN.
1379
27
static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
1380
27
  return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
1381
27
                           : 
RN->getNodeAs<BasicBlock>()0
;
1382
27
}
1383
1384
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
1385
373
                            OptimizationRemarkEmitter &ORE) {
1386
373
  scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
1387
373
1388
373
  buildStmts(R);
1389
373
1390
373
  // Create all invariant load instructions first. These are categorized as
1391
373
  // 'synthesizable', therefore are not part of any ScopStmt but need to be
1392
373
  // created somewhere.
1393
373
  const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
1394
1.91k
  for (BasicBlock *BB : scop->getRegion().blocks()) {
1395
1.91k
    if (isErrorBlock(*BB, scop->getRegion(), LI, DT))
1396
12
      continue;
1397
1.90k
1398
6.34k
    
for (Instruction &Inst : *BB) 1.90k
{
1399
6.34k
      LoadInst *Load = dyn_cast<LoadInst>(&Inst);
1400
6.34k
      if (!Load)
1401
5.86k
        continue;
1402
475
1403
475
      if (!RIL.count(Load))
1404
417
        continue;
1405
58
1406
58
      // Invariant loads require a MemoryAccess to be created in some statement.
1407
58
      // It is not important to which statement the MemoryAccess is added
1408
58
      // because it will later be removed from the ScopStmt again. We chose the
1409
58
      // first statement of the basic block the LoadInst is in.
1410
58
      ArrayRef<ScopStmt *> List = scop->getStmtListFor(BB);
1411
58
      assert(!List.empty());
1412
58
      ScopStmt *RILStmt = List.front();
1413
58
      buildMemoryAccess(Load, RILStmt);
1414
58
    }
1415
1.91k
  }
1416
373
  buildAccessFunctions();
1417
373
1418
373
  // In case the region does not have an exiting block we will later (during
1419
373
  // code generation) split the exit block. This will move potential PHI nodes
1420
373
  // from the current exit block into the new region exiting block. Hence, PHI
1421
373
  // nodes that are at this point not part of the region will be.
1422
373
  // To handle these PHI nodes later we will now model their operands as scalar
1423
373
  // accesses. Note that we do not model anything in the exit block if we have
1424
373
  // an exiting block in the region, as there will not be any splitting later.
1425
373
  if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge()) {
1426
62
    for (Instruction &Inst : *R.getExit()) {
1427
62
      PHINode *PHI = dyn_cast<PHINode>(&Inst);
1428
62
      if (!PHI)
1429
46
        break;
1430
16
1431
16
      buildPHIAccesses(nullptr, PHI, nullptr, true);
1432
16
    }
1433
46
  }
1434
373
1435
373
  // Create memory accesses for global reads since all arrays are now known.
1436
373
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
1437
373
  for (auto GlobalReadPair : GlobalReads) {
1438
2
    ScopStmt *GlobalReadStmt = GlobalReadPair.first;
1439
2
    Instruction *GlobalRead = GlobalReadPair.second;
1440
2
    for (auto *BP : ArrayBasePointers)
1441
3
      addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
1442
3
                     BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
1443
2
  }
1444
373
1445
373
  scop->buildInvariantEquivalenceClasses();
1446
373
1447
373
  /// A map from basic blocks to their invalid domains.
1448
373
  DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
1449
373
1450
373
  if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) {
1451
0
    DEBUG(dbgs() << "Bailing-out because buildDomains encountered problems\n");
1452
0
    return;
1453
0
  }
1454
373
1455
373
  scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap);
1456
373
1457
373
  // Initialize the invalid domain.
1458
373
  for (ScopStmt &Stmt : scop->Stmts)
1459
1.87k
    if (Stmt.isBlockStmt())
1460
1.85k
      Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()]);
1461
27
    else
1462
27
      Stmt.setInvalidDomain(InvalidDomainMap[getRegionNodeBasicBlock(
1463
27
          Stmt.getRegion()->getNode())]);
1464
373
1465
373
  // Remove empty statements.
1466
373
  // Exit early in case there are no executable statements left in this scop.
1467
373
  scop->removeStmtNotInDomainMap();
1468
373
  scop->simplifySCoP(false);
1469
373
  if (scop->isEmpty()) {
1470
11
    DEBUG(dbgs() << "Bailing-out because SCoP is empty\n");
1471
11
    return;
1472
11
  }
1473
362
1474
362
  // The ScopStmts now have enough information to initialize themselves.
1475
690
  
for (ScopStmt &Stmt : *scop) 362
{
1476
690
    buildDomain(Stmt);
1477
690
    collectSurroundingLoops(Stmt);
1478
690
    buildAccessRelations(Stmt);
1479
690
1480
690
    if (DetectReductions)
1481
689
      checkForReductions(Stmt);
1482
690
  }
1483
362
1484
362
  // Check early for a feasible runtime context.
1485
362
  if (!scop->hasFeasibleRuntimeContext()) {
1486
1
    DEBUG(dbgs() << "Bailing-out because of unfeasible context (early)\n");
1487
1
    return;
1488
1
  }
1489
361
1490
361
  // Check early for profitability. Afterwards it cannot change anymore,
1491
361
  // only the runtime context could become infeasible.
1492
361
  if (!scop->isProfitable(UnprofitableScalarAccs)) {
1493
1
    scop->invalidate(PROFITABLE, DebugLoc());
1494
1
    DEBUG(dbgs() << "Bailing-out because SCoP is not considered profitable\n");
1495
1
    return;
1496
1
  }
1497
360
1498
360
  scop->buildSchedule(LI);
1499
360
1500
360
  scop->finalizeAccesses();
1501
360
1502
360
  scop->realignParams();
1503
360
  scop->addUserContext();
1504
360
1505
360
  // After the context was fully constructed, thus all our knowledge about
1506
360
  // the parameters is in there, we add all recorded assumptions to the
1507
360
  // assumed/invalid context.
1508
360
  scop->addRecordedAssumptions();
1509
360
1510
360
  scop->simplifyContexts();
1511
360
  if (!scop->buildAliasChecks(AA)) {
1512
3
    DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
1513
3
    return;
1514
3
  }
1515
357
1516
357
  scop->hoistInvariantLoads();
1517
357
  scop->canonicalizeDynamicBasePtrs();
1518
357
  scop->verifyInvariantLoads();
1519
357
  scop->simplifySCoP(true);
1520
357
1521
357
  // Check late for a feasible runtime context because profitability did not
1522
357
  // change.
1523
357
  if (!scop->hasFeasibleRuntimeContext()) {
1524
8
    DEBUG(dbgs() << "Bailing-out because of unfeasible context (late)\n");
1525
8
    return;
1526
8
  }
1527
349
1528
#ifndef NDEBUG
1529
  verifyUses(scop.get(), LI, DT);
1530
#endif
1531
}
1532
1533
ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
1534
                         const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
1535
                         ScopDetection &SD, ScalarEvolution &SE,
1536
                         OptimizationRemarkEmitter &ORE)
1537
373
    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
1538
373
  DebugLoc Beg, End;
1539
373
  auto P = getBBPairForRegion(R);
1540
373
  getDebugLocations(P, Beg, End);
1541
373
1542
373
  std::string Msg = "SCoP begins here.";
1543
373
  ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEntry", Beg, P.first)
1544
373
           << Msg);
1545
373
1546
373
  buildScop(*R, AC, ORE);
1547
373
1548
373
  DEBUG(dbgs() << *scop);
1549
373
1550
373
  if (!scop->hasFeasibleRuntimeContext()) {
1551
24
    InfeasibleScops++;
1552
24
    Msg = "SCoP ends here but was dismissed.";
1553
24
    DEBUG(dbgs() << "SCoP detected but dismissed\n");
1554
24
    scop.reset();
1555
349
  } else {
1556
349
    Msg = "SCoP ends here.";
1557
349
    ++ScopFound;
1558
349
    if (scop->getMaxLoopDepth() > 0)
1559
331
      ++RichScopFound;
1560
349
  }
1561
373
1562
373
  if (R->isTopLevelRegion())
1563
0
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.first)
1564
0
             << Msg);
1565
373
  else
1566
373
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.second)
1567
373
             << Msg);
1568
373
}