Coverage Report

Created: 2018-04-23 18:20

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Support/ScopHelper.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScopHelper.cpp - Some Helper Functions for Scop.  ------------------===//
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
// Small functions that help with Scop and LLVM-IR.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/Support/ScopHelper.h"
15
#include "polly/Options.h"
16
#include "polly/ScopInfo.h"
17
#include "polly/Support/SCEVValidator.h"
18
#include "llvm/Analysis/LoopInfo.h"
19
#include "llvm/Analysis/RegionInfo.h"
20
#include "llvm/Analysis/ScalarEvolution.h"
21
#include "llvm/Analysis/ScalarEvolutionExpander.h"
22
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
23
#include "llvm/IR/CFG.h"
24
#include "llvm/IR/IntrinsicInst.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
27
28
using namespace llvm;
29
using namespace polly;
30
31
#define DEBUG_TYPE "polly-scop-helper"
32
33
static cl::opt<bool> PollyAllowErrorBlocks(
34
    "polly-allow-error-blocks",
35
    cl::desc("Allow to speculate on the execution of 'error blocks'."),
36
    cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
37
38
static cl::list<std::string> DebugFunctions(
39
    "polly-debug-func",
40
    cl::desc("Allow calls to the specified functions in SCoPs even if their "
41
             "side-effects are unknown. This can be used to do debug output in "
42
             "Polly-transformed code."),
43
    cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
44
45
// Ensures that there is just one predecessor to the entry node from outside the
46
// region.
47
// The identity of the region entry node is preserved.
48
static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
49
292
                                RegionInfo *RI) {
50
292
  BasicBlock *EnteringBB = R->getEnteringBlock();
51
292
  BasicBlock *Entry = R->getEntry();
52
292
53
292
  // Before (one of):
54
292
  //
55
292
  //                       \    /            //
56
292
  //                      EnteringBB         //
57
292
  //                        |    \------>    //
58
292
  //   \   /                |                //
59
292
  //   Entry <--\         Entry <--\         //
60
292
  //   /   \    /         /   \    /         //
61
292
  //        ....               ....          //
62
292
63
292
  // Create single entry edge if the region has multiple entry edges.
64
292
  if (!EnteringBB) {
65
6
    SmallVector<BasicBlock *, 4> Preds;
66
6
    for (BasicBlock *P : predecessors(Entry))
67
12
      if (!R->contains(P))
68
12
        Preds.push_back(P);
69
6
70
6
    BasicBlock *NewEntering =
71
6
        SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
72
6
73
6
    if (RI) {
74
6
      // The exit block of predecessing regions must be changed to NewEntering
75
12
      for (BasicBlock *ExitPred : predecessors(NewEntering)) {
76
12
        Region *RegionOfPred = RI->getRegionFor(ExitPred);
77
12
        if (RegionOfPred->getExit() != Entry)
78
11
          continue;
79
1
80
2
        
while (1
!RegionOfPred->isTopLevelRegion() &&
81
2
               
RegionOfPred->getExit() == Entry1
) {
82
1
          RegionOfPred->replaceExit(NewEntering);
83
1
          RegionOfPred = RegionOfPred->getParent();
84
1
        }
85
1
      }
86
6
87
6
      // Make all ancestors use EnteringBB as entry; there might be edges to it
88
6
      Region *AncestorR = R->getParent();
89
6
      RI->setRegionFor(NewEntering, AncestorR);
90
11
      while (!AncestorR->isTopLevelRegion() && 
AncestorR->getEntry() == Entry6
) {
91
5
        AncestorR->replaceEntry(NewEntering);
92
5
        AncestorR = AncestorR->getParent();
93
5
      }
94
6
    }
95
6
96
6
    EnteringBB = NewEntering;
97
6
  }
98
292
  assert(R->getEnteringBlock() == EnteringBB);
99
292
100
292
  // After:
101
292
  //
102
292
  //    \    /       //
103
292
  //  EnteringBB     //
104
292
  //      |          //
105
292
  //      |          //
106
292
  //    Entry <--\   //
107
292
  //    /   \    /   //
108
292
  //         ....    //
109
292
}
110
111
// Ensure that the region has a single block that branches to the exit node.
112
static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
113
292
                               RegionInfo *RI) {
114
292
  BasicBlock *ExitBB = R->getExit();
115
292
  BasicBlock *ExitingBB = R->getExitingBlock();
116
292
117
292
  // Before:
118
292
  //
119
292
  //   (Region)   ______/  //
120
292
  //      \  |   /         //
121
292
  //       ExitBB          //
122
292
  //       /    \          //
123
292
124
292
  if (!ExitingBB) {
125
60
    SmallVector<BasicBlock *, 4> Preds;
126
60
    for (BasicBlock *P : predecessors(ExitBB))
127
140
      if (R->contains(P))
128
124
        Preds.push_back(P);
129
60
130
60
    //  Preds[0] Preds[1]      otherBB //
131
60
    //         \  |  ________/         //
132
60
    //          \ | /                  //
133
60
    //           BB                    //
134
60
    ExitingBB =
135
60
        SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
136
60
    // Preds[0] Preds[1]      otherBB  //
137
60
    //        \  /           /         //
138
60
    // BB.region_exiting    /          //
139
60
    //                  \  /           //
140
60
    //                   BB            //
141
60
142
60
    if (RI)
143
60
      RI->setRegionFor(ExitingBB, R);
144
60
145
60
    // Change the exit of nested regions, but not the region itself,
146
60
    R->replaceExitRecursive(ExitingBB);
147
60
    R->replaceExit(ExitBB);
148
60
  }
149
292
  assert(ExitingBB == R->getExitingBlock());
150
292
151
292
  // After:
152
292
  //
153
292
  //     \   /                //
154
292
  //    ExitingBB     _____/  //
155
292
  //          \      /        //
156
292
  //           ExitBB         //
157
292
  //           /    \         //
158
292
}
159
160
void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
161
292
                           RegionInfo *RI) {
162
292
  assert(R && !R->isTopLevelRegion());
163
292
  assert(!RI || RI == R->getRegionInfo());
164
292
  assert((!RI || DT) &&
165
292
         "RegionInfo requires DominatorTree to be updated as well");
166
292
167
292
  simplifyRegionEntry(R, DT, LI, RI);
168
292
  simplifyRegionExit(R, DT, LI, RI);
169
292
  assert(R->isSimple());
170
292
}
171
172
// Split the block into two successive blocks.
173
//
174
// Like llvm::SplitBlock, but also preserves RegionInfo
175
static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
176
                              DominatorTree *DT, llvm::LoopInfo *LI,
