Coverage Report

Created: 2019-02-20 07:29

/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
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// Small functions that help with Scop and LLVM-IR.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "polly/Support/ScopHelper.h"
14
#include "polly/Options.h"
15
#include "polly/ScopInfo.h"
16
#include "polly/Support/SCEVValidator.h"
17
#include "llvm/Analysis/LoopInfo.h"
18
#include "llvm/Analysis/RegionInfo.h"
19
#include "llvm/Analysis/RegionInfoImpl.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
293
                                RegionInfo *RI) {
50
293
  BasicBlock *EnteringBB = R->getEnteringBlock();
51
293
  BasicBlock *Entry = R->getEntry();
52
293
53
293
  // Before (one of):
54
293
  //
55
293
  //                       \    /            //
56
293
  //                      EnteringBB         //
57
293
  //                        |    \------>    //
58
293
  //   \   /                |                //
59
293
  //   Entry <--\         Entry <--\         //
60
293
  //   /   \    /         /   \    /         //
61
293
  //        ....               ....          //
62
293
63
293
  // Create single entry edge if the region has multiple entry edges.
64
293
  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
293
  assert(R->getEnteringBlock() == EnteringBB);
99
293
100
293
  // After:
101
293
  //
102
293
  //    \    /       //
103
293
  //  EnteringBB     //
104
293
  //      |          //
105
293
  //      |          //
106
293
  //    Entry <--\   //
107
293
  //    /   \    /   //
108
293
  //         ....    //
109
293
}
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
293
                               RegionInfo *RI) {
114
293
  BasicBlock *ExitBB = R->getExit();
115
293
  BasicBlock *ExitingBB = R->getExitingBlock();
116
293
117
293
  // Before:
118
293
  //
119
293
  //   (Region)   ______/  //
120
293
  //      \  |   /         //
121
293
  //       ExitBB          //
122
293
  //       /    \          //
123
293
124
293
  if (!ExitingBB) {
125
59
    SmallVector<BasicBlock *, 4> Preds;
126
59
    for (BasicBlock *P : predecessors(ExitBB))
127
136
      if (R->contains(P))
128
120
        Preds.push_back(P);
129
59
130
59
    //  Preds[0] Preds[1]      otherBB //
131
59
    //         \  |  ________/         //
132
59
    //          \ | /                  //
133
59
    //           BB                    //
134
59
    ExitingBB =
135
59
        SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
136
59
    // Preds[0] Preds[1]      otherBB  //
137
59
    //        \  /           /         //
138
59
    // BB.region_exiting    /          //
139
59
    //                  \  /           //
140
59
    //                   BB            //
141
59
142
59
    if (RI)
143
59
      RI->setRegionFor(ExitingBB, R);
144
59
145
59
    // Change the exit of nested regions, but not the region itself,
146
59
    R->replaceExitRecursive(ExitingBB);
147
59
    R->replaceExit(ExitBB);
148
59
  }
149
293
  assert(ExitingBB == R->getExitingBlock());
150
293
151
293
  // After:
152
293
  //
153
293
  //     \   /                //
154
293
  //    ExitingBB     _____/  //
155
293
  //          \      /        //
156
293
  //           ExitBB         //
157
293
  //           /    \         //
158
293
}
159
160
void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
161
293
                           RegionInfo *RI) {
162
293
  assert(R && !R->isTopLevelRegion());
163
293
  assert(!RI || RI == R->getRegionInfo());
164
293
  assert((!RI || DT) &&
165
293
         "RegionInfo requires DominatorTree to be updated as well");
166
293
167
293
  simplifyRegionEntry(R, DT, LI, RI);
168
293
  simplifyRegionExit(R, DT, LI, RI);
169
293
  assert(R->isSimple());
170
293
}
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.13k
        VMap(VMap), RTCBB(RTCBB) {}
242
243
1.13k
  Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
244
1.13k
    // If we generate code in the region we will immediately fall back to the
245
1.13k
    // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
246
1.13k
    // needed replace them by copies computed in the entering block.
247
1.13k
    if (!R.contains(I))
248
1.13k
      E = visit(E);
249
1.13k
    return Expander.expandCodeFor(E, Ty, I);
250
1.13k
  }
