Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
// Ensures that there is just one predecessor to the entry node from outside the
39
// region.
40
// The identity of the region entry node is preserved.
41
static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
42
281
                                RegionInfo *RI) {
43
281
  BasicBlock *EnteringBB = R->getEnteringBlock();
44
281
  BasicBlock *Entry = R->getEntry();
45
281
46
281
  // Before (one of):
47
281
  //
48
281
  //                       \    /            //
49
281
  //                      EnteringBB         //
50
281
  //                        |    \------>    //
51
281
  //   \   /                |                //
52
281
  //   Entry <--\         Entry <--\         //
53
281
  //   /   \    /         /   \    /         //
54
281
  //        ....               ....          //
55
281
56
281
  // Create single entry edge if the region has multiple entry edges.
57
281
  if (
!EnteringBB281
)
{6
58
6
    SmallVector<BasicBlock *, 4> Preds;
59
6
    for (BasicBlock *P : predecessors(Entry))
60
12
      
if (12
!R->contains(P)12
)
61
12
        Preds.push_back(P);
62
6
63
6
    BasicBlock *NewEntering =
64
6
        SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
65
6
66
6
    if (
RI6
)
{6
67
6
      // The exit block of predecessing regions must be changed to NewEntering
68
12
      for (BasicBlock *ExitPred : predecessors(NewEntering)) {
69
12
        Region *RegionOfPred = RI->getRegionFor(ExitPred);
70
12
        if (RegionOfPred->getExit() != Entry)
71
11
          continue;
72
12
73
1
        
while (1
!RegionOfPred->isTopLevelRegion() &&2
74
1
               
RegionOfPred->getExit() == Entry1
)
{1
75
1
          RegionOfPred->replaceExit(NewEntering);
76
1
          RegionOfPred = RegionOfPred->getParent();
77
1
        }
78
6
      }
79
6
80
6
      // Make all ancestors use EnteringBB as entry; there might be edges to it
81
6
      Region *AncestorR = R->getParent();
82
6
      RI->setRegionFor(NewEntering, AncestorR);
83
11
      while (
!AncestorR->isTopLevelRegion() && 11
AncestorR->getEntry() == Entry6
)
{5
84
5
        AncestorR->replaceEntry(NewEntering);
85
5
        AncestorR = AncestorR->getParent();
86
6
      }
87
6
    }
88
6
89
6
    EnteringBB = NewEntering;
90
281
  }
91
281
  assert(R->getEnteringBlock() == EnteringBB);
92
281
93
281
  // After:
94
281
  //
95
281
  //    \    /       //
96
281
  //  EnteringBB     //
97
281
  //      |          //
98
281
  //      |          //
99
281
  //    Entry <--\   //
100
281
  //    /   \    /   //
101
281
  //         ....    //
102
281
}
103
104
// Ensure that the region has a single block that branches to the exit node.
105
static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
106
281
                               RegionInfo *RI) {
107
281
  BasicBlock *ExitBB = R->getExit();
108
281
  BasicBlock *ExitingBB = R->getExitingBlock();
109
281
110
281
  // Before:
111
281
  //
112
281
  //   (Region)   ______/  //
113
281
  //      \  |   /         //
114
281
  //       ExitBB          //
115
281
  //       /    \          //
116
281
117
281
  if (
!ExitingBB281
)
{58
118
58
    SmallVector<BasicBlock *, 4> Preds;
119
58
    for (BasicBlock *P : predecessors(ExitBB))
120
136
      
if (136
R->contains(P)136
)
121
120
        Preds.push_back(P);
122
58
123
58
    //  Preds[0] Preds[1]      otherBB //
124
58
    //         \  |  ________/         //
125
58
    //          \ | /                  //
126
58
    //           BB                    //
127
58
    ExitingBB =
128
58
        SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
129
58
    // Preds[0] Preds[1]      otherBB  //
130
58
    //        \  /           /         //
131
58
    // BB.region_exiting    /          //
132
58
    //                  \  /           //
133
58
    //                   BB            //
134
58
135
58
    if (RI)
136
58
      RI->setRegionFor(ExitingBB, R);
137
58
138
58
    // Change the exit of nested regions, but not the region itself,
139
58
    R->replaceExitRecursive(ExitingBB);
140
58
    R->replaceExit(ExitBB);
141
281
  }
142
281
  assert(ExitingBB == R->getExitingBlock());
143
281
144
281
  // After:
145
281
  //
146
281
  //     \   /                //
147
281
  //    ExitingBB     _____/  //
148
281
  //          \      /        //
149
281
  //           ExitBB         //
150
281
  //           /    \         //
151
281
}
152
153
void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
154
281
                           RegionInfo *RI) {
155
281
  assert(R && !R->isTopLevelRegion());
156
281
  assert(!RI || RI == R->getRegionInfo());
157
281
  assert((!RI || DT) &&
158
281
         "RegionInfo requires DominatorTree to be updated as well");
159
281
160
281
  simplifyRegionEntry(R, DT, LI, RI);
161
281
  simplifyRegionExit(R, DT, LI, RI);
162
281
  assert(R->isSimple());
163
281
}
164
165
// Split the block into two successive blocks.
166
//
167
// Like llvm::SplitBlock, but also preserves RegionInfo
168
static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
169
                              DominatorTree *DT, llvm::LoopInfo *LI,
170
13
                              RegionInfo *RI) {
171
13
  assert(Old && SplitPt);
172
13
173
13
  // Before:
174
13
  //
175
13
  //  \   /  //
176
13
  //   Old   //
177
13
  //  /   \  //
178
13
179
13
  BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
180
13
181
13
  if (
RI13
)
{0
182
0
    Region *R = RI->getRegionFor(Old);
183
0
    RI->setRegionFor(NewBlock, R);
184
13
  }
185
13
186
13
  // After:
187
13
  //
188
13
  //   \   /    //
189
13
  //    Old     //
190
13
  //     |      //
191
13
  //  NewBlock  //
192
13
  //   /   \    //
193
13
194
13
  return NewBlock;
195
13
}
196
197
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,
198
13
                                     LoopInfo *LI, RegionInfo *RI) {
199
13
  // Find first non-alloca instruction. Every basic block has a non-alloca
200
13
  // instruction, as every well formed basic block has a terminator.
201
13
  BasicBlock::iterator I = EntryBlock->begin();
202
13
  while (isa<AllocaInst>(I))
203
0
    ++I;
204
13
205
13
  // splitBlock updates DT, LI and RI.
206
13
  splitBlock(EntryBlock, &*I, DT, LI, RI);
207
13
}
208
209
13
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
210
13
  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
211
13
  auto *DT = DTWP ? 
&DTWP->getDomTree()13
:
nullptr0
;
212
13
  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
213
13
  auto *LI = LIWP ? 
&LIWP->getLoopInfo()13
:
nullptr0
;
214
13
  RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
215
13
  RegionInfo *RI = RIP ? 
&RIP->getRegionInfo()0
:
nullptr13
;
216
13
217
13
  // splitBlock updates DT, LI and RI.
218
13
  polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI);
219
13
}
220
221
/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
222
/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
223
/// however to generate new code if the instruction is in the analyzed region
224
/// and we generate code outside/in front of that region. Hence, we generate the
225
/// code for the SDiv/SRem operands in front of the analyzed region and then
226
/// create a new SDiv/SRem operation there too.
227
struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
228
  friend struct SCEVVisitor<ScopExpander, const SCEV *>;
229
230
  explicit ScopExpander(const Region &R, ScalarEvolution &SE,
231
                        const DataLayout &DL, const char *Name, ValueMapT *VMap,
232
                        BasicBlock *RTCBB)
233
      : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
234
1.23k
        VMap(VMap), RTCBB(RTCBB) {}
235
236
1.24k
  Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
237
1.24k
    // If we generate code in the region we will immediately fall back to the
238
1.24k
    // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
239
1.24k
    // needed replace them by copies computed in the entering block.
240
1.24k
    if (!R.contains(I))
241
1.24k
      E = visit(E);
242
1.24k
    return Expander.expandCodeFor(E, Ty, I);
243
1.24k
  }
244
245
private:
246
  SCEVExpander Expander;
247
  ScalarEvolution &SE;
248
  const char *Name;
249
  const Region &R;
250
  ValueMapT *VMap;
251
  BasicBlock *RTCBB;
252
253
  const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
254
1.55k
                               Instruction *IP) {
255
1.55k
    if (
!Inst || 1.55k
!R.contains(Inst)675
)
256
1.55k
      return E;
257
1.55k
258
1.55k
    assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
259
2
           !isa<PHINode>(Inst));
260
2
261
2
    auto *InstClone = Inst->clone();
262
2
    for (auto &Op : Inst->operands()) {
263
2
      assert(SE.isSCEVable(Op->getType()));
264
2
      auto *OpSCEV = SE.getSCEV(Op);
265
2
      auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
266
2
      InstClone->replaceUsesOfWith(Op, OpClone);
267
2
    }
268
2
269
2
    InstClone->setName(Name + Inst->getName());
270
2
    InstClone->insertBefore(IP);
271
1.55k
    return SE.getSCEV(InstClone);
272
1.55k
  }
273
274
1.62k
  const SCEV *visitUnknown(const SCEVUnknown *E) {
275
1.62k
276
1.62k
    // If a value mapping was given try if the underlying value is remapped.
277
1.62k
    Value *NewVal = VMap ? 
VMap->lookup(E->getValue())1.59k
:
nullptr32
;
278
1.62k
    if (
NewVal1.62k
)
{70
279
70
      auto *NewE = SE.getSCEV(NewVal);
280
70
281
70
      // While the mapped value might be different the SCEV representation might
282
70
      // not be. To this end we will check before we go into recursion here.
283
70
      if (E != NewE)
284
67
        return visit(NewE);
285
1.62k
    }
286
1.62k
287
1.62k
    Instruction *Inst = dyn_cast<Instruction>(E->getValue());
288
1.56k
    Instruction *IP;
289
1.56k
    if (
Inst && 1.56k
!R.contains(Inst)678
)
290
676
      IP = Inst;
291
885
    else 
if (885
Inst && 885
RTCBB->getParent() == Inst->getFunction()2
)
292
2
      IP = RTCBB->getTerminator();
293
885
    else
294
883
      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
295
1.56k
296
1.56k
    if (
!Inst || 1.56k
(Inst->getOpcode() != Instruction::SRem &&678
297
678
                  Inst->getOpcode() != Instruction::SDiv))
298
1.55k
      return visitGenericInst(E, Inst, IP);
299
1.56k
300
1.56k
    const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
301
3
    const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
302
3
303
3
    if (!SE.isKnownNonZero(RHSScev))
304
1
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
305
3
306
3
    Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
307
3
    Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
308
3
309
3
    Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
310
3
                                  LHS, RHS, Inst->getName() + Name, IP);
311
1.56k
    return SE.getSCEV(Inst);
312
1.62k
  }
313
314
  /// The following functions will just traverse the SCEV and rebuild it with
315
  /// the new operands returned by the traversal.
316
  ///
317
  ///{
318
1.00k
  const SCEV *visitConstant(const SCEVConstant *E) { return E; }
319
88
  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
320
88
    return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
321
88
  }
322
12
  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
323
12
    return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
324
12
  }
325
48
  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
326
48
    return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
327
48
  }
328
11
  const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
329
11
    auto *RHSScev = visit(E->getRHS());
330
11
    if (!SE.isKnownNonZero(RHSScev))
331
8
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
332
11
    return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
333
11
  }
334
564
  const SCEV *visitAddExpr(const SCEVAddExpr *E) {
335
564
    SmallVector<const SCEV *, 4> NewOps;
336
564
    for (const SCEV *Op : E->operands())
337
1.29k
      NewOps.push_back(visit(Op));
338
564
    return SE.getAddExpr(NewOps);
339
564
  }
340
501
  const SCEV *visitMulExpr(const SCEVMulExpr *E) {
341
501
    SmallVector<const SCEV *, 4> NewOps;
342
501
    for (const SCEV *Op : E->operands())
343
1.03k
      NewOps.push_back(visit(Op));
344
501
    return SE.getMulExpr(NewOps);
345
501
  }
346
3
  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
347
3
    SmallVector<const SCEV *, 4> NewOps;
348
3
    for (const SCEV *Op : E->operands())
349
6
      NewOps.push_back(visit(Op));
350
3
    return SE.getUMaxExpr(NewOps);
351
3
  }
352
1
  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
353
1
    SmallVector<const SCEV *, 4> NewOps;
354
1
    for (const SCEV *Op : E->operands())
355
2
      NewOps.push_back(visit(Op));
356
1
    return SE.getSMaxExpr(NewOps);
357
1
  }
358
34
  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
359
34
    SmallVector<const SCEV *, 4> NewOps;
360
34
    for (const SCEV *Op : E->operands())
361
68
      NewOps.push_back(visit(Op));
362
34
    return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
363
34
  }
364
  ///}
365
};
366
367
Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
368
                            const char *Name, const SCEV *E, Type *Ty,
369
                            Instruction *IP, ValueMapT *VMap,
370
1.23k
                            BasicBlock *RTCBB) {
371
1.23k
  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
372
1.23k
  return Expander.expandCodeFor(E, Ty, IP);
373
1.23k
}
374
375
bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
376
90.4k
                         const DominatorTree &DT) {
377
90.4k
  if (!PollyAllowErrorBlocks)
378
0
    return false;
379
90.4k
380
90.4k
  
if (90.4k
isa<UnreachableInst>(BB.getTerminator())90.4k
)
381
0
    return true;
382
90.4k
383
90.4k
  
if (90.4k
LI.isLoopHeader(&BB)90.4k
)
384
34.4k
    return false;
385
90.4k
386
90.4k
  // Basic blocks that are always executed are not considered error blocks,
387
90.4k
  // as their execution can not be a rare event.
388
90.4k
  bool DominatesAllPredecessors = true;
389
55.9k
  if (
R.isTopLevelRegion()55.9k
)
{101
390
101
    for (BasicBlock &I : *R.getEntry()->getParent())
391
550
      
if (550
isa<ReturnInst>(I.getTerminator()) && 550
!DT.dominates(&BB, &I)101
)
392
12
        DominatesAllPredecessors = false;
393
55.9k
  } else {
394
55.8k
    for (auto Pred : predecessors(R.getExit()))
395
87.9k
      
if (87.9k
R.contains(Pred) && 87.9k
!DT.dominates(&BB, Pred)82.6k
)
396
40.9k
        DominatesAllPredecessors = false;
397
55.9k
  }
398
55.9k
399
55.9k
  if (DominatesAllPredecessors)
400
20.5k
    return false;
401
55.9k
402
55.9k
  // FIXME: This is a simple heuristic to determine if the load is executed
403
55.9k
  //        in a conditional. However, we actually would need the control
404
55.9k
  //        condition, i.e., the post dominance frontier. Alternatively we
405
55.9k
  //        could walk up the dominance tree until we find a block that is
406
55.9k
  //        not post dominated by the load and check if it is a conditional
407
55.9k
  //        or a loop header.
408
55.9k
  auto *DTNode = DT.getNode(&BB);
409
35.4k
  auto *IDomBB = DTNode->getIDom()->getBlock();
410
35.4k
  if (LI.isLoopHeader(IDomBB))
411
18.1k
    return false;
412
35.4k
413
35.4k
  for (Instruction &Inst : BB)
414
54.2k
    
if (CallInst *54.2k
CI54.2k
= dyn_cast<CallInst>(&Inst))
{330
415
330
      if (isIgnoredIntrinsic(CI))
416
61
        return false;
417
330
418
269
      
if (269
!CI->doesNotAccessMemory()269
)
419
249
        return true;
420
20
      
if (20
CI->doesNotReturn()20
)
421
0
        return true;
422
17.3k
    }
423
17.3k
424
16.9k
  return false;
425
90.4k
}
426
427
30.4k
Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
428
30.4k
  if (BranchInst *
BR30.4k
= dyn_cast<BranchInst>(TI))
{30.3k
429
30.3k
    if (BR->isUnconditional())
430
13.8k
      return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
431
30.3k
432
16.4k
    return BR->getCondition();
433
30.4k
  }
434
30.4k
435
66
  
if (SwitchInst *66
SI66
= dyn_cast<SwitchInst>(TI))
436
66
    return SI->getCondition();
437
66
438
0
  return nullptr;
439
30.4k
}
440
441
bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
442
2.97k
                            ScalarEvolution &SE, const DominatorTree &DT) {
443
2.97k
  Loop *L = LI.getLoopFor(LInst->getParent());
444
2.97k
  auto *Ptr = LInst->getPointerOperand();
445
2.97k
  const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
446
3.28k
  while (
L && 3.28k
R.contains(L)832
)
{329
447
329
    if (!SE.isLoopInvariant(PtrSCEV, L))
448
17
      return false;
449
329
    L = L->getParentLoop();
450
2.97k
  }
451
2.97k
452
2.95k
  
for (auto *User : Ptr->users()) 2.95k
{21.4k
453
21.4k
    auto *UserI = dyn_cast<Instruction>(User);
454
21.4k
    if (
!UserI || 21.4k
!R.contains(UserI)21.4k
)
455
3.05k
      continue;
456
18.3k
    
if (18.3k
!UserI->mayWriteToMemory()18.3k
)
457
17.9k
      continue;
458
18.3k
459
18.3k
    auto &BB = *UserI->getParent();
460
388
    if (DT.dominates(&BB, LInst->getParent()))
461
121
      return false;
462
388
463
388
    bool DominatesAllPredecessors = true;
464
267
    for (auto Pred : predecessors(R.getExit()))
465
526
      
if (526
R.contains(Pred) && 526
!DT.dominates(&BB, Pred)526
)
466
492
        DominatesAllPredecessors = false;
467
267
468
267
    if (!DominatesAllPredecessors)
469
267
      continue;
470
267
471
0
    return false;
472
2.95k
  }
473
2.95k
474
2.83k
  return true;
475
2.97k
}
476
477
35.4k
bool polly::isIgnoredIntrinsic(const Value *V) {
478
35.4k
  if (auto *
IT35.4k
= dyn_cast<IntrinsicInst>(V))
{254
479
254
    switch (IT->getIntrinsicID()) {
480
254
    // Lifetime markers are supported/ignored.
481
254
    case llvm::Intrinsic::lifetime_start:
482
160
    case llvm::Intrinsic::lifetime_end:
483
160
    // Invariant markers are supported/ignored.
484
160
    case llvm::Intrinsic::invariant_start:
485
160
    case llvm::Intrinsic::invariant_end:
486
160
    // Some misc annotations are supported/ignored.
487
160
    case llvm::Intrinsic::var_annotation:
488
160
    case llvm::Intrinsic::ptr_annotation:
489
160
    case llvm::Intrinsic::annotation:
490
160
    case llvm::Intrinsic::donothing:
491
160
    case llvm::Intrinsic::assume:
492
160
    // Some debug info intrinsics are supported/ignored.
493
160
    case llvm::Intrinsic::dbg_value:
494
160
    case llvm::Intrinsic::dbg_declare:
495
160
      return true;
496
160
    default:
497
254
      break;
498
254
    }
499
35.4k
  }
500
35.2k
  return false;
501
35.4k
}
502
503
bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
504
36.3k
                          Loop *Scope) {
505
36.3k
  if (
!V || 36.3k
!SE->isSCEVable(V->getType())36.3k
)
506
3.92k
    return false;
507
36.3k
508
36.3k
  const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
509
32.4k
  if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
510
32.4k
    
if (32.4k
!isa<SCEVCouldNotCompute>(Scev)32.4k
)
511
32.4k
      
if (32.4k
!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS)32.4k
)
512
25.3k
        return true;
513
32.4k
514
7.09k
  return false;
515
36.3k
}
516
517
17.8k
llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {
518
17.8k
  Instruction *UI = dyn_cast<Instruction>(U.getUser());
519
17.8k
  if (!UI)
520
0
    return nullptr;
521
17.8k
522
17.8k
  
if (PHINode *17.8k
PHI17.8k
= dyn_cast<PHINode>(UI))
523
1.83k
    return PHI->getIncomingBlock(U);
524
17.8k
525
15.9k
  return UI->getParent();
526
17.8k
}
527
528
std::tuple<std::vector<const SCEV *>, std::vector<int>>
529
2.62k
polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
530
2.62k
  std::vector<const SCEV *> Subscripts;
531
2.62k
  std::vector<int> Sizes;
532
2.62k
533
2.62k
  Type *Ty = GEP->getPointerOperandType();
534
2.62k
535
2.62k
  bool DroppedFirstDim = false;
536
2.62k
537
5.90k
  for (unsigned i = 1; 
i < GEP->getNumOperands()5.90k
;
i++3.28k
)
{3.39k
538
3.39k
539
3.39k
    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
540
3.39k
541
3.39k
    if (
i == 13.39k
)
{2.62k
542
2.62k
      if (auto *
PtrTy2.62k
= dyn_cast<PointerType>(Ty))
{2.62k
543
2.62k
        Ty = PtrTy->getElementType();
544
2.62k
      } else 
if (auto *0
ArrayTy0
= dyn_cast<ArrayType>(Ty))
{0
545
0
        Ty = ArrayTy->getElementType();
546
0
      } else {
547
0
        Subscripts.clear();
548
0
        Sizes.clear();
549
0
        break;
550
2.62k
      }
551
2.62k
      
if (auto *2.62k
Const2.62k
= dyn_cast<SCEVConstant>(Expr))
552
772
        
if (772
Const->getValue()->isZero()772
)
{561
553
561
          DroppedFirstDim = true;
554
561
          continue;
555
2.62k
        }
556
2.62k
      Subscripts.push_back(Expr);
557
2.62k
      continue;
558
3.39k
    }
559
3.39k
560
3.39k
    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
561
772
    if (
!ArrayTy772
)
{105
562
105
      Subscripts.clear();
563
105
      Sizes.clear();
564
105
      break;
565
772
    }
566
772
567
772
    Subscripts.push_back(Expr);
568
667
    if (
!(DroppedFirstDim && 667
i == 2478
))
569
257
      Sizes.push_back(ArrayTy->getNumElements());
570
667
571
667
    Ty = ArrayTy->getElementType();
572
2.62k
  }
573
2.62k
574
2.62k
  return std::make_tuple(Subscripts, Sizes);
575
2.62k
}
576
577
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
578
13.4k
                                           const BoxedLoopsSetTy &BoxedLoops) {
579
13.5k
  while (BoxedLoops.count(L))
580
46
    L = L->getParentLoop();
581
13.4k
  return L;
582
13.4k
}
583
584
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
585
                                           llvm::LoopInfo &LI,
586
13.4k
                                           const BoxedLoopsSetTy &BoxedLoops) {
587
13.4k
  Loop *L = LI.getLoopFor(BB);
588
13.4k
  return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
589
13.4k
}