177
14
                              RegionInfo *RI) {
178
14
  assert(Old && SplitPt);
179
14
180
14
  // Before:
181
14
  //
182
14
  //  \   /  //
183
14
  //   Old   //
184
14
  //  /   \  //
185
14
186
14
  BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
187
14
188
14
  if (RI) {
189
0
    Region *R = RI->getRegionFor(Old);
190
0
    RI->setRegionFor(NewBlock, R);
191
0
  }
192
14
193
14
  // After:
194
14
  //
195
14
  //   \   /    //
196
14
  //    Old     //
197
14
  //     |      //
198
14
  //  NewBlock  //
199
14
  //   /   \    //
200
14
201
14
  return NewBlock;
202
14
}
203
204
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,
205
14
                                     LoopInfo *LI, RegionInfo *RI) {
206
14
  // Find first non-alloca instruction. Every basic block has a non-alloca
207
14
  // instruction, as every well formed basic block has a terminator.
208
14
  BasicBlock::iterator I = EntryBlock->begin();
209
14
  while (isa<AllocaInst>(I))
210
0
    ++I;
211
14
212
14
  // splitBlock updates DT, LI and RI.
213
14
  splitBlock(EntryBlock, &*I, DT, LI, RI);
214
14
}
215
216
13
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
217
13
  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
218
13
  auto *DT = DTWP ? &DTWP->getDomTree() : 
nullptr0
;
219
13
  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
220
13
  auto *LI = LIWP ? &LIWP->getLoopInfo() : 
nullptr0
;
221
13
  RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
222
13
  RegionInfo *RI = RIP ? 
&RIP->getRegionInfo()0
: nullptr;
223
13
224
13
  // splitBlock updates DT, LI and RI.
225
13
  polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI);