251
252
3.80k
  const SCEV *visit(const SCEV *E) {
253
3.80k
    // Cache the expansion results for intermediate SCEV expressions. A SCEV
254
3.80k
    // expression can refer to an operand multiple times (e.g. "x*x), so
255
3.80k
    // a naive visitor takes exponential time.
256
3.80k
    if (SCEVCache.count(E))
257
53
      return SCEVCache[E];
258
3.75k
    const SCEV *Result = SCEVVisitor::visit(E);
259
3.75k
    SCEVCache[E] = Result;
260
3.75k
    return Result;
261
3.75k
  }
262
263
private:
264
  SCEVExpander Expander;
265
  ScalarEvolution &SE;
266
  const char *Name;
267
  const Region &R;
268
  ValueMapT *VMap;
269
  BasicBlock *RTCBB;
270
  DenseMap<const SCEV *, const SCEV *> SCEVCache;
271
272
  const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
273
1.50k
                               Instruction *IP) {
274
1.50k
    if (!Inst || 
!R.contains(Inst)634
)
275
1.50k
      return E;
276
2
277
2
    assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
278
2
           !isa<PHINode>(Inst));
279
2
280
2
    auto *InstClone = Inst->clone();
281
2
    for (auto &Op : Inst->operands()) {
282
2
      assert(SE.isSCEVable(Op->getType()));
283
2
      auto *OpSCEV = SE.getSCEV(Op);
284
2
      auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);
285
2
      InstClone->replaceUsesOfWith(Op, OpClone);
286
2
    }
287
2
288
2
    InstClone->setName(Name + Inst->getName());
289
2
    InstClone->insertBefore(IP);
290
2
    return SE.getSCEV(InstClone);
291
2
  }
292
293
1.58k
  const SCEV *visitUnknown(const SCEVUnknown *E) {
294
1.58k
295
1.58k
    // If a value mapping was given try if the underlying value is remapped.
296
1.58k
    Value *NewVal = VMap ? 
VMap->lookup(E->getValue())1.57k
:
nullptr16
;
297
1.58k
    if (NewVal) {
298
82
      auto *NewE = SE.getSCEV(NewVal);
299
82
300
82
      // While the mapped value might be different the SCEV representation might
301
82
      // not be. To this end we will check before we go into recursion here.
302
82
      if (E != NewE)
303
79
        return visit(NewE);
304
1.50k
    }
305
1.50k
306
1.50k
    Instruction *Inst = dyn_cast<Instruction>(E->getValue());
307
1.50k
    Instruction *IP;
308
1.50k
    if (Inst && 
!R.contains(Inst)635
)
309
633
      IP = Inst;
310
874
    else if (Inst && 
RTCBB->getParent() == Inst->getFunction()2
)
311
2
      IP = RTCBB->getTerminator();
312
872
    else
313
872
      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
314
1.50k
315
1.50k
    if (!Inst || 
(635
Inst->getOpcode() != Instruction::SRem635
&&
316
635
                  Inst->getOpcode() != Instruction::SDiv))
317
1.50k
      return visitGenericInst(E, Inst, IP);
318
1
319
1
    const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
320
1
    const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
321
1
322
1
    if (!SE.isKnownNonZero(RHSScev))
323
1
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
324
1
325
1
    Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);
326
1
    Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);
327
1
328
1
    Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),
329
1
                                  LHS, RHS, Inst->getName() + Name, IP);
330
1
    return SE.getSCEV(Inst);
331
1
  }
332
333
  /// The following functions will just traverse the SCEV and rebuild it with
334
  /// the new operands returned by the traversal.
335
  ///
336
  ///{
337
920
  const SCEV *visitConstant(const SCEVConstant *E) { return E; }
338
74
  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
339
74
    return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
340
74
  }
341
22
  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {
342
22
    return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType());
343
22
  }
344
36
  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {
345
36
    return SE.getSignExtendExpr(visit(E->getOperand()), E->getType());
346
36
  }
347
13
  const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {
348
13
    auto *RHSScev = visit(E->getRHS());
349
13
    if (!SE.isKnownNonZero(RHSScev))
350
8
      RHSScev = SE.getUMaxExpr(RHSScev, SE.getConstant(E->getType(), 1));
351
13
    return SE.getUDivExpr(visit(E->getLHS()), RHSScev);
352
13
  }
353
503
  const SCEV *visitAddExpr(const SCEVAddExpr *E) {
354
503
    SmallVector<const SCEV *, 4> NewOps;
355
503
    for (const SCEV *Op : E->operands())
356
1.20k
      NewOps.push_back(visit(Op));
357
503
    return SE.getAddExpr(NewOps);
358
503
  }
359
559
  const SCEV *visitMulExpr(const SCEVMulExpr *E) {
360
559
    SmallVector<const SCEV *, 4> NewOps;
361
559
    for (const SCEV *Op : E->operands())
362
1.15k
      NewOps.push_back(visit(Op));
363
559
    return SE.getMulExpr(NewOps);
364
559
  }
365
2
  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {
366
2
    SmallVector<const SCEV *, 4> NewOps;
367
2
    for (const SCEV *Op : E->operands())
368
4
      NewOps.push_back(visit(Op));
369
2
    return SE.getUMaxExpr(NewOps);
370
2
  }
371
0
  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {
372
0
    SmallVector<const SCEV *, 4> NewOps;
373
0
    for (const SCEV *Op : E->operands())
374
0
      NewOps.push_back(visit(Op));
375
0
    return SE.getSMaxExpr(NewOps);
376
0
  }
377
38
  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
378
38
    SmallVector<const SCEV *, 4> NewOps;
379
38
    for (const SCEV *Op : E->operands())
380
76
      NewOps.push_back(visit(Op));
381
38
    return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
382
38
  }
383
  ///}
384
};
385
386
Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
387
                            const char *Name, const SCEV *E, Type *Ty,
388
                            Instruction *IP, ValueMapT *VMap,
389
1.13k
                            BasicBlock *RTCBB) {
390
1.13k
  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
391
1.13k
  return Expander.expandCodeFor(E, Ty, IP);
392
1.13k
}
393
394
bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
395
104k
                         const DominatorTree &DT) {
396
104k
  if (!PollyAllowErrorBlocks)
397
0
    return false;
398
104k
399
104k
  if (isa<UnreachableInst>(BB.getTerminator()))
400
0
    return true;
401
104k
402
104k
  if (LI.isLoopHeader(&BB))
403
40.2k
    return false;
404
64.3k
405
64.3k
  // Basic blocks that are always executed are not considered error blocks,
406
64.3k
  // as their execution can not be a rare event.
407
64.3k
  bool DominatesAllPredecessors = true;
408
64.3k
  if (R.isTopLevelRegion()) {
409
117
    for (BasicBlock &I : *R.getEntry()->getParent())
410
634
      if (isa<ReturnInst>(I.getTerminator()) && 
!DT.dominates(&BB, &I)117
)
411
14
        DominatesAllPredecessors = false;
412
64.2k
  } else {
413
64.2k
    for (auto Pred : predecessors(R.getExit()))
414
98.3k
      if (R.contains(Pred) && 
!DT.dominates(&BB, Pred)92.5k
)
415
47.2k
        DominatesAllPredecessors = false;
416
64.2k
  }
417
64.3k
418
64.3k
  if (DominatesAllPredecessors)
419
22.8k
    return false;
420
41.4k
421
41.4k
  for (Instruction &Inst : BB)
422
371k
    if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
423
1.20k
      if (isDebugCall(CI))
424
8
        continue;
425
1.19k
426
1.19k
      if (isIgnoredIntrinsic(CI))
427
249
        continue;
428
946
429
946
      // memset, memcpy and memmove are modeled intrinsics.
430
946
      if (isa<MemSetInst>(CI) || 
isa<MemTransferInst>(CI)885
)
431
129
        continue;
432
817
433
817
      if (!CI->doesNotAccessMemory())
434
348
        return true;
435
469
      if (CI->doesNotReturn())
436
0
        return true;
437
469
    }
438
41.4k
439
41.4k
  
return false41.1k
;
440
41.4k
}
441
442
32.1k
Value *polly::getConditionFromTerminator(Instruction *TI) {
443
32.1k
  if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
444
32.0k
    if (BR->isUnconditional())
445
14.6k
      return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
446
17.4k
447
17.4k
    return BR->getCondition();
448
17.4k
  }
449
56
450
56
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
451
56
    return SI->getCondition();
452
0
453
0
  return nullptr;
454
0
}
455
456
static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
457
944
                            ScalarEvolution &SE) {
458
1.22k
  for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {
459
1.22k
    const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);
460
1.22k
    Loop *OuterLoop = R.outermostLoopInRegion(L);
461
1.22k
    if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))
462
69
      return true;
463
1.22k
  }
464
944
  
return false875
;
465
944
}
466
467
bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
468
                            ScalarEvolution &SE, const DominatorTree &DT,
469
3.02k
                            const InvariantLoadsSetTy &KnownInvariantLoads) {
470
3.02k
  Loop *L = LI.getLoopFor(LInst->getParent());
471
3.02k
  auto *Ptr = LInst->getPointerOperand();
472
3.02k
473
3.02k
  // A LoadInst is hoistable if the address it is loading from is also
474
3.02k
  // invariant; in this case: another invariant load (whether that address
475
3.02k
  // is also not written to has to be checked separately)
476
3.02k
  // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst
477
3.02k
  // pattern generated by the Chapel frontend, but generally this applies
478
3.02k
  // for any chain of instruction that does not also depend on any
479
3.02k
  // induction variable
480
3.02k
  if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) {
481
944
    if (!hasVariantIndex(GepInst, L, R, SE)) {
482
875
      if (auto *DecidingLoad =
483
273
              dyn_cast<LoadInst>(GepInst->getPointerOperand())) {
484
273
        if (KnownInvariantLoads.count(DecidingLoad))
485
179
          return true;
486
2.84k
      }
487
875
    }
488
944
  }
489
2.84k
490
2.84k
  const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
491
3.19k
  while (L && 
R.contains(L)715
) {
492
369
    if (!SE.isLoopInvariant(PtrSCEV, L))
493
19
      return false;
494
350
    L = L->getParentLoop();
495
350
  }
496
2.84k
497
21.3k
  
for (auto *User : Ptr->users())2.82k
{
498
21.3k
    auto *UserI = dyn_cast<Instruction>(User);
499
21.3k
    if (!UserI || !R.contains(UserI))
500
3.06k
      continue;
501
18.2k
    if (!UserI->mayWriteToMemory())
502
17.8k
      continue;
503
396
504
396
    auto &BB = *UserI->getParent();
505
396
    if (DT.dominates(&BB, LInst->getParent()))
506
122
      return false;
507
274
508
274
    bool DominatesAllPredecessors = true;
509
274
    if (R.isTopLevelRegion()) {
510
1
      for (BasicBlock &I : *R.getEntry()->getParent())
511
5
        if (isa<ReturnInst>(I.getTerminator()) && 
!DT.dominates(&BB, &I)1
)
512
1
          DominatesAllPredecessors = false;
513
273
    } else {
514
273
      for (auto Pred : predecessors(R.getExit()))
515
532
        if (R.contains(Pred) && !DT.dominates(&BB, Pred))
516
498
          DominatesAllPredecessors = false;
517
273
    }
518
274
519
274
    if (!DominatesAllPredecessors)
520
274
      continue;
521
0
522
0
    return false;
523
0
  }
524
2.82k
525
2.82k
  
return true2.70k
;
526
2.82k
}
527
528
17.7k
bool polly::isIgnoredIntrinsic(const Value *V) {
529
17.7k
  if (auto *IT = dyn_cast<IntrinsicInst>(V)) {
530
621
    switch (IT->getIntrinsicID()) {
531
621
    // Lifetime markers are supported/ignored.
532
621
    case llvm::Intrinsic::lifetime_start:
533
307
    case llvm::Intrinsic::lifetime_end:
534
307
    // Invariant markers are supported/ignored.
535
307
    case llvm::Intrinsic::invariant_start:
536
307
    case llvm::Intrinsic::invariant_end:
537
307
    // Some misc annotations are supported/ignored.
538
307
    case llvm::Intrinsic::var_annotation:
539
307
    case llvm::Intrinsic::ptr_annotation:
540
307
    case llvm::Intrinsic::annotation:
541
307
    case llvm::Intrinsic::donothing:
542
307
    case llvm::Intrinsic::assume:
543
307
    // Some debug info intrinsics are supported/ignored.
544
307
    case llvm::Intrinsic::dbg_value:
545
307
    case llvm::Intrinsic::dbg_declare:
546
307
      return true;
547
314
    default:
548
314
      break;
549
17.4k
    }
550
17.4k
  }
551
17.4k
  return false;
552
17.4k
}
553
554
bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
555
28.0k
                          Loop *Scope) {
556
28.0k
  if (!V || !SE->isSCEVable(V->getType()))
557
4.40k
    return false;
558
23.6k
559
23.6k
  const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
560
23.6k
  if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
561
23.6k
    if (!isa<SCEVCouldNotCompute>(Scev))
562
23.6k
      if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS))
563
16.1k
        return true;
564
7.52k
565
7.52k
  return false;
566
7.52k
}
567
568
18.9k
llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {
569
18.9k
  Instruction *UI = dyn_cast<Instruction>(U.getUser());
570
18.9k
  if (!UI)
571
0
    return nullptr;
572
18.9k
573
18.9k
  if (PHINode *PHI = dyn_cast<PHINode>(UI))
574
2.03k
    return PHI->getIncomingBlock(U);
575
16.9k
576
16.9k
  return UI->getParent();
577
16.9k
}
578
579
std::tuple<std::vector<const SCEV *>, std::vector<int>>
580
2.74k
polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
581
2.74k
  std::vector<const SCEV *> Subscripts;
582
2.74k
  std::vector<int> Sizes;
583
2.74k
584
2.74k
  Type *Ty = GEP->getPointerOperandType();
585
2.74k
586
2.74k
  bool DroppedFirstDim = false;
587
2.74k
588
6.17k
  for (unsigned i = 1; i < GEP->getNumOperands(); 
i++3.42k
) {
589
3.54k
590
3.54k
    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
591
3.54k
592
3.54k
    if (i == 1) {
593
2.74k
      if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
594
2.74k
        Ty = PtrTy->getElementType();
595
2.74k
      } else 
if (auto *0
ArrayTy0
= dyn_cast<ArrayType>(Ty)) {
596
0
        Ty = ArrayTy->getElementType();
597
0
      } else {
598
0
        Subscripts.clear();
599
0
        Sizes.clear();
600
0
        break;
601
0
      }
602
2.74k
      if (auto *Const = dyn_cast<SCEVConstant>(Expr))
603
801
        if (Const->getValue()->isZero()) {
604
588
          DroppedFirstDim = true;
605
588
          continue;
606
588
        }
607
2.15k
      Subscripts.push_back(Expr);
608
2.15k
      continue;
609
2.15k
    }
610
798
611
798
    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
612
798
    if (!ArrayTy) {
613
113
      Subscripts.clear();
614
113
      Sizes.clear();
615
113
      break;
616
113
    }
617
685
618
685
    Subscripts.push_back(Expr);
619
685
    if (!(DroppedFirstDim && 
i == 2494
))
620
261
      Sizes.push_back(ArrayTy->getNumElements());
621
685
622
685
    Ty = ArrayTy->getElementType();
623
685
  }
624
2.74k
625
2.74k
  return std::make_tuple(Subscripts, Sizes);
626
2.74k
}
627
628
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
629
14.3k
                                           const BoxedLoopsSetTy &BoxedLoops) {
630
14.3k
  while (BoxedLoops.count(L))
631
42
    L = L->getParentLoop();
632
14.3k
  return L;
633
14.3k
}
634
635
llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,
636
                                           llvm::LoopInfo &LI,
637
14.3k
                                           const BoxedLoopsSetTy &BoxedLoops) {
638
14.3k
  Loop *L = LI.getLoopFor(BB);
639
14.3k
  return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
640
14.3k
}
641
642
1.27k
bool polly::isDebugCall(Instruction *Inst) {
643
1.27k
  auto *CI = dyn_cast<CallInst>(Inst);
644
1.27k
  if (!CI)
645
1
    return false;
646
1.27k
647
1.27k
  Function *CF = CI->getCalledFunction();
648
1.27k
  if (!CF)
649
5
    return false;
650
1.26k
651
1.26k
  return std::find(DebugFunctions.begin(), DebugFunctions.end(),
652
1.26k
                   CF->getName()) != DebugFunctions.end();
653
1.26k
}
654
655
0
static bool hasDebugCall(BasicBlock *BB) {
656
0
  for (Instruction &Inst : *BB) {
657
0
    if (isDebugCall(&Inst))
658
0
      return true;
659
0
  }
660
0
  return false;
661
0
}
662
663
11.1k
bool polly::hasDebugCall(ScopStmt *Stmt) {
664
11.1k
  // Quick skip if no debug functions have been defined.
665
11.1k
  if (DebugFunctions.empty())
666
11.1k
    return false;
667
7
668
7
  if (!Stmt)
669
0
    return false;
670
7
671
7
  for (Instruction *Inst : Stmt->getInstructions())
672
3
    if (isDebugCall(Inst))
673
2
      return true;
674
7
675
7
  
if (5
Stmt->isRegionStmt()5
) {
676
0
    for (BasicBlock *RBB : Stmt->getRegion()->blocks())
677
0
      if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB))
678
0
        return true;
679
0
  }
680
5
681
5
  return false;
682
5
}