Coverage Report

Created: 2017-03-28 09:59

/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
258
                                RegionInfo *RI) {
43
258
  BasicBlock *EnteringBB = R->getEnteringBlock();
44
258
  BasicBlock *Entry = R->getEntry();
45
258
46
258
  // Before (one of):
47
258
  //
48
258
  //                       \    /            //
49
258
  //                      EnteringBB         //
50
258
  //                        |    \------>    //
51
258
  //   \   /                |                //
52
258
  //   Entry <--\         Entry <--\         //
53
258
  //   /   \    /         /   \    /         //
54
258
  //        ....               ....          //
55
258
56
258
  // Create single entry edge if the region has multiple entry edges.
57
258
  if (
!EnteringBB258
)
{8
58
8
    SmallVector<BasicBlock *, 4> Preds;
59
8
    for (BasicBlock *P : predecessors(Entry))
60
18
      
if (18
!R->contains(P)18
)
61
17
        Preds.push_back(P);
62
8
63
8
    BasicBlock *NewEntering =
64
8
        SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
65
8
66
8
    if (
RI8
)
{8
67
8
      // The exit block of predecessing regions must be changed to NewEntering
68
17
      for (BasicBlock *ExitPred : predecessors(NewEntering)) {
69
17
        Region *RegionOfPred = RI->getRegionFor(ExitPred);
70
17
        if (RegionOfPred->getExit() != Entry)
71
15
          continue;
72
17
73
4
        
while (2
!RegionOfPred->isTopLevelRegion() &&4
74
2
               
RegionOfPred->getExit() == Entry2
)
{2
75
2
          RegionOfPred->replaceExit(NewEntering);
76
2
          RegionOfPred = RegionOfPred->getParent();
77
2
        }
78
2
      }
79
8
80
8
      // Make all ancestors use EnteringBB as entry; there might be edges to it
81
8
      Region *AncestorR = R->getParent();
82
8
      RI->setRegionFor(NewEntering, AncestorR);
83
15
      while (
!AncestorR->isTopLevelRegion() && 15
AncestorR->getEntry() == Entry8
)
{7
84
7
        AncestorR->replaceEntry(NewEntering);
85
7
        AncestorR = AncestorR->getParent();
86
7
      }
87
8
    }
88
8
89
8
    EnteringBB = NewEntering;
90
8
  }
91
258
  assert(R->getEnteringBlock() == EnteringBB);
92
258
93
258
  // After:
94
258
  //
95
258
  //    \    /       //
96
258
  //  EnteringBB     //
97
258
  //      |          //
98
258
  //      |          //
99
258
  //    Entry <--\   //
100
258
  //    /   \    /   //
101
258
  //         ....    //
102
258
}
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
258
                               RegionInfo *RI) {
107
258
  BasicBlock *ExitBB = R->getExit();
108
258
  BasicBlock *ExitingBB = R->getExitingBlock();
109
258
110
258
  // Before:
111
258
  //
112
258
  //   (Region)   ______/  //
113
258
  //      \  |   /         //
114
258
  //       ExitBB          //
115
258
  //       /    \          //
116
258
117
258
  if (
!ExitingBB258
)
{55
118
55
    SmallVector<BasicBlock *, 4> Preds;
119
55
    for (BasicBlock *P : predecessors(ExitBB))
120
133
      
if (133
R->contains(P)133
)
121
116
        Preds.push_back(P);
122
55
123
55
    //  Preds[0] Preds[1]      otherBB //
124
55
    //         \  |  ________/         //
125
55
    //          \ | /                  //
126
55
    //           BB                    //
127
55
    ExitingBB =
128
55
        SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
129
55
    // Preds[0] Preds[1]      otherBB  //
130
55
    //        \  /           /         //
131
55
    // BB.region_exiting    /          //
132
55
    //                  \  /           //
133
55
    //                   BB            //
134
55
135
55
    if (RI)
136
55
      RI->setRegionFor(ExitingBB, R);
137
55
138
55
    // Change the exit of nested regions, but not the region itself,
139
55
    R->replaceExitRecursive(ExitingBB);
140
55
    R->replaceExit(ExitBB);
141
55
  }
142
258
  assert(ExitingBB == R->getExitingBlock());
143
258
144
258
  // After:
145
258
  //
146
258
  //     \   /                //
147
258
  //    ExitingBB     _____/  //
148
258
  //          \      /        //
149
258
  //           ExitBB         //
150
258
  //           /    \         //
151
258
}
152
153
void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
154
258
                           RegionInfo *RI) {
155
258
  assert(R && !R->isTopLevelRegion());
156
258
  assert(!RI || RI == R->getRegionInfo());
157
258
  assert((!RI || DT) &&
158
258
         "RegionInfo requires DominatorTree to be updated as well");
159
258
160
258
  simplifyRegionEntry(R, DT, LI, RI);
161
258
  simplifyRegionExit(R, DT, LI, RI);
162
258
  assert(R->isSimple());
163
258
}
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
0
  }
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
13
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
198
13
  // Find first non-alloca instruction. Every basic block has a non-alloc