226
13
}
227
228
/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
229
/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
230
/// however to generate new code if the instruction is in the analyzed region
231
/// and we generate code outside/in front of that region. Hence, we generate the
232
/// code for the SDiv/SRem operands in front of the analyzed region and then
233
/// create a new SDiv/SRem operation there too.
234
struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
235
  friend struct SCEVVisitor<ScopExpander, const SCEV *>;
236
237
  explicit ScopExpander(const Region &R, ScalarEvolution &SE,
238
                        const DataLayout &DL, const char *Name, ValueMapT *VMap,
239
                        BasicBlock *RTCBB)
240
      : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
241
1.10k
        VMap(VMap), RTCBB(RTCBB) {}
242
243
1.11k
  Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
244
1.11k
    // If we generate code in the region we will immediately fall back to the
245
1.11k
    // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
246
1.11k
    // needed replace them by copies computed in the entering block.
247
1.11k
    if (!R.contains(I))
248
1.11k
      E = visit(E);
249
1.11k
    return Expander.expandCodeFor(E, Ty, I);
250
1.11k
  }
251
252
private:
253
  SCEVExpander Expander;
254
  ScalarEvolution &SE;
255
  const char *Name;
256
  const Region &R;
257
  ValueMapT *VMap;
258
  BasicBlock *RTCBB;
259
260
  const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
261
1.43k
                               Instruction *IP) {
262
1.43k
    if (!Inst || 
!R.contains(Inst)597
)
263
1.43k
      return E;
264
2
265
2
    assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
266
2
           !isa<PHINode>(Inst));
267
2
268
2
    auto *InstClone = Inst->clone();
269
2
    for (auto &Op : Inst->operands()) {
270
2
      assert(SE.isSCEVable(Op->getType()));
271
2
      auto *OpSCEV = SE.getSCEV(Op);
272
2
      auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
273
2
      InstClone->replaceUsesOfWith(Op, OpClone);
274
2
    }
275
2
276
2
    InstClone->setName(Name + Inst->getName());
277
2
    InstClone->insertBefore(IP);
278
2
    return SE.getSCEV(InstClone);
279
2
  }
280
281
1.49k
  const SCEV *visitUnknown(const SCEVUnknown *E) {
282
1.49k
283
1.49k
    // If a value mapping was given try if the underlying value is remapped.
284
1.49k
    Value *NewVal = VMap ? 
VMap->lookup(E->getValue())1.48k
:
nullptr16
;
285
1.49k
    if (NewVal) {
286
64
      auto *NewE = SE.getSCEV(NewVal);
287
64
288
64
      // While the mapped value might be different the SCEV representation might
289
64
      // not be. To this end we will check before we go into recursion here.
290
64
      if (E != NewE)
291
61
        return visit(NewE);
292
1.43k
    }
293
1.43k
294
1.43k
    Instruction *Inst = dyn_cast<Instruction>(E->getValue());
295
1.43k
    Instruction *IP;
296
1.43k
    if (Inst && 
!R.contains(Inst)598
)
297
596
      IP = Inst;
298
842
    else if (Inst && 
RTCBB->getParent() == Inst->getFunction()2
)
299
2
      IP = RTCBB->getTerminator();
300
840
    else
301
840
      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
302
1.43k
303
1.43k
    if (!Inst || 
(598
Inst->getOpcode() != Instruction::SRem598
&&
304
598
                  Inst->getOpcode() != Instruction::SDiv))
305
1.43k
      return visitGenericInst(E, Inst, IP);
306
1
307
1
    const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
308
1
    const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
309
1
310
1
    if (!SE.isKnownNonZero(RHSScev))
311
1
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
312
1
313
1
    Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
314
1
    Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
315
1
316
1
    Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
317
1
                                  LHS, RHS, Inst->getName() + Name, IP);
318
1
    return SE.getSCEV(Inst);
319
1
  }
320
321
  /// The following functions will just traverse the SCEV and rebuild it with
322
  /// the new operands returned by the traversal.
323
  ///
324
  ///{
325
909
  const SCEV *visitConstant(const SCEVConstant *E) { return E; }
326
76
  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
327
76
    return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
328
76
  }
329
15
  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
330
15
    return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
331
15
  }
332
36
  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
333
36
    return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
334
36
  }
335
14
  const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
336
14
    auto *RHSScev = visit(E->getRHS());
337
14
    if (!SE.isKnownNonZero(RHSScev))
338
8
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
339
14
    return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
340
14
  }
341
481
  const SCEV *visitAddExpr(const SCEVAddExpr *E) {
342
481
    SmallVector<const SCEV *, 4> NewOps;
343
481
    for (const SCEV *Op : E->operands())
344
1.12k
      NewOps.push_back(visit(Op));
345
481
    return SE.getAddExpr(NewOps);
346
481
  }
347
504
  const SCEV *visitMulExpr(const SCEVMulExpr *E) {
348
504
    SmallVector<const SCEV *, 4> NewOps;
349
504
    for (const SCEV *Op : E->operands())
350
1.04k
      NewOps.push_back(visit(Op));
351
504
    return SE.getMulExpr(NewOps);
352
504
  }
353
2
  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
354
2
    SmallVector<const SCEV *, 4> NewOps;
355
2
    for (const SCEV *Op : E->operands())
356
4
      NewOps.push_back(visit(Op));
357
2
    return SE.getUMaxExpr(NewOps);
358
2
  }
359
0
  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
360
0
    SmallVector<const SCEV *, 4> NewOps;
361
0
    for (const SCEV *Op : E->operands())
362
0
      NewOps.push_back(visit(Op));
363
0
    return SE.getSMaxExpr(NewOps);
364
0
  }
365
36
  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
366
36
    SmallVector<const SCEV *, 4> NewOps;
367
36
    for (const SCEV *Op : E->operands())
368
72
      NewOps.push_back(visit(Op));
369
36
    return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
370
36
  }
371
  ///}
372
};
373
374
Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
375
                            const char *Name, const SCEV *E, Type *Ty,
376
                            Instruction *IP, ValueMapT *VMap,
377
1.10k
                            BasicBlock *RTCBB) {
378
1.10k
  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
379
1.10k
  return Expander.expandCodeFor(E, Ty, IP);
380
1.10k
}
381
382
bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
383
104k
                         const DominatorTree &DT) {
384
104k
  if (!PollyAllowErrorBlocks)
385
0
    return false;
386
104k
387
104k
  if (isa<UnreachableInst>(BB.getTerminator()))
388
0
    return true;
389
104k
390
104k
  if (LI.isLoopHeader(&BB))
391
39.9k
    return false;
392
64.2k
393
64.2k
  // Basic blocks that are always executed are not considered error blocks,
394
64.2k
  // as their execution can not be a rare event.
395
64.2k
  bool DominatesAllPredecessors = true;
396
64.2k
  if (R.isTopLevelRegion()) {
397
117
    for (BasicBlock &I : *R.getEntry()->getParent())
398
634
      if (isa<ReturnInst>(I.getTerminator()) && 
!DT.dominates(&BB, &I)117
)
399
14
        DominatesAllPredecessors = false;
400
64.1k
  } else {
401
64.1k
    for (auto Pred : predecessors(R.getExit()))
402
98.9k
      if (R.contains(Pred) && 
!DT.dominates(&BB, Pred)93.2k
)
403
47.6k
        DominatesAllPredecessors = false;
404
64.1k
  }
405
64.2k
406
64.2k
  if (DominatesAllPredecessors)
407
22.7k
    return false;
408
41.4k
409
41.4k
  for (Instruction &Inst : BB)
410
338k
    if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
411
1.23k
      if (isDebugCall(CI))
412
8
        continue;
413
1.23k
414
1.23k
      if (isIgnoredIntrinsic(CI))
415
249
        continue;
416
981
417
981
      // memset, memcpy and memmove are modeled intrinsics.
418
981
      if (isa<MemSetInst>(CI) || 
isa<MemTransferInst>(CI)920
)
419
129
        continue;
420
852
421
852
      if (!CI->doesNotAccessMemory())
422
383
        return true;
423
469
      if (CI->doesNotReturn())
424
0
        return true;
425
469
    }
426
41.4k
427
41.4k
  
return false41.0k
;
428
41.4k
}
429
430
32.2k
Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
431
32.2k
  if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
432
32.1k
    if (BR->isUnconditional())
433
14.6k
      return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
434
17.5k
435
17.5k
    return BR->getCondition();
436
17.5k
  }
437
66
438
66
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
439
66
    return SI->getCondition();
440
0
441
0
  return nullptr;
442
0
}
443
444
bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
445
3.00k
                            ScalarEvolution &SE, const DominatorTree &DT) {
446
3.00k
  Loop *L = LI.getLoopFor(LInst->getParent());
447
3.00k
  auto *Ptr = LInst->getPointerOperand();
448
3.00k
  const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
449
3.33k
  while (L && 
R.contains(L)853
) {
450
350
    if (!SE.isLoopInvariant(PtrSCEV, L))
451
17
      return false;
452
333
    L = L->getParentLoop();
453
333
  }
454
3.00k
455
21.4k
  
for (auto *User : Ptr->users())2.98k
{
456
21.4k
    auto *UserI = dyn_cast<Instruction>(User);
457
21.4k
    if (!UserI || !R.contains(UserI))
458
3.06k
      continue;
459
18.4k
    if (!UserI->mayWriteToMemory())
460
18.0k
      continue;
461
396
462
396
    auto &BB = *UserI->getParent();
463
396
    if (DT.dominates(&BB, LInst->getParent()))
464
122
      return false;
465
274
466
274
    bool DominatesAllPredecessors = true;
467
274
    if (R.isTopLevelRegion()) {
468
1
      for (BasicBlock &I : *R.getEntry()->getParent())
469
5
        if (isa<ReturnInst>(I.getTerminator()) && 
!DT.dominates(&BB, &I)1
)
470
1
          DominatesAllPredecessors = false;
471
273
    } else {
472
273
      for (auto Pred : predecessors(R.getExit()))
473
532
        if (R.contains(Pred) && !DT.dominates(&BB, Pred))
474
498
          DominatesAllPredecessors = false;
475
273
    }
476
274
477
274
    if (!DominatesAllPredecessors)
478
274
      continue;
479
0
480
0
    return false;
481
0
  }
482
2.98k
483
2.98k
  
return true2.86k
;
484
2.98k
}
485
486
17.7k
bool polly::isIgnoredIntrinsic(const Value *V) {
487
17.7k
  if (auto *IT = dyn_cast<IntrinsicInst>(V)) {
488
621
    switch (IT->getIntrinsicID()) {
489
621
    // Lifetime markers are supported/ignored.
490
621
    case llvm::Intrinsic::lifetime_start:
491
307
    case llvm::Intrinsic::lifetime_end:
492
307
    // Invariant markers are supported/ignored.
493
307
    case llvm::Intrinsic::invariant_start:
494
307
    case llvm::Intrinsic::invariant_end:
495
307
    // Some misc annotations are supported/ignored.
496
307
    case llvm::Intrinsic::var_annotation:
497
307
    case llvm::Intrinsic::ptr_annotation:
498
307
    case llvm::Intrinsic::annotation:
499
307
    case llvm::Intrinsic::donothing:
500
307
    case llvm::Intrinsic::assume:
501
307
    // Some debug info intrinsics are supported/ignored.
502
307
    case llvm::Intrinsic::dbg_value:
503
307
    case llvm::Intrinsic::dbg_declare:
504
307
      return true;
505
314
    default:
506
314
      break;
507
17.4k
    }
508
17.4k
  }
509
17.4k
  return false;
510
17.4k
}
511
512
bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
513
27.9k
                          Loop *Scope) {
514
27.9k
  if (!V || !SE->isSCEVable(V->getType()))
515
4.35k
    return false;
516
23.5k
517
23.5k
  const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
518
23.5k
  if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
519
23.5k
    if (!isa<SCEVCouldNotCompute>(Scev))
520
23.5k
      if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS))
521
15.9k
        return true;
522
7.57k
523
7.57k
  return false;
524
7.57k
}
525
526
18.8k
llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {
527
18.8k
  Instruction *UI = dyn_cast<Instruction>(U.getUser());
528
18.8k
  if (!UI)
529
0
    return nullptr;
530
18.8k
531
18.8k
  if (PHINode *PHI = dyn_cast<PHINode>(UI))
532
2.03k
    return PHI->getIncomingBlock(U);
533
16.8k
534
16.8k
  return UI->getParent();
535
16.8k
}
536
537
std::tuple<std::vector<const SCEV *>, std::vector<int>>
538
2.73k
polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
539
2.73k
  std::vector<const SCEV *> Subscripts;
540
2.73k
  std::vector<int> Sizes;
541
2.73k
542
2.73k
  Type *Ty = GEP->getPointerOperandType();
543
2.73k
544
2.73k
  bool DroppedFirstDim = false;
545
2.73k
546
6.15k
  for (unsigned i = 1; i < GEP->getNumOperands(); 
i++3.41k
) {
547
3.52k
548
3.52k
    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
549
3.52k
550
3.52k
    if (i == 1) {
551
2.73k
      if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
552
2.73k
        Ty = PtrTy->getElementType();
553
2.73k
      } else 
if (auto *0
ArrayTy0
= dyn_cast<ArrayType>(Ty)) {
554
0
        Ty = ArrayTy->getElementType();
555
0
      } else {
556
0
        Subscripts.clear();
557
0
        Sizes.clear();
558
0
        break;
559
0
      }
560
2.73k
      if (auto *Const = dyn_cast<SCEVConstant>(Expr))
561
796
        if (Const->getValue()->isZero()) {
562
583
          DroppedFirstDim = true;
563
583
          continue;
564
583
        }
565
2.15k
      Subscripts.push_back(Expr);
566
2.15k
      continue;
567
2.15k
    }
568
791
569
791
    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
570
791
    if (!ArrayTy) {
571
110
      Subscripts.clear();
572
110
      Sizes.clear();
573
110
      break;
574
110
    }
575
681
576
681
    Subscripts.push_back(Expr);
577
681
    if (!(DroppedFirstDim && 
i == 2490
))
578
259
      Sizes.push_back(ArrayTy->getNumElements());
579
681
580
681
    Ty = ArrayTy->getElementType();
581
681
  }
582
2.73k
583
2.73k
  return std::make_tuple(Subscripts, Sizes);
584
2.73k
}
585
586
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
587
14.4k
                                           const BoxedLoopsSetTy &BoxedLoops) {
588
14.4k
  while (BoxedLoops.count(L))
589
46
    L = L->getParentLoop();
590
14.4k
  return L;
591
14.4k
}
592
593
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
594
                                           llvm::LoopInfo &LI,
595
14.4k
                                           const BoxedLoopsSetTy &BoxedLoops) {
596
14.4k
  Loop *L = LI.getLoopFor(BB);
597
14.4k
  return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
598
14.4k
}
599
600
1.30k
bool polly::isDebugCall(Instruction *Inst) {
601
1.30k
  auto *CI = dyn_cast<CallInst>(Inst);
602
1.30k
  if (!CI)
603
1
    return false;
604
1.30k
605
1.30k
  Function *CF = CI->getCalledFunction();
606
1.30k
  if (!CF)
607
5
    return false;
608
1.30k
609
1.30k
  return std::find(DebugFunctions.begin(), DebugFunctions.end(),
610
1.30k
                   CF->getName()) != DebugFunctions.end();
611
1.30k
}
612
613
0
static bool hasDebugCall(BasicBlock *BB) {
614
0
  for (Instruction &Inst : *BB) {
615
0
    if (isDebugCall(&Inst))
616
0
      return true;
617
0
  }
618
0
  return false;
619
0
}
620
621
11.1k
bool polly::hasDebugCall(ScopStmt *Stmt) {
622
11.1k
  // Quick skip if no debug functions have been defined.
623
11.1k
  if (DebugFunctions.empty())
624
11.1k
    return false;
625
7
626
7
  if (!Stmt)
627
0
    return false;
628
7
629
7
  for (Instruction *Inst : Stmt->getInstructions())
630
3
    if (isDebugCall(Inst))
631
2
      return true;
632
7
633
7
  
if (5
Stmt->isRegionStmt()5
) {
634
0
    for (BasicBlock *RBB : Stmt->getRegion()->blocks())
635
0
      if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB))
636
0
        return true;
637
0
  }
638
5
639
5
  return false;
640
5
}