Coverage Report

Created: 2017-03-28 09:59

/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 "llvm/Analysis/RegionIterator.h"
22
#include "llvm/IR/DiagnosticInfo.h"
23
24
using namespace llvm;
25
using namespace polly;
26
27
1.86k
#define DEBUG_TYPE "polly-scops"
28
29
STATISTIC(ScopFound, "Number of valid Scops");
30
STATISTIC(RichScopFound, "Number of Scops containing a loop");
31
STATISTIC(InfeasibleScops,
32
          "Number of SCoPs with statically infeasible context.");
33
34
static cl::opt<bool> ModelReadOnlyScalars(
35
    "polly-analyze-read-only-scalars",
36
    cl::desc("Model read-only scalar values in the scop description"),
37
    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
38
39
void ScopBuilder::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
40
1.51k
                                   bool IsExitBlock) {
41
1.51k
42
1.51k
  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
43
1.51k
  // true, are not modeled as ordinary PHI nodes as they are not part of the
44
1.51k
  // region. However, we model the operands in the predecessor blocks that are
45
1.51k
  // part of the region as regular scalar accesses.
46
1.51k
47
1.51k
  // If we can synthesize a PHI we can skip it, however only if it is in
48
1.51k
  // the region. If it is not it can only be in the exit block of the region.
49
1.51k
  // In this case we model the operands but not the PHI itself.
50
1.51k
  auto *Scope = LI.getLoopFor(PHI->getParent());
51
1.51k
  if (
!IsExitBlock && 1.51k
canSynthesize(PHI, *scop, &SE, Scope)1.47k
)
52
1.32k
    return;
53
1.51k
54
1.51k
  // PHI nodes are modeled as if they had been demoted prior to the SCoP
55
1.51k
  // detection. Hence, the PHI is a load of a new memory location in which the
56
1.51k
  // incoming value was written at the end of the incoming basic block.
57
190
  bool OnlyNonAffineSubRegionOperands = true;
58
595
  for (unsigned u = 0; 
u < PHI->getNumIncomingValues()595
;
u++405
)
{405
59
405
    Value *Op = PHI->getIncomingValue(u);
60
405
    BasicBlock *OpBB = PHI->getIncomingBlock(u);
61
405
62
405
    // Do not build PHI dependences inside a non-affine subregion, but make
63
405
    // sure that the necessary scalar values are still made available.
64
405
    if (
NonAffineSubRegion && 405
NonAffineSubRegion->contains(OpBB)69
)
{17
65
17
      auto *OpInst = dyn_cast<Instruction>(Op);
66
17
      if (
!OpInst || 17
!NonAffineSubRegion->contains(OpInst)8
)
67
10
        ensureValueRead(Op, OpBB);
68
17
      continue;
69
17
    }
70
405
71
388
    OnlyNonAffineSubRegionOperands = false;
72
388
    ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
73
388
  }
74
190
75
190
  if (
!OnlyNonAffineSubRegionOperands && 190
!IsExitBlock184
)
{145
76
145
    addPHIReadAccess(PHI);
77
145
  }
78
190
}
79
80
11.3k
void ScopBuilder::buildScalarDependences(Instruction *Inst) {
81
11.3k
  assert(!isa<PHINode>(Inst));
82
11.3k
83
11.3k
  // Pull-in required operands.
84
11.3k
  for (Use &Op : Inst->operands())
85
21.3k
    ensureValueRead(Op.get(), Inst->getParent());
86
11.3k
}
87
88
17.1k
void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
89
17.1k
  // Check for uses of this instruction outside the scop. Because we do not
90
17.1k
  // iterate over such instructions and therefore did not "ensure" the existence
91
17.1k
  // of a write, we must determine such use here.
92
15.2k
  for (Use &U : Inst->uses()) {
93
15.2k
    Instruction *UI = dyn_cast<Instruction>(U.getUser());
94
15.2k
    if (!UI)
95
0
      continue;
96
15.2k
97
15.2k
    BasicBlock *UseParent = getUseBlock(U);
98
15.2k
    BasicBlock *UserParent = UI->getParent();
99
15.2k
100
15.2k
    // An escaping value is either used by an instruction not within the scop,
101
15.2k
    // or (when the scop region's exit needs to be simplified) by a PHI in the
102
15.2k
    // scop's exit block. This is because region simplification before code
103
15.2k
    // generation inserts new basic blocks before the PHI such that its incoming
104
15.2k
    // blocks are not in the scop anymore.
105
15.2k
    if (!scop->contains(UseParent) ||
106
15.1k
        
(isa<PHINode>(UI) && 15.1k
scop->isExit(UserParent)1.53k
&&
107
87
         
scop->hasSingleExitEdge()53
))
{87
108
87
      // At least one escaping use found.
109
87
      ensureValueWrite(Inst);
110
87
      break;
111
87
    }
112
15.2k
  }
113
17.1k
}
114
115
2.85k
bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
116
2.85k
  Value *Val = Inst.getValueOperand();
117
2.85k
  Type *ElementType = Val->getType();
118
2.85k
  Value *Address = Inst.getPointerOperand();
119
2.85k
  const SCEV *AccessFunction =
120
2.85k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
121
2.85k
  const SCEVUnknown *BasePointer =
122
2.85k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
123
2.85k
  enum MemoryAccess::AccessType AccType =
124
1.50k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.50k
:
MemoryAccess::MUST_WRITE1.35k
;
125
2.85k
126
2.85k
  if (auto *
BitCast2.85k
= dyn_cast<BitCastInst>(Address))
{75
127
75
    auto *Src = BitCast->getOperand(0);
128
75
    auto *SrcTy = Src->getType();
129
75
    auto *DstTy = BitCast->getType();
130
75
    // Do not try to delinearize non-sized (opaque) pointers.
131
75
    if (
(SrcTy->isPointerTy() && 75
!SrcTy->getPointerElementType()->isSized()75
) ||
132
74
        
(DstTy->isPointerTy() && 74
!DstTy->getPointerElementType()->isSized()74
))
{1
133
1
      return false;
134
1
    }
135
74
    
if (74
SrcTy->isPointerTy() && 74
DstTy->isPointerTy()74
&&
136
74
        DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
137
74
            DL.getTypeAllocSize(DstTy->getPointerElementType()))
138
35
      Address = Src;
139
74
  }
140
2.85k
141
2.85k
  auto *GEP = dyn_cast<GetElementPtrInst>(Address);
142
2.85k
  if (!GEP)
143
613
    return false;
144
2.85k
145
2.24k
  std::vector<const SCEV *> Subscripts;
146
2.24k
  std::vector<int> Sizes;
147
2.24k
  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
148
2.24k
  auto *BasePtr = GEP->getOperand(0);
149
2.24k
150
2.24k
  if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
151
14
    BasePtr = BasePtrCast->getOperand(0);
152
2.24k
153
2.24k
  // Check for identical base pointers to ensure that we do not miss index
154
2.24k
  // offsets that have been added before this GEP is applied.
155
2.24k
  if (BasePtr != BasePointer->getValue())
156
70
    return false;
157
2.24k
158
2.17k
  std::vector<const SCEV *> SizesSCEV;
159
2.17k
160
2.17k
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
161
2.17k
162
2.17k
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
163
2.23k
  for (auto *Subscript : Subscripts) {
164
2.23k
    InvariantLoadsSetTy AccessILS;
165
2.23k
    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
166
2.23k
                      &AccessILS))
167
138
      return false;
168
2.23k
169
2.09k
    for (LoadInst *LInst : AccessILS)
170
43
      
if (43
!ScopRIL.count(LInst)43
)
171
3
        return false;
172
2.09k
  }
173
2.17k
174
2.03k
  
if (2.03k
Sizes.empty()2.03k
)
175
1.85k
    return false;
176
2.03k
177
179
  SizesSCEV.push_back(nullptr);
178
179
179
179
  for (auto V : Sizes)
180
198
    SizesSCEV.push_back(SE.getSCEV(
181
198
        ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
182
179
183
179
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
184
179
                 Subscripts, SizesSCEV, Val);
185
179
  return true;
186
2.03k
}
187
188
2.67k
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
189
2.67k
  if (!PollyDelinearize)
190
6
    return false;
191
2.67k
192
2.67k
  Value *Address = Inst.getPointerOperand();
193
2.67k
  Value *Val = Inst.getValueOperand();
194
2.67k
  Type *ElementType = Val->getType();
195
2.67k
  unsigned ElementSize = DL.getTypeAllocSize(ElementType);
196
2.67k
  enum MemoryAccess::AccessType AccType =
197
1.40k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.40k
:
MemoryAccess::MUST_WRITE1.26k
;
198
2.67k
199
2.67k
  const SCEV *AccessFunction =
200
2.67k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
201
2.67k
  const SCEVUnknown *BasePointer =
202
2.67k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
203
2.67k
204
2.67k
  assert(BasePointer && "Could not find base pointer");
205
2.67k
206
2.67k
  auto &InsnToMemAcc = scop->getInsnToMemAccMap();
207
2.67k
  auto AccItr = InsnToMemAcc.find(Inst);
208
2.67k
  if (AccItr == InsnToMemAcc.end())
209
2.51k
    return false;
210
2.67k
211
159
  std::vector<const SCEV *> Sizes = {nullptr};
212
159
213
159
  Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
214
159
               AccItr->second.Shape->DelinearizedSizes.end());
215
159
  // Remove the element size. This information is already provided by the
216
159
  // ElementSize parameter. In case the element size of this access and the
217
159
  // element size used for delinearization differs the delinearization is
218
159
  // incorrect. Hence, we invalidate the scop.
219
159
  //
220
159
  // TODO: Handle delinearization with differing element sizes.
221
159
  auto DelinearizedSize =
222
159
      cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
223
159
  Sizes.pop_back();
224
159
  if (ElementSize != DelinearizedSize)
225
2
    scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
226
159
227
159
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
228
159
                 AccItr->second.DelinearizedSubscripts, Sizes, Val);
229
159
  return true;
230
2.67k
}
231
232
2.91k
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
233
2.91k
  auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
234
2.91k
235
2.91k
  if (MemIntr == nullptr)
236
2.90k
    return false;
237
2.91k
238
13
  auto *L = LI.getLoopFor(Inst->getParent());
239
13
  auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
240
13
  assert(LengthVal);
241
13
242
13
  // Check if the length val is actually affine or if we overapproximate it
243
13
  InvariantLoadsSetTy AccessILS;
244
13
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
245
13
246
13
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
247
13
  bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
248
13
                                     LengthVal, SE, &AccessILS);
249
13
  for (LoadInst *LInst : AccessILS)
250
0
    
if (0
!ScopRIL.count(LInst)0
)
251
0
      LengthIsAffine = false;
252
13
  if (!LengthIsAffine)
253
2
    LengthVal = nullptr;
254
13
255
13
  auto *DestPtrVal = MemIntr->getDest();
256
13
  assert(DestPtrVal);
257
13
258
13
  auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
259
13
  assert(DestAccFunc);
260
13
  // Ignore accesses to "NULL".
261
13
  // TODO: We could use this to optimize the region further, e.g., intersect
262
13
  //       the context with
263
13
  //          isl_set_complement(isl_set_params(getDomain()))
264
13
  //       as we know it would be undefined to execute this instruction anyway.
265
13
  if (DestAccFunc->isZero())
266
2
    return true;
267
13
268
11
  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
269
11
  assert(DestPtrSCEV);
270
11
  DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
271
11
  addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
272
11
                 IntegerType::getInt8Ty(DestPtrVal->getContext()),
273
11
                 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
274
11
                 Inst.getValueOperand());
275
11
276
11
  auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
277
11
  if (!MemTrans)
278
5
    return true;
279
11
280
6
  auto *SrcPtrVal = MemTrans->getSource();
281
6
  assert(SrcPtrVal);
282
6
283
6
  auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
284
6
  assert(SrcAccFunc);
285
6
  // Ignore accesses to "NULL".
286
6
  // TODO: See above TODO
287
6
  if (SrcAccFunc->isZero())
288
0
    return true;
289
6
290
6
  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
291
6
  assert(SrcPtrSCEV);
292
6
  SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
293
6
  addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
294
6
                 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
295
6
                 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
296
6
                 Inst.getValueOperand());
297
6
298
6
  return true;
299
6
}
300
301
2.90k
bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
302
2.90k
  auto *CI = dyn_cast_or_null<CallInst>(Inst);
303
2.90k
304
2.90k
  if (CI == nullptr)
305
2.85k
    return false;
306
2.90k
307
48
  
if (48
CI->doesNotAccessMemory() || 48
isIgnoredIntrinsic(CI)25
)
308
34
    return true;
309
48
310
14
  bool ReadOnly = false;
311
14
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
312
14
  auto *CalledFunction = CI->getCalledFunction();
313
14
  switch (AA.getModRefBehavior(CalledFunction)) {
314
0
  case FMRB_UnknownModRefBehavior:
315
0
    llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
316
0
  case FMRB_DoesNotAccessMemory:
317
0
    return true;
318
0
  case FMRB_DoesNotReadMemory:
319
0
  case FMRB_OnlyAccessesInaccessibleMem:
320
0
  case FMRB_OnlyAccessesInaccessibleOrArgMem:
321
0
    return false;
322
8
  case FMRB_OnlyReadsMemory:
323
8
    GlobalReads.push_back(CI);
324
8
    return true;
325
4
  case FMRB_OnlyReadsArgumentPointees:
326
4
    ReadOnly = true;
327
4
  // Fall through
328
6
  case FMRB_OnlyAccessesArgumentPointees:
329
4
    auto AccType = ReadOnly ? 
MemoryAccess::READ4
:
MemoryAccess::MAY_WRITE2
;
330
6
    Loop *L = LI.getLoopFor(Inst->getParent());
331
16
    for (const auto &Arg : CI->arg_operands()) {
332
16
      if (!Arg->getType()->isPointerTy())
333
6
        continue;
334
16
335
10
      auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
336
10
      if (ArgSCEV->isZero())
337
4
        continue;
338
10
339
6
      auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
340
6
      addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
341
6
                     ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
342
6
    }
343
6
    return true;
344
14
  }
345
14
346
0
  return true;
347
14
}
348
349
2.51k
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
350
2.51k
  Value *Address = Inst.getPointerOperand();
351
2.51k
  Value *Val = Inst.getValueOperand();
352
2.51k
  Type *ElementType = Val->getType();
353
2.51k
  enum MemoryAccess::AccessType AccType =
354
1.31k
      isa<LoadInst>(Inst) ? 
MemoryAccess::READ1.31k
:
MemoryAccess::MUST_WRITE1.19k
;
355
2.51k
356
2.51k
  const SCEV *AccessFunction =
357
2.51k
      SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
358
2.51k
  const SCEVUnknown *BasePointer =
359
2.51k
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
360
2.51k
361
2.51k
  assert(BasePointer && "Could not find base pointer");
362
2.51k
  AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
363
2.51k
364
2.51k
  // Check if the access depends on a loop contained in a non-affine subregion.
365
2.51k
  bool isVariantInNonAffineLoop = false;
366
2.51k
  SetVector<const Loop *> Loops;
367
2.51k
  findLoops(AccessFunction, Loops);
368
2.51k
  for (const Loop *L : Loops)
369
1.49k
    
if (1.49k
Stmt->contains(L)1.49k
)
{8
370
8
      isVariantInNonAffineLoop = true;
371
8
      break;
372
8
    }
373
2.51k
374
2.51k
  InvariantLoadsSetTy AccessILS;
375
2.51k
376
2.51k
  Loop *SurroundingLoop = Stmt->getSurroundingLoop();
377
2.51k
  bool IsAffine = !isVariantInNonAffineLoop &&
378
2.50k
                  isAffineExpr(&scop->getRegion(), SurroundingLoop,
379
2.50k
                               AccessFunction, SE, &AccessILS);
380
2.51k
381
2.51k
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
382
2.51k
  for (LoadInst *LInst : AccessILS)
383
46
    
if (46
!ScopRIL.count(LInst)46
)
384
6
      IsAffine = false;
385
2.51k
386
2.51k
  if (
!IsAffine && 2.51k
AccType == MemoryAccess::MUST_WRITE31
)
387
20
    AccType = MemoryAccess::MAY_WRITE;
388
2.51k
389
2.51k
  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
390
2.51k
                 {AccessFunction}, {nullptr}, Val);
391
2.51k
}
392
393
2.91k
void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
394
2.91k
395
2.91k
  if (buildAccessMemIntrinsic(Inst, Stmt))
396
13
    return;
397
2.91k
398
2.90k
  
if (2.90k
buildAccessCallInst(Inst, Stmt)2.90k
)
399
48
    return;
400
2.90k
401
2.85k
  
if (2.85k
buildAccessMultiDimFixed(Inst, Stmt)2.85k
)
402
179
    return;
403
2.85k
404
2.67k
  
if (2.67k
buildAccessMultiDimParam(Inst, Stmt)2.67k
)
405
159
    return;
406
2.67k
407
2.51k
  buildAccessSingleDim(Inst, Stmt);
408
2.51k
}
409
410
1.91k
void ScopBuilder::buildAccessFunctions(Region &SR) {
411
1.91k
412
1.91k
  if (
scop->isNonAffineSubRegion(&SR)1.91k
)
{96
413
96
    for (BasicBlock *BB : SR.blocks())
414
275
      buildAccessFunctions(*BB, &SR);
415
96
    return;
416
96
  }
417
1.91k
418
7.09k
  
for (auto I = SR.element_begin(), E = SR.element_end(); 1.81k
I != E7.09k
;
++I5.28k
)
419
5.28k
    
if (5.28k
I->isSubRegion()5.28k
)
420
979
      buildAccessFunctions(*I->getNodeAs<Region>());
421
5.28k
    else
422
4.30k
      buildAccessFunctions(*I->getNodeAs<BasicBlock>());
423
1.81k
}
424
425
1.91k
void ScopBuilder::buildStmts(Region &SR) {
426
1.91k
427
1.91k
  if (
scop->isNonAffineSubRegion(&SR)1.91k
)
{96
428
96
    Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
429
96
    auto &BoxedLoops = scop->getBoxedLoops();
430
106
    while (BoxedLoops.count(SurroundingLoop))
431
10
      SurroundingLoop = SurroundingLoop->getParentLoop();
432
96
    scop->addScopStmt(&SR, SurroundingLoop);
433
96
    return;
434
96
  }
435
1.91k
436
7.09k
  
for (auto I = SR.element_begin(), E = SR.element_end(); 1.81k
I != E7.09k
;
++I5.28k
)
437
5.28k
    
if (5.28k
I->isSubRegion()5.28k
)
438
979
      buildStmts(*I->getNodeAs<Region>());
439
4.30k
    else {
440
4.30k
      Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
441
4.30k
      scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop);
442
4.30k
    }
443
1.81k
}
444
445
void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
446
                                       Region *NonAffineSubRegion,
447
4.71k
                                       bool IsExitBlock) {
448
4.71k
  // We do not build access functions for error blocks, as they may contain
449
4.71k
  // instructions we can not model.
450
4.71k
  if (
isErrorBlock(BB, scop->getRegion(), LI, DT) && 4.71k
!IsExitBlock39
)
451
39
    return;
452
4.71k
453
4.67k
  ScopStmt *Stmt = scop->getStmtFor(&BB);
454
4.67k
455
17.3k
  for (Instruction &Inst : BB) {
456
17.3k
    PHINode *PHI = dyn_cast<PHINode>(&Inst);
457
17.3k
    if (PHI)
458
1.51k
      buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
459
17.3k
460
17.3k
    // For the exit block we stop modeling after the last PHI node.
461
17.3k
    if (
!PHI && 17.3k
IsExitBlock15.8k
)
462
137
      break;
463
17.3k
464
17.2k
    
if (auto 17.2k
MemInst17.2k
= MemAccInst::dyn_cast(Inst))
{2.91k
465
2.91k
      assert(Stmt && "Cannot build access function in non-existing statement");
466
2.91k
      buildMemoryAccess(MemInst, Stmt);
467
2.91k
    }
468
17.2k
469
17.2k
    if (isIgnoredIntrinsic(&Inst))
470
28
      continue;
471
17.2k
472
17.2k
    // PHI nodes have already been modeled above and TerminatorInsts that are
473
17.2k
    // not part of a non-affine subregion are fully modeled and regenerated
474
17.2k
    // from the polyhedral domains. Hence, they do not need to be modeled as
475
17.2k
    // explicit data dependences.
476
17.1k
    
if (17.1k
!PHI && 17.1k
(!isa<TerminatorInst>(&Inst) || 15.6k
NonAffineSubRegion4.53k
))
477
11.3k
      buildScalarDependences(&Inst);
478
17.1k
479
17.1k
    if (!IsExitBlock)
480
17.1k
      buildEscapingDependences(&Inst);
481
17.1k
  }
482
4.67k
}
483
484
MemoryAccess *ScopBuilder::addMemoryAccess(
485
    BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
486
    Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
487
    ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
488
3.82k
    MemoryKind Kind) {
489
3.82k
  ScopStmt *Stmt = scop->getStmtFor(BB);
490
3.82k
491
3.82k
  // Do not create a memory access for anything not in the SCoP. It would be
492
3.82k
  // ignored anyway.
493
3.82k
  if (!Stmt)
494
0
    return nullptr;
495
3.82k
496
3.82k
  Value *BaseAddr = BaseAddress;
497
3.82k
  std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
498
3.82k
499
3.82k
  bool isKnownMustAccess = false;
500
3.82k
501
3.82k
  // Accesses in single-basic block statements are always excuted.
502
3.82k
  if (Stmt->isBlockStmt())
503
3.46k
    isKnownMustAccess = true;
504
3.82k
505
3.82k
  if (
Stmt->isRegionStmt()3.82k
)
{357
506
357
    // Accesses that dominate the exit block of a non-affine region are always
507
357
    // executed. In non-affine regions there may exist MemoryKind::Values that
508
357
    // do not dominate the exit. MemoryKind::Values will always dominate the
509
357
    // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
510
357
    // non-affine region.
511
357
    if (DT.dominates(BB, Stmt->getRegion()->getExit()))
512
232
      isKnownMustAccess = true;
513
357
  }
514
3.82k
515
3.82k
  // Non-affine PHI writes do not "happen" at a particular instruction, but
516
3.82k
  // after exiting the statement. Therefore they are guaranteed to execute and
517
3.82k
  // overwrite the old value.
518
3.82k
  if (
Kind == MemoryKind::PHI || 3.82k
Kind == MemoryKind::ExitPHI3.46k
)
519
430
    isKnownMustAccess = true;
520
3.82k
521
3.82k
  if (
!isKnownMustAccess && 3.82k
AccType == MemoryAccess::MUST_WRITE116
)
522
61
    AccType = MemoryAccess::MAY_WRITE;
523
3.82k
524
3.82k
  auto *Access =
525
3.82k
      new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType, Affine,
526
3.82k
                       Subscripts, Sizes, AccessValue, Kind, BaseName);
527
3.82k
528
3.82k
  scop->addAccessFunction(Access);
529
3.82k
  Stmt->addAccess(Access);
530
3.82k
  return Access;
531
3.82k
}
532
533
void ScopBuilder::addArrayAccess(
534
    MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
535
    Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
536
2.89k
    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
537
2.89k
  ArrayBasePointers.insert(BaseAddress);
538
2.89k
  addMemoryAccess(MemAccInst->getParent(), MemAccInst, AccType, BaseAddress,
539
2.89k
                  ElementType, IsAffine, AccessValue, Subscripts, Sizes,
540
2.89k
                  MemoryKind::Array);
541
2.89k
}
542
543
310
void ScopBuilder::ensureValueWrite(Instruction *Inst) {
544
310
  ScopStmt *Stmt = scop->getStmtFor(Inst);
545
310
546
310
  // Inst not defined within this SCoP.
547
310
  if (!Stmt)
548
12
    return;
549
310
550
310
  // Do not process further if the instruction is already written.
551
298
  
if (298
Stmt->lookupValueWriteOf(Inst)298
)
552
47
    return;
553
298
554
251
  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
555
251
                  Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
556
251
                  ArrayRef<const SCEV *>(), MemoryKind::Value);
557
251
}
558
559
21.6k
void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
560
21.6k
561
21.6k
  // There cannot be an "access" for literal constants. BasicBlock references
562
21.6k
  // (jump destinations) also never change.
563
21.6k
  if (
(isa<Constant>(V) && 21.6k
!isa<GlobalVariable>(V)5.48k
) ||
isa<BasicBlock>(V)16.4k
)
564
5.64k
    return;
565
21.6k
566
21.6k
  // If the instruction can be synthesized and the user is in the region we do
567
21.6k
  // not need to add a value dependences.
568
16.0k
  auto *Scope = LI.getLoopFor(UserBB);
569
16.0k
  if (canSynthesize(V, *scop, &SE, Scope))
570
12.1k
    return;
571
16.0k
572
16.0k
  // Do not build scalar dependences for required invariant loads as we will
573
16.0k
  // hoist them later on anyway or drop the SCoP if we cannot.
574
3.89k
  auto &ScopRIL = scop->getRequiredInvariantLoads();
575
3.89k
  if (ScopRIL.count(dyn_cast<LoadInst>(V)))
576
337
    return;
577
3.89k
578
3.89k
  // Determine the ScopStmt containing the value's definition and use. There is
579
3.89k
  // no defining ScopStmt if the value is a function argument, a global value,
580
3.89k
  // or defined outside the SCoP.
581
3.55k
  Instruction *ValueInst = dyn_cast<Instruction>(V);
582
3.52k
  ScopStmt *ValueStmt = ValueInst ? 
scop->getStmtFor(ValueInst)3.52k
:
nullptr29
;
583
3.55k
584
3.55k
  ScopStmt *UserStmt = scop->getStmtFor(UserBB);
585
3.55k
586
3.55k
  // We do not model uses outside the scop.
587
3.55k
  if (!UserStmt)
588
0
    return;
589
3.55k
590
3.55k
  // Add MemoryAccess for invariant values only if requested.
591
3.55k
  
if (3.55k
!ModelReadOnlyScalars && 3.55k
!ValueStmt11
)
592
3
    return;
593
3.55k
594
3.55k
  // Ignore use-def chains within the same ScopStmt.
595
3.55k
  
if (3.55k
ValueStmt == UserStmt3.55k
)
596
3.27k
    return;
597
3.55k
598
3.55k
  // Do not create another MemoryAccess for reloading the value if one already
599
3.55k
  // exists.
600
273
  
if (273
UserStmt->lookupValueReadOf(V)273
)
601
26
    return;
602
273
603
247
  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V,
604
247
                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
605
247
                  MemoryKind::Value);
606
247
  if (ValueInst)
607
223
    ensureValueWrite(ValueInst);
608
247
}
609
610
void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
611
388
                                 Value *IncomingValue, bool IsExitBlock) {
612
388
  // As the incoming block might turn out to be an error statement ensure we
613
388
  // will create an exit PHI SAI object. It is needed during code generation
614
388
  // and would be created later anyway.
615
388
  if (IsExitBlock)
616
103
    scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
617
103
                                   MemoryKind::ExitPHI);
618
388
619
388
  ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
620
388
  if (!IncomingStmt)
621
52
    return;
622
388
623
388
  // Take care for the incoming value being available in the incoming block.
624
388
  // This must be done before the check for multiple PHI writes because multiple
625
388
  // exiting edges from subregion each can be the effective written value of the
626
388
  // subregion. As such, all of them must be made available in the subregion
627
388
  // statement.
628
336
  ensureValueRead(IncomingValue, IncomingBlock);
629
336
630
336
  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
631
336
  if (MemoryAccess *
Acc336
= IncomingStmt->lookupPHIWriteOf(PHI))
{51
632
51
    assert(Acc->getAccessInstruction() == PHI);
633
51
    Acc->addIncoming(IncomingBlock, IncomingValue);
634
51
    return;
635
51
  }
636
336
637
285
  MemoryAccess *Acc =
638
285
      addMemoryAccess(IncomingStmt->getEntryBlock(), PHI,
639
285
                      MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
640
285
                      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
641
214
                      IsExitBlock ? 
MemoryKind::ExitPHI71
:
MemoryKind::PHI214
);
642
285
  assert(Acc);
643
285
  Acc->addIncoming(IncomingBlock, IncomingValue);
644
285
}
645
646
145
void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
647
145
  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
648
145
                  PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
649
145
                  ArrayRef<const SCEV *>(), MemoryKind::PHI);
650
145
}
651
652
934
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
653
934
  scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
654
934
655
934
  buildStmts(R);
656
934
  buildAccessFunctions(R);
657
934
658
934
  // In case the region does not have an exiting block we will later (during
659
934
  // code generation) split the exit block. This will move potential PHI nodes
660
934
  // from the current exit block into the new region exiting block. Hence, PHI
661
934
  // nodes that are at this point not part of the region will be.
662
934
  // To handle these PHI nodes later we will now model their operands as scalar
663
934
  // accesses. Note that we do not model anything in the exit block if we have
664
934
  // an exiting block in the region, as there will not be any splitting later.
665
934
  if (!scop->hasSingleExitEdge())
666
137
    buildAccessFunctions(*R.getExit(), nullptr,
667
137
                         /* IsExitBlock */ true);
668
934
669
934
  // Create memory accesses for global reads since all arrays are now known.
670
934
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
671
934
  for (auto *GlobalRead : GlobalReads)
672
8
    for (auto *BP : ArrayBasePointers)
673
16
      addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
674
16
                     BP->getType(), false, {AF}, {nullptr}, GlobalRead);
675
934
676
934
  scop->init(AA, AC, DT, LI);
677
934
}
678
679
ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
680
                         const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
681
                         ScopDetection &SD, ScalarEvolution &SE)
682
934
    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
683
934
684
934
  Function *F = R->getEntry()->getParent();
685
934
686
934
  DebugLoc Beg, End;
687
934
  getDebugLocations(getBBPairForRegion(R), Beg, End);
688
934
  std::string Msg = "SCoP begins here.";
689
934
  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
690
934
691
934
  buildScop(*R, AC);
692
934
693
934
  DEBUG(scop->print(dbgs()));
694
934
695
934
  if (
!scop->hasFeasibleRuntimeContext()934
)
{56
696
56
    InfeasibleScops++;
697
56
    Msg = "SCoP ends here but was dismissed.";
698
56
    scop.reset();
699
878
  } else {
700
878
    Msg = "SCoP ends here.";
701
878
    ++ScopFound;
702
878
    if (scop->getMaxLoopDepth() > 0)
703
818
      ++RichScopFound;
704
878
  }
705
934
706
934
  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
707
934
}