199
13
  // instruction, as every well formed basic block has a terminator.
200
13
  BasicBlock::iterator I = EntryBlock->begin();
201
13
  while (isa<AllocaInst>(I))
202
0
    ++I;
203
13
204
13
  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
205
13
  auto *DT = DTWP ? 
&DTWP->getDomTree()13
:
nullptr0
;
206
13
  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
207
13
  auto *LI = LIWP ? 
&LIWP->getLoopInfo()13
:
nullptr0
;
208
13
  RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
209
13
  RegionInfo *RI = RIP ? 
&RIP->getRegionInfo()0
:
nullptr13
;
210
13
211
13
  // splitBlock updates DT, LI and RI.
212
13
  splitBlock(EntryBlock, &*I, DT, LI, RI);
213
13
}
214
215
/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
216
/// instruction but just use it, if it is referenced as a SCEVUnknown. We want
217
/// however to generate new code if the instruction is in the analyzed region
218
/// and we generate code outside/in front of that region. Hence, we generate the
219
/// code for the SDiv/SRem operands in front of the analyzed region and then
220
/// create a new SDiv/SRem operation there too.
221
struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
222
  friend struct SCEVVisitor<ScopExpander, const SCEV *>;
223
224
  explicit ScopExpander(const Region &R, ScalarEvolution &SE,
225
                        const DataLayout &DL, const char *Name, ValueMapT *VMap,
226
                        BasicBlock *RTCBB)
227
      : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
228
919
        VMap(VMap), RTCBB(RTCBB) {}
229
230
926
  Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
231
926
    // If we generate code in the region we will immediately fall back to the
232
926
    // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
233
926
    // needed replace them by copies computed in the entering block.
234
926
    if (!R.contains(I))
235
926
      E = visit(E);
236
926
    return Expander.expandCodeFor(E, Ty, I);
237
926
  }
238
239
private:
240
  SCEVExpander Expander;
241
  ScalarEvolution &SE;
242
  const char *Name;
243
  const Region &R;
244
  ValueMapT *VMap;
245
  BasicBlock *RTCBB;
246
247
  const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
248
1.29k
                               Instruction *IP) {
249
1.29k
    if (
!Inst || 1.29k
!R.contains(Inst)468
)
250
1.29k
      return E;
251
1.29k
252
1
    assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
253
1
           !isa<PHINode>(Inst));
254
1
255
1
    auto *InstClone = Inst->clone();
256
1
    for (auto &Op : Inst->operands()) {
257
1
      assert(SE.isSCEVable(Op->getType()));
258
1
      auto *OpSCEV = SE.getSCEV(Op);
259
1
      auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
260
1
      InstClone->replaceUsesOfWith(Op, OpClone);
261
1
    }
262
1
263
1
    InstClone->setName(Name + Inst->getName());
264
1
    InstClone->insertBefore(IP);
265
1
    return SE.getSCEV(InstClone);
266
1.29k
  }
267
268
1.33k
  const SCEV *visitUnknown(const SCEVUnknown *E) {
269
1.33k
270
1.33k
    // If a value mapping was given try if the underlying value is remapped.
271
1.30k
    Value *NewVal = VMap ? 
VMap->lookup(E->getValue())1.30k
:
nullptr32
;
272
1.33k
    if (
NewVal1.33k
)
{38
273
38
      auto *NewE = SE.getSCEV(NewVal);
274
38
275
38
      // While the mapped value might be different the SCEV representation might
276
38
      // not be. To this end we will check before we go into recursion here.
277
38
      if (E != NewE)
278
35
        return visit(NewE);
279
38
    }
280
1.33k
281
1.29k
    Instruction *Inst = dyn_cast<Instruction>(E->getValue());
282
1.29k
    Instruction *IP;
283
1.29k
    if (
Inst && 1.29k
!R.contains(Inst)471
)
284
470
      IP = Inst;
285
828
    else 
if (828
Inst && 828
RTCBB->getParent() == Inst->getFunction()1
)
286
1
      IP = RTCBB->getTerminator();
287
828
    else
288
827
      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
289
1.29k
290
1.29k
    if (
!Inst || 1.29k
(Inst->getOpcode() != Instruction::SRem &&471
291
471
                  Inst->getOpcode() != Instruction::SDiv))
292
1.29k
      return visitGenericInst(E, Inst, IP);
293
1.29k
294
3
    const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
295
3
    const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
296
3
297
3
    if (!SE.isKnownNonZero(RHSScev))
298
1
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
299
3
300
3
    Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
301
3
    Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
302
3
303
3
    Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
304
3
                                  LHS, RHS, Inst->getName() + Name, IP);
305
3
    return SE.getSCEV(Inst);
306
1.29k
  }
307
308
  /// The following functions will just traverse the SCEV and rebuild it with
309
  /// the new operands returned by the traversal.
310
  ///
311
  ///{
312
619
  const SCEV *visitConstant(const SCEVConstant *E) { return E; }
313
80
  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
314
80
    return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
315
80
  }
316
8
  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
317
8
    return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
318
8
  }
319
41
  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
320
41
    return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
321
41
  }
322
11
  const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
323
11
    auto *RHSScev = visit(E->getRHS());
324
11
    if (!SE.isKnownNonZero(RHSScev))
325
8
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
326
11
    return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
327
11
  }
328
425
  const SCEV *visitAddExpr(const SCEVAddExpr *E) {
329
425
    SmallVector<const SCEV *, 4> NewOps;
330
425
    for (const SCEV *Op : E->operands())
331
971
      NewOps.push_back(visit(Op));
332
425
    return SE.getAddExpr(NewOps);
333
425
  }
334
365
  const SCEV *visitMulExpr(const SCEVMulExpr *E) {
335
365
    SmallVector<const SCEV *, 4> NewOps;
336
365
    for (const SCEV *Op : E->operands())
337
761
      NewOps.push_back(visit(Op));
338
365
    return SE.getMulExpr(NewOps);
339
365
  }
340
1
  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
341
1
    SmallVector<const SCEV *, 4> NewOps;
342
1
    for (const SCEV *Op : E->operands())
343
2
      NewOps.push_back(visit(Op));
344
1
    return SE.getUMaxExpr(NewOps);
345
1
  }
346
0
  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
347
0
    SmallVector<const SCEV *, 4> NewOps;
348
0
    for (const SCEV *Op : E->operands())
349
0
      NewOps.push_back(visit(Op));
350
0
    return SE.getSMaxExpr(NewOps);
351
0
  }
352
37
  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
353
37
    SmallVector<const SCEV *, 4> NewOps;
354
37
    for (const SCEV *Op : E->operands())
355
74
      NewOps.push_back(visit(Op));
356
37
    return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
357
37
  }
358
  ///}
359
};
360
361
Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
362
                            const char *Name, const SCEV *E, Type *Ty,
363
                            Instruction *IP, ValueMapT *VMap,
364
919
                            BasicBlock *RTCBB) {
365
919
  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
366
919
  return Expander.expandCodeFor(E, Ty, IP);
367
919
}
368
369
bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
370
78.9k
                         const DominatorTree &DT) {
371
78.9k
  if (!PollyAllowErrorBlocks)
372
0
    return false;
373
78.9k
374
78.9k
  
if (78.9k
isa<UnreachableInst>(BB.getTerminator())78.9k
)
375
0
    return true;
376
78.9k
377
78.9k
  
if (78.9k
LI.isLoopHeader(&BB)78.9k
)
378
29.9k
    return false;
379
78.9k
380
78.9k
  // Basic blocks that are always executed are not considered error blocks,
381
78.9k
  // as their execution can not be a rare event.
382
49.0k
  bool DominatesAllPredecessors = true;
383
49.0k
  for (auto Pred : predecessors(R.getExit()))
384
72.1k
    
if (72.1k
R.contains(Pred) && 72.1k
!DT.dominates(&BB, Pred)67.3k
)
385
32.5k
      DominatesAllPredecessors = false;
386
49.0k
387
49.0k
  if (DominatesAllPredecessors)
388
19.0k
    return false;
389
49.0k
390
49.0k
  // FIXME: This is a simple heuristic to determine if the load is executed
391
49.0k
  //        in a conditional. However, we actually would need the control
392
49.0k
  //        condition, i.e., the post dominance frontier. Alternatively we
393
49.0k
  //        could walk up the dominance tree until we find a block that is
394
49.0k
  //        not post dominated by the load and check if it is a conditional
395
49.0k
  //        or a loop header.
396
29.9k
  auto *DTNode = DT.getNode(&BB);
397
29.9k
  auto *IDomBB = DTNode->getIDom()->getBlock();
398
29.9k
  if (LI.isLoopHeader(IDomBB))
399
15.8k
    return false;
400
29.9k
401
14.0k
  for (Instruction &Inst : BB)
402
41.6k
    
if (CallInst *41.6k
CI41.6k
= dyn_cast<CallInst>(&Inst))
{300
403
300
      if (isIgnoredIntrinsic(CI))
404
57
        return false;
405
300
406
243
      
if (243
!CI->doesNotAccessMemory()243
)
407
243
        return true;
408
0
      
if (0
CI->doesNotReturn()0
)
409
0
        return true;
410
0
    }
411
14.0k
412
13.7k
  return false;
413
14.0k
}
414
415
26.0k
Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
416
26.0k
  if (BranchInst *
BR26.0k
= dyn_cast<BranchInst>(TI))
{25.9k
417
25.9k
    if (BR->isUnconditional())
418
11.7k
      return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
419
25.9k
420
14.1k
    return BR->getCondition();
421
25.9k
  }
422
26.0k
423
66
  
if (SwitchInst *66
SI66
= dyn_cast<SwitchInst>(TI))
424
66
    return SI->getCondition();
425
66
426
0
  return nullptr;
427
66
}
428
429
bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
430
3.63k
                            ScalarEvolution &SE, const DominatorTree &DT) {
431
3.63k
  Loop *L = LI.getLoopFor(LInst->getParent());
432
3.63k
  auto *Ptr = LInst->getPointerOperand();
433
3.63k
  const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
434
4.06k
  while (
L && 4.06k
R.contains(L)972
)
{447
435
447
    if (!SE.isLoopInvariant(PtrSCEV, L))
436
17
      return false;
437
430
    L = L->getParentLoop();
438
430
  }
439
3.63k
440
23.5k
  
for (auto *User : Ptr->users()) 3.61k
{23.5k
441
23.5k
    auto *UserI = dyn_cast<Instruction>(User);
442
23.5k
    if (
!UserI || 23.5k
!R.contains(UserI)23.5k
)
443
3.10k
      continue;
444
20.4k
    
if (20.4k
!UserI->mayWriteToMemory()20.4k
)
445
19.7k
      continue;
446
20.4k
447
612
    auto &BB = *UserI->getParent();
448
612
    if (DT.dominates(&BB, LInst->getParent()))
449
121
      return false;
450
612
451
491
    bool DominatesAllPredecessors = true;
452
491
    for (auto Pred : predecessors(R.getExit()))
453
974
      
if (974
R.contains(Pred) && 974
!DT.dominates(&BB, Pred)974
)
454
940
        DominatesAllPredecessors = false;
455
491
456
491
    if (!DominatesAllPredecessors)
457
491
      continue;
458
491
459
0
    return false;
460
491
  }
461
3.61k
462
3.49k
  return true;
463
3.61k
}
464
465
18.0k
bool polly::isIgnoredIntrinsic(const Value *V) {
466
18.0k
  if (auto *
IT18.0k
= dyn_cast<IntrinsicInst>(V))
{190
467
190
    switch (IT->getIntrinsicID()) {
468
190
    // Lifetime markers are supported/ignored.
469
130
    case llvm::Intrinsic::lifetime_start:
470
130
    case llvm::Intrinsic::lifetime_end:
471
130
    // Invariant markers are supported/ignored.
472
130
    case llvm::Intrinsic::invariant_start:
473
130
    case llvm::Intrinsic::invariant_end:
474
130
    // Some misc annotations are supported/ignored.
475
130
    case llvm::Intrinsic::var_annotation:
476
130
    case llvm::Intrinsic::ptr_annotation:
477
130
    case llvm::Intrinsic::annotation:
478
130
    case llvm::Intrinsic::donothing:
479
130
    case llvm::Intrinsic::assume:
480
130
    case llvm::Intrinsic::expect:
481
130
    // Some debug info intrisics are supported/ignored.
482
130
    case llvm::Intrinsic::dbg_value:
483
130
    case llvm::Intrinsic::dbg_declare:
484
130
      return true;
485
60
    default:
486
60
      break;
487
190
    }
488
190
  }
489
17.9k
  return false;
490
18.0k
}
491
492
bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
493
19.6k
                          Loop *Scope) {
494
19.6k
  if (
!V || 19.6k
!SE->isSCEVable(V->getType())19.6k
)
495
1.70k
    return false;
496
19.6k
497
17.9k
  
if (const SCEV *17.9k
Scev17.9k
= SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
498
17.9k
    
if (17.9k
!isa<SCEVCouldNotCompute>(Scev)17.9k
)
499
17.9k
      
if (17.9k
!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false)17.9k
)
500
14.4k
        return true;
501
17.9k
502
3.54k
  return false;
503
17.9k
}
504
505
15.2k
llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
506
15.2k
  Instruction *UI = dyn_cast<Instruction>(U.getUser());
507
15.2k
  if (!UI)
508
0
    return nullptr;
509
15.2k
510
15.2k
  
if (PHINode *15.2k
PHI15.2k
= dyn_cast<PHINode>(UI))
511
1.54k
    return PHI->getIncomingBlock(U);
512
15.2k
513
13.7k
  return UI->getParent();
514
15.2k
}
515
516
std::tuple<std::vector<const SCEV *>, std::vector<int>>
517
2.24k
polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
518
2.24k
  std::vector<const SCEV *> Subscripts;
519
2.24k
  std::vector<int> Sizes;
520
2.24k
521
2.24k
  Type *Ty = GEP->getPointerOperandType();
522
2.24k
523
2.24k
  bool DroppedFirstDim = false;
524
2.24k
525
5.08k
  for (unsigned i = 1; 
i < GEP->getNumOperands()5.08k
;
i++2.84k
)
{2.94k
526
2.94k
527
2.94k
    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
528
2.94k
529
2.94k
    if (
i == 12.94k
)
{2.24k
530
2.24k
      if (auto *
PtrTy2.24k
= dyn_cast<PointerType>(Ty))
{2.24k
531
2.24k
        Ty = PtrTy->getElementType();
532
0
      } else 
if (auto *0
ArrayTy0
= dyn_cast<ArrayType>(Ty))
{0
533
0
        Ty = ArrayTy->getElementType();
534
0
      } else {
535
0
        Subscripts.clear();
536
0
        Sizes.clear();
537
0
        break;
538
0
      }
539
2.24k
      
if (auto *2.24k
Const2.24k
= dyn_cast<SCEVConstant>(Expr))
540
753
        
if (753
Const->getValue()->isZero()753
)
{549
541
549
          DroppedFirstDim = true;
542
549
          continue;
543
549
        }
544
1.69k
      Subscripts.push_back(Expr);
545
1.69k
      continue;
546
2.24k
    }
547
2.94k
548
705
    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
549
705
    if (
!ArrayTy705
)
{102
550
102
      Subscripts.clear();
551
102
      Sizes.clear();
552
102
      break;
553
102
    }
554
705
555
603
    Subscripts.push_back(Expr);
556
603
    if (
!(DroppedFirstDim && 603
i == 2471
))
557
200
      Sizes.push_back(ArrayTy->getNumElements());
558
603
559
603
    Ty = ArrayTy->getElementType();
560
603
  }
561
2.24k
562
2.24k
  return std::make_tuple(Subscripts, Sizes);
563
2.24k
}