Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/LoopInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
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
// This file defines the LoopInfo class that is used to identify natural loops
10
// and determine the loop depth of various nodes of the CFG.  Note that the
11
// loops identified may actually be several natural loops that share the same
12
// header node... not just a single natural loop.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/Analysis/LoopInfo.h"
17
#include "llvm/ADT/DepthFirstIterator.h"
18
#include "llvm/ADT/ScopeExit.h"
19
#include "llvm/ADT/SmallPtrSet.h"
20
#include "llvm/Analysis/IVDescriptors.h"
21
#include "llvm/Analysis/LoopInfoImpl.h"
22
#include "llvm/Analysis/LoopIterator.h"
23
#include "llvm/Analysis/MemorySSA.h"
24
#include "llvm/Analysis/MemorySSAUpdater.h"
25
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
26
#include "llvm/Analysis/ValueTracking.h"
27
#include "llvm/Config/llvm-config.h"
28
#include "llvm/IR/CFG.h"
29
#include "llvm/IR/Constants.h"
30
#include "llvm/IR/DebugLoc.h"
31
#include "llvm/IR/Dominators.h"
32
#include "llvm/IR/IRPrintingPasses.h"
33
#include "llvm/IR/Instructions.h"
34
#include "llvm/IR/LLVMContext.h"
35
#include "llvm/IR/Metadata.h"
36
#include "llvm/IR/PassManager.h"
37
#include "llvm/Support/CommandLine.h"
38
#include "llvm/Support/Debug.h"
39
#include "llvm/Support/raw_ostream.h"
40
#include <algorithm>
41
using namespace llvm;
42
43
// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
44
template class llvm::LoopBase<BasicBlock, Loop>;
45
template class llvm::LoopInfoBase<BasicBlock, Loop>;
46
47
// Always verify loopinfo if expensive checking is enabled.
48
#ifdef EXPENSIVE_CHECKS
49
bool llvm::VerifyLoopInfo = true;
50
#else
51
bool llvm::VerifyLoopInfo = false;
52
#endif
53
static cl::opt<bool, true>
54
    VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
55
                    cl::Hidden, cl::desc("Verify loop info (time consuming)"));
56
57
//===----------------------------------------------------------------------===//
58
// Loop implementation
59
//
60
61
22.5M
bool Loop::isLoopInvariant(const Value *V) const {
62
22.5M
  if (const Instruction *I = dyn_cast<Instruction>(V))
63
17.8M
    return !contains(I);
64
4.76M
  return true; // All non-instructions are loop invariant
65
4.76M
}
66
67
13.3M
bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
68
16.1M
  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
69
13.3M
}
70
71
bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
72
2.34M
                             MemorySSAUpdater *MSSAU) const {
73
2.34M
  if (Instruction *I = dyn_cast<Instruction>(V))
74
2.31M
    return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
75
32.1k
  return true; // All non-instructions are loop-invariant.
76
32.1k
}
77
78
bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
79
                             Instruction *InsertPt,
80
2.56M
                             MemorySSAUpdater *MSSAU) const {
81
2.56M
  // Test if the value is already loop-invariant.
82
2.56M
  if (isLoopInvariant(I))
83
45.2k
    return true;
84
2.52M
  if (!isSafeToSpeculativelyExecute(I))
85
990k
    return false;
86
1.53M
  if (I->mayReadFromMemory())
87
53.2k
    return false;
88
1.48M
  // EH block instructions are immobile.
89
1.48M
  if (I->isEHPad())
90
0
    return false;
91
1.48M
  // Determine the insertion point, unless one was given.
92
1.48M
  if (!InsertPt) {
93
784k
    BasicBlock *Preheader = getLoopPreheader();
94
784k
    // Without a preheader, hoisting is not feasible.
95
784k
    if (!Preheader)
96
0
      return false;
97
784k
    InsertPt = Preheader->getTerminator();
98
784k
  }
99
1.48M
  // Don't hoist instructions with loop-variant operands.
100
1.48M
  for (Value *Operand : I->operands())
101
1.51M
    if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
102
1.46M
      return false;
103
1.48M
104
1.48M
  // Hoist.
105
1.48M
  I->moveBefore(InsertPt);
106
19.4k
  if (MSSAU)
107
0
    if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
108
0
      MSSAU->moveToPlace(MUD, InsertPt->getParent(), MemorySSA::End);
109
19.4k
110
19.4k
  // There is possibility of hoisting this instruction above some arbitrary
111
19.4k
  // condition. Any metadata defined on it can be control dependent on this
112
19.4k
  // condition. Conservatively strip it here so that we don't give any wrong
113
19.4k
  // information to the optimizer.
114
19.4k
  I->dropUnknownNonDebugMetadata();
115
19.4k
116
19.4k
  Changed = true;
117
19.4k
  return true;
118
1.48M
}
119
120
bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
121
4.84k
                                  BasicBlock *&Backedge) const {
122
4.84k
  BasicBlock *H = getHeader();
123
4.84k
124
4.84k
  Incoming = nullptr;
125
4.84k
  Backedge = nullptr;
126
4.84k
  pred_iterator PI = pred_begin(H);
127
4.84k
  assert(PI != pred_end(H) && "Loop must have at least one backedge!");
128
4.84k
  Backedge = *PI++;
129
4.84k
  if (PI == pred_end(H))
130
0
    return false; // dead loop
131
4.84k
  Incoming = *PI++;
132
4.84k
  if (PI != pred_end(H))
133
23
    return false; // multiple backedges?
134
4.82k
135
4.82k
  if (contains(Incoming)) {
136
3.32k
    if (contains(Backedge))
137
0
      return false;
138
3.32k
    std::swap(Incoming, Backedge);
139
3.32k
  } else 
if (1.50k
!contains(Backedge)1.50k
)
140
0
    return false;
141
4.82k
142
4.82k
  assert(Incoming && Backedge && "expected non-null incoming and backedges");
143
4.82k
  return true;
144
4.82k
}
145
146
4.84k
PHINode *Loop::getCanonicalInductionVariable() const {
147
4.84k
  BasicBlock *H = getHeader();
148
4.84k
149
4.84k
  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
150
4.84k
  if (!getIncomingAndBackEdge(Incoming, Backedge))
151
23
    return nullptr;
152
4.82k
153
4.82k
  // Loop over all of the PHI nodes, looking for a canonical indvar.
154
6.10k
  
for (BasicBlock::iterator I = H->begin(); 4.82k
isa<PHINode>(I);
++I1.27k
) {
155
5.53k
    PHINode *PN = cast<PHINode>(I);
156
5.53k
    if (ConstantInt *CI =
157
4.72k
            dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
158
4.72k
      if (CI->isZero())
159
4.40k
        if (Instruction *Inc =
160
4.40k
                dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
161
4.40k
          if (Inc->getOpcode() == Instruction::Add && 
Inc->getOperand(0) == PN4.36k
)
162
4.35k
            if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
163
4.30k
              if (CI->isOne())
164
4.25k
                return PN;
165
5.53k
  }
166
4.82k
  
return nullptr569
;
167
4.82k
}
168
169
/// Get the latch condition instruction.
170
48
static ICmpInst *getLatchCmpInst(const Loop &L) {
171
48
  if (BasicBlock *Latch = L.getLoopLatch())
172
48
    if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
173
48
      if (BI->isConditional())
174
48
        return dyn_cast<ICmpInst>(BI->getCondition());
175
0
176
0
  return nullptr;
177
0
}
178
179
/// Return the final value of the loop induction variable if found.
180
static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
181
16
                               const Instruction &StepInst) {
182
16
  ICmpInst *LatchCmpInst = getLatchCmpInst(L);
183
16
  if (!LatchCmpInst)
184
0
    return nullptr;
185
16
186
16
  Value *Op0 = LatchCmpInst->getOperand(0);
187
16
  Value *Op1 = LatchCmpInst->getOperand(1);
188
16
  if (Op0 == &IndVar || 
Op0 == &StepInst13
)
189
16
    return Op1;
190
0
191
0
  if (Op1 == &IndVar || Op1 == &StepInst)
192
0
    return Op0;
193
0
194
0
  return nullptr;
195
0
}
196
197
Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L,
198
                                                       PHINode &IndVar,
199
16
                                                       ScalarEvolution &SE) {
200
16
  InductionDescriptor IndDesc;
201
16
  if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
202
0
    return None;
203
16
204
16
  Value *InitialIVValue = IndDesc.getStartValue();
205
16
  Instruction *StepInst = IndDesc.getInductionBinOp();
206
16
  if (!InitialIVValue || !StepInst)
207
0
    return None;
208
16
209
16
  const SCEV *Step = IndDesc.getStep();
210
16
  Value *StepInstOp1 = StepInst->getOperand(1);
211
16
  Value *StepInstOp0 = StepInst->getOperand(0);
212
16
  Value *StepValue = nullptr;
213
16
  if (SE.getSCEV(StepInstOp1) == Step)
214
15
    StepValue = StepInstOp1;
215
1
  else if (SE.getSCEV(StepInstOp0) == Step)
216
0
    StepValue = StepInstOp0;
217
16
218
16
  Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
219
16
  if (!FinalIVValue)
220
0
    return None;
221
16
222
16
  return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
223
16
                    SE);
224
16
}
225
226
using Direction = Loop::LoopBounds::Direction;
227
228
16
ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
229
16
  BasicBlock *Latch = L.getLoopLatch();
230
16
  assert(Latch && "Expecting valid latch");
231
16
232
16
  BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
233
16
  assert(BI && BI->isConditional() && "Expecting conditional latch branch");
234
16
235
16
  ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
236
16
  assert(LatchCmpInst &&
237
16
         "Expecting the latch compare instruction to be a CmpInst");
238
16
239
16
  // Need to inverse the predicate when first successor is not the loop
240
16
  // header
241
16
  ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
242
16
                                 ? 
LatchCmpInst->getPredicate()14
243
16
                                 : 
LatchCmpInst->getInversePredicate()2
;
244
16
245
16
  if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
246
0
    Pred = ICmpInst::getSwappedPredicate(Pred);
247
16
248
16
  // Need to flip strictness of the predicate when the latch compare instruction
249
16
  // is not using StepInst
250
16
  if (LatchCmpInst->getOperand(0) == &getStepInst() ||
251
16
      
LatchCmpInst->getOperand(1) == &getStepInst()3
)
252
13
    return Pred;
253
3
254
3
  // Cannot flip strictness of NE and EQ
255
3
  if (Pred != ICmpInst::ICMP_NE && 
Pred != ICmpInst::ICMP_EQ0
)
256
0
    return ICmpInst::getFlippedStrictnessPredicate(Pred);
257
3
258
3
  Direction D = getDirection();
259
3
  if (D == Direction::Increasing)
260
2
    return ICmpInst::ICMP_SLT;
261
1
262
1
  if (D == Direction::Decreasing)
263
0
    return ICmpInst::ICMP_SGT;
264
1
265
1
  // If cannot determine the direction, then unable to find the canonical
266
1
  // predicate
267
1
  return ICmpInst::BAD_ICMP_PREDICATE;
268
1
}
269
270
19
Direction Loop::LoopBounds::getDirection() const {
271
19
  if (const SCEVAddRecExpr *StepAddRecExpr =
272
19
          dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
273
19
    if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
274
19
      if (SE.isKnownPositive(StepRecur))
275
15
        return Direction::Increasing;
276
4
      if (SE.isKnownNegative(StepRecur))
277
1
        return Direction::Decreasing;
278
3
    }
279
3
280
3
  return Direction::Unknown;
281
3
}
282
283
16
Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
284
16
  if (PHINode *IndVar = getInductionVariable(SE))
285
16
    return LoopBounds::getBounds(*this, *IndVar, SE);
286
0
287
0
  return None;
288
0
}
289
290
32
PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
291
32
  if (!isLoopSimplifyForm())
292
0
    return nullptr;
293
32
294
32
  BasicBlock *Header = getHeader();
295
32
  assert(Header && "Expected a valid loop header");
296
32
  ICmpInst *CmpInst = getLatchCmpInst(*this);
297
32
  if (!CmpInst)
298
0
    return nullptr;
299
32
300
32
  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
301
32
  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
302
32
303
32
  for (PHINode &IndVar : Header->phis()) {
304
32
    InductionDescriptor IndDesc;
305
32
    if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
306
0
      continue;
307
32
308
32
    Instruction *StepInst = IndDesc.getInductionBinOp();
309
32
310
32
    // case 1:
311
32
    // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
312
32
    // StepInst = IndVar + step
313
32
    // cmp = StepInst < FinalValue
314
32
    if (StepInst == LatchCmpOp0 || 
StepInst == LatchCmpOp16
)
315
26
      return &IndVar;
316
6
317
6
    // case 2:
318
6
    // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
319
6
    // StepInst = IndVar + step
320
6
    // cmp = IndVar < FinalValue
321
6
    if (&IndVar == LatchCmpOp0 || 
&IndVar == LatchCmpOp10
)
322
6
      return &IndVar;
323
6
  }
324
32
325
32
  
return nullptr0
;
326
32
}
327
328
bool Loop::getInductionDescriptor(ScalarEvolution &SE,
329
0
                                  InductionDescriptor &IndDesc) const {
330
0
  if (PHINode *IndVar = getInductionVariable(SE))
331
0
    return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
332
0
333
0
  return false;
334
0
}
335
336
bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
337
5
                                        ScalarEvolution &SE) const {
338
5
  // Located in the loop header
339
5
  BasicBlock *Header = getHeader();
340
5
  if (AuxIndVar.getParent() != Header)
341
0
    return false;
342
5
343
5
  // No uses outside of the loop
344
5
  for (User *U : AuxIndVar.users())
345
8
    if (const Instruction *I = dyn_cast<Instruction>(U))
346
8
      if (!contains(I))
347
1
        return false;
348
5
349
5
  InductionDescriptor IndDesc;
350
4
  if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
351
2
    return false;
352
2
353
2
  // The step instruction opcode should be add or sub.
354
2
  if (IndDesc.getInductionOpcode() != Instruction::Add &&
355
2
      
IndDesc.getInductionOpcode() != Instruction::Sub0
)
356
0
    return false;
357
2
358
2
  // Incremented by a loop invariant step for each loop iteration
359
2
  return SE.isLoopInvariant(IndDesc.getStep(), this);
360
2
}
361
362
0
bool Loop::isCanonical(ScalarEvolution &SE) const {
363
0
  InductionDescriptor IndDesc;
364
0
  if (!getInductionDescriptor(SE, IndDesc))
365
0
    return false;
366
0
367
0
  ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
368
0
  if (!Init || !Init->isZero())
369
0
    return false;
370
0
371
0
  if (IndDesc.getInductionOpcode() != Instruction::Add)
372
0
    return false;
373
0
374
0
  ConstantInt *Step = IndDesc.getConstIntStepValue();
375
0
  if (!Step || !Step->isOne())
376
0
    return false;
377
0
378
0
  return true;
379
0
}
380
381
// Check that 'BB' doesn't have any uses outside of the 'L'
382
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
383
2
                               DominatorTree &DT) {
384
12
  for (const Instruction &I : BB) {
385
12
    // Tokens can't be used in PHI nodes and live-out tokens prevent loop
386
12
    // optimizations, so for the purposes of considered LCSSA form, we
387
12
    // can ignore them.
388
12
    if (I.getType()->isTokenTy())
389
0
      continue;
390
12
391
13
    
for (const Use &U : I.uses())12
{
392
13
      const Instruction *UI = cast<Instruction>(U.getUser());
393
13
      const BasicBlock *UserBB = UI->getParent();
394
13
      if (const PHINode *P = dyn_cast<PHINode>(UI))
395
1
        UserBB = P->getIncomingBlock(U);
396
13
397
13
      // Check the current block, as a fast-path, before checking whether
398
13
      // the use is anywhere in the loop.  Most values are used in the same
399
13
      // block they are defined in.  Also, blocks not reachable from the
400
13
      // entry are special; uses in them don't need to go through PHIs.
401
13
      if (UserBB != &BB && 
!L.contains(UserBB)4
&&
402
13
          
DT.isReachableFromEntry(UserBB)0
)
403
0
        return false;
404
13
    }
405
12
  }
406
2
  return true;
407
2
}
408
409
0
bool Loop::isLCSSAForm(DominatorTree &DT) const {
410
0
  // For each block we check that it doesn't have any uses outside of this loop.
411
0
  return all_of(this->blocks(), [&](const BasicBlock *BB) {
412
0
    return isBlockInLCSSAForm(*this, *BB, DT);
413
0
  });
414
0
}
415
416
1
bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
417
1
  // For each block we check that it doesn't have any uses outside of its
418
1
  // innermost loop. This process will transitively guarantee that the current
419
1
  // loop and all of the nested loops are in LCSSA form.
420
2
  return all_of(this->blocks(), [&](const BasicBlock *BB) {
421
2
    return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
422
2
  });
423
1
}
424
425
2.93M
bool Loop::isLoopSimplifyForm() const {
426
2.93M
  // Normal-form loops have a preheader, a single backedge, and all of their
427
2.93M
  // exits have all their predecessors inside the loop.
428
2.93M
  return getLoopPreheader() && 
getLoopLatch()2.93M
&&
hasDedicatedExits()2.93M
;
429
2.93M
}
430
431
// Routines that reform the loop CFG and split edges often fail on indirectbr.
432
241k
bool Loop::isSafeToClone() const {
433
241k
  // Return false if any loop blocks contain indirectbrs, or there are any calls
434
241k
  // to noduplicate functions.
435
241k
  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
436
241k
  // operand list to reflect the newly cloned labels.
437
1.07M
  for (BasicBlock *BB : this->blocks()) {
438
1.07M
    if (isa<IndirectBrInst>(BB->getTerminator()) ||
439
1.07M
        
isa<CallBrInst>(BB->getTerminator())1.07M
)
440
7
      return false;
441
1.07M
442
1.07M
    for (Instruction &I : *BB)
443
6.62M
      if (auto CS = CallSite(&I))
444
447k
        if (CS.cannotDuplicate())
445
3
          return false;
446
1.07M
  }
447
241k
  
return true241k
;
448
241k
}
449
450
8.63M
MDNode *Loop::getLoopID() const {
451
8.63M
  MDNode *LoopID = nullptr;
452
8.63M
453
8.63M
  // Go through the latch blocks and check the terminator for the metadata.
454
8.63M
  SmallVector<BasicBlock *, 4> LatchesBlocks;
455
8.63M
  getLoopLatches(LatchesBlocks);
456
8.63M
  for (BasicBlock *BB : LatchesBlocks) {
457
8.63M
    Instruction *TI = BB->getTerminator();
458
8.63M
    MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
459
8.63M
460
8.63M
    if (!MD)
461
7.14M
      return nullptr;
462
1.49M
463
1.49M
    if (!LoopID)
464
1.49M
      LoopID = MD;
465
149
    else if (MD != LoopID)
466
4
      return nullptr;
467
1.49M
  }
468
8.63M
  
if (1.49M
!LoopID1.49M
||
LoopID->getNumOperands() == 01.49M
||
469
1.49M
      LoopID->getOperand(0) != LoopID)
470
0
    return nullptr;
471
1.49M
  return LoopID;
472
1.49M
}
473
474
57.8k
void Loop::setLoopID(MDNode *LoopID) const {
475
57.8k
  assert((!LoopID || LoopID->getNumOperands() > 0) &&
476
57.8k
         "Loop ID needs at least one operand");
477
57.8k
  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
478
57.8k
         "Loop ID should refer to itself");
479
57.8k
480
57.8k
  SmallVector<BasicBlock *, 4> LoopLatches;
481
57.8k
  getLoopLatches(LoopLatches);
482
57.8k
  for (BasicBlock *BB : LoopLatches)
483
57.8k
    BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
484
57.8k
}
485
486
1.27k
void Loop::setLoopAlreadyUnrolled() {
487
1.27k
  LLVMContext &Context = getHeader()->getContext();
488
1.27k
489
1.27k
  MDNode *DisableUnrollMD =
490
1.27k
      MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
491
1.27k
  MDNode *LoopID = getLoopID();
492
1.27k
  MDNode *NewLoopID = makePostTransformationMetadata(
493
1.27k
      Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
494
1.27k
  setLoopID(NewLoopID);
495
1.27k
}
496
497
107k
bool Loop::isAnnotatedParallel() const {
498
107k
  MDNode *DesiredLoopIdMetadata = getLoopID();
499
107k
500
107k
  if (!DesiredLoopIdMetadata)
501
69.4k
    return false;
502
38.5k
503
38.5k
  MDNode *ParallelAccesses =
504
38.5k
      findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
505
38.5k
  SmallPtrSet<MDNode *, 4>
506
38.5k
      ParallelAccessGroups; // For scalable 'contains' check.
507
38.5k
  if (ParallelAccesses) {
508
34
    for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
509
34
      MDNode *AccGroup = cast<MDNode>(MD.get());
510
34
      assert(isValidAsAccessGroup(AccGroup) &&
511
34
             "List item must be an access group");
512
34
      ParallelAccessGroups.insert(AccGroup);
513
34
    }
514
32
  }
515
38.5k
516
38.5k
  // The loop branch contains the parallel loop metadata. In order to ensure
517
38.5k
  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
518
38.5k
  // dependencies (thus converted the loop back to a sequential loop), check
519
38.5k
  // that all the memory instructions in the loop belong to an access group that
520
38.5k
  // is parallel to this loop.
521
42.4k
  for (BasicBlock *BB : this->blocks()) {
522
363k
    for (Instruction &I : *BB) {
523
363k
      if (!I.mayReadOrWriteMemory())
524
325k
        continue;
525
37.6k
526
37.6k
      if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
527
132
        auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
528
132
          if (AG->getNumOperands() == 0) {
529
125
            assert(isValidAsAccessGroup(AG) && "Item must be an access group");
530
125
            return ParallelAccessGroups.count(AG);
531
125
          }
532
7
533
13
          
for (const MDOperand &AccessListItem : AG->operands())7
{
534
13
            MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
535
13
            assert(isValidAsAccessGroup(AccGroup) &&
536
13
                   "List item must be an access group");
537
13
            if (ParallelAccessGroups.count(AccGroup))
538
6
              return true;
539
13
          }
540
7
          
return false1
;
541
7
        };
542
132
543
132
        if (ContainsAccessGroup(AccessGroup))
544
127
          continue;
545
37.5k
      }
546
37.5k
547
37.5k
      // The memory instruction can refer to the loop identifier metadata
548
37.5k
      // directly or indirectly through another list metadata (in case of
549
37.5k
      // nested parallel loops). The loop identifier metadata refers to
550
37.5k
      // itself so we can check both cases with the same routine.
551
37.5k
      MDNode *LoopIdMD =
552
37.5k
          I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
553
37.5k
554
37.5k
      if (!LoopIdMD)
555
37.5k
        return false;
556
2
557
2
      bool LoopIdMDFound = false;
558
2
      for (const MDOperand &MDOp : LoopIdMD->operands()) {
559
2
        if (MDOp == DesiredLoopIdMetadata) {
560
2
          LoopIdMDFound = true;
561
2
          break;
562
2
        }
563
2
      }
564
2
565
2
      if (!LoopIdMDFound)
566
0
        return false;
567
2
    }
568
42.4k
  }
569
38.5k
  
return true982
;
570
38.5k
}
571
572
737k
DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
573
574
737k
Loop::LocRange Loop::getLocRange() const {
575
737k
  // If we have a debug location in the loop ID, then use it.
576
737k
  if (MDNode *LoopID = getLoopID()) {
577
107k
    DebugLoc Start;
578
107k
    // We use the first DebugLoc in the header as the start location of the loop
579
107k
    // and if there is a second DebugLoc in the header we use it as end location
580
107k
    // of the loop.
581
246k
    for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; 
++i139k
) {
582
193k
      if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
583
108k
        if (!Start)
584
54.1k
          Start = DebugLoc(L);
585
54.0k
        else
586
54.0k
          return LocRange(Start, DebugLoc(L));
587
108k
      }
588
193k
    }
589
107k
590
107k
    
if (53.0k
Start53.0k
)
591
49
      return LocRange(Start);
592
683k
  }
593
683k
594
683k
  // Try the pre-header first.
595
683k
  if (BasicBlock *PHeadBB = getLoopPreheader())
596
226k
    if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
597
1.91k
      return LocRange(DL);
598
681k
599
681k
  // If we have no pre-header or there are no instructions with debug
600
681k
  // info in it, try the header.
601
681k
  if (BasicBlock *HeadBB = getHeader())
602
681k
    return LocRange(HeadBB->getTerminator()->getDebugLoc());
603
0
604
0
  return LocRange();
605
0
}
606
607
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
608
LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
609
610
LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
611
  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
612
}
613
#endif
614
615
//===----------------------------------------------------------------------===//
616
// UnloopUpdater implementation
617
//
618
619
namespace {
620
/// Find the new parent loop for all blocks within the "unloop" whose last
621
/// backedges has just been removed.
622
class UnloopUpdater {
623
  Loop &Unloop;
624
  LoopInfo *LI;
625
626
  LoopBlocksDFS DFS;
627
628
  // Map unloop's immediate subloops to their nearest reachable parents. Nested
629
  // loops within these subloops will not change parents. However, an immediate
630
  // subloop's new parent will be the nearest loop reachable from either its own
631
  // exits *or* any of its nested loop's exits.
632
  DenseMap<Loop *, Loop *> SubloopParents;
633
634
  // Flag the presence of an irreducible backedge whose destination is a block
635
  // directly contained by the original unloop.
636
  bool FoundIB;
637
638
public:
639
  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
640
5.89k
      : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
641
642
  void updateBlockParents();
643
644
  void removeBlocksFromAncestors();
645
646
  void updateSubloopParents();
647
648
protected:
649
  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
650
};
651
} // end anonymous namespace
652
653
/// Update the parent loop for all blocks that are directly contained within the
654
/// original "unloop".
655
5.89k
void UnloopUpdater::updateBlockParents() {
656
5.89k
  if (Unloop.getNumBlocks()) {
657
3.72k
    // Perform a post order CFG traversal of all blocks within this loop,
658
3.72k
    // propagating the nearest loop from successors to predecessors.
659
3.72k
    LoopBlocksTraversal Traversal(DFS, LI);
660
15.2k
    for (BasicBlock *POI : Traversal) {
661
15.2k
662
15.2k
      Loop *L = LI->getLoopFor(POI);
663
15.2k
      Loop *NL = getNearestLoop(POI, L);
664
15.2k
665
15.2k
      if (NL != L) {
666
13.5k
        // For reducible loops, NL is now an ancestor of Unloop.
667
13.5k
        assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
668
13.5k
               "uninitialized successor");
669
13.5k
        LI->changeLoopFor(POI, NL);
670
13.5k
      } else {
671
1.68k
        // Or the current block is part of a subloop, in which case its parent
672
1.68k
        // is unchanged.
673
1.68k
        assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
674
1.68k
      }
675
15.2k
    }
676
3.72k
  }
677
5.89k
  // Each irreducible loop within the unloop induces a round of iteration using
678
5.89k
  // the DFS result cached by Traversal.
679
5.89k
  bool Changed = FoundIB;
680
5.89k
  for (unsigned NIters = 0; Changed; 
++NIters4
) {
681
4
    assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
682
4
683
4
    // Iterate over the postorder list of blocks, propagating the nearest loop
684
4
    // from successors to predecessors as before.
685
4
    Changed = false;
686
4
    for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
687
4
                                   POE = DFS.endPostorder();
688
56
         POI != POE; 
++POI52
) {
689
52
690
52
      Loop *L = LI->getLoopFor(*POI);
691
52
      Loop *NL = getNearestLoop(*POI, L);
692
52
      if (NL != L) {
693
6
        assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
694
6
               "uninitialized successor");
695
6
        LI->changeLoopFor(*POI, NL);
696
6
        Changed = true;
697
6
      }
698
52
    }
699
4
  }
700
5.89k
}
701
702
/// Remove unloop's blocks from all ancestors below their new parents.
703
5.89k
void UnloopUpdater::removeBlocksFromAncestors() {
704
5.89k
  // Remove all unloop's blocks (including those in nested subloops) from
705
5.89k
  // ancestors below the new parent loop.
706
5.89k
  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
707
21.1k
       BI != BE; 
++BI15.2k
) {
708
15.2k
    Loop *OuterParent = LI->getLoopFor(*BI);
709
15.2k
    if (Unloop.contains(OuterParent)) {
710
2.15k
      while (OuterParent->getParentLoop() != &Unloop)
711
478
        OuterParent = OuterParent->getParentLoop();
712
1.67k
      OuterParent = SubloopParents[OuterParent];
713
1.67k
    }
714
15.2k
    // Remove blocks from former Ancestors except Unloop itself which will be
715
15.2k
    // deleted.
716
15.2k
    for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
717
15.2k
         
OldParent = OldParent->getParentLoop()55
) {
718
55
      assert(OldParent && "new loop is not an ancestor of the original");
719
55
      OldParent->removeBlockFromLoop(*BI);
720
55
    }
721
15.2k
  }
722
5.89k
}
723
724
/// Update the parent loop for all subloops directly nested within unloop.
725
5.89k
void UnloopUpdater::updateSubloopParents() {
726
6.49k
  while (!Unloop.empty()) {
727
602
    Loop *Subloop = *std::prev(Unloop.end());
728
602
    Unloop.removeChildLoop(std::prev(Unloop.end()));
729
602
730
602
    assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
731
602
    if (Loop *Parent = SubloopParents[Subloop])
732
600
      Parent->addChildLoop(Subloop);
733
2
    else
734
2
      LI->addTopLevelLoop(Subloop);
735
602
  }
736
5.89k
}
737
738
/// Return the nearest parent loop among this block's successors. If a successor
739
/// is a subloop header, consider its parent to be the nearest parent of the
740
/// subloop's exits.
741
///
742
/// For subloop blocks, simply update SubloopParents and return NULL.
743
15.2k
Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
744
15.2k
745
15.2k
  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
746
15.2k
  // is considered uninitialized.
747
15.2k
  Loop *NearLoop = BBLoop;
748
15.2k
749
15.2k
  Loop *Subloop = nullptr;
750
15.2k
  if (NearLoop != &Unloop && 
Unloop.contains(NearLoop)1.72k
) {
751
1.67k
    Subloop = NearLoop;
752
1.67k
    // Find the subloop ancestor that is directly contained within Unloop.
753
2.15k
    while (Subloop->getParentLoop() != &Unloop) {
754
478
      Subloop = Subloop->getParentLoop();
755
478
      assert(Subloop && "subloop is not an ancestor of the original loop");
756
478
    }
757
1.67k
    // Get the current nearest parent of the Subloop exits, initially Unloop.
758
1.67k
    NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
759
1.67k
  }
760
15.2k
761
15.2k
  succ_iterator I = succ_begin(BB), E = succ_end(BB);
762
15.2k
  if (I == E) {
763
16
    assert(!Subloop && "subloop blocks must have a successor");
764
16
    NearLoop = nullptr; // unloop blocks may now exit the function.
765
16
  }
766
39.5k
  for (; I != E; 
++I24.2k
) {
767
24.2k
    if (*I == BB)
768
475
      continue; // self loops are uninteresting
769
23.7k
770
23.7k
    Loop *L = LI->getLoopFor(*I);
771
23.7k
    if (L == &Unloop) {
772
10
      // This successor has not been processed. This path must lead to an
773
10
      // irreducible backedge.
774
10
      assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
775
10
      FoundIB = true;
776
10
    }
777
23.7k
    if (L != &Unloop && 
Unloop.contains(L)23.7k
) {
778
2.24k
      // Successor is in a subloop.
779
2.24k
      if (Subloop)
780
1.64k
        continue; // Branching within subloops. Ignore it.
781
602
782
602
      // BB branches from the original into a subloop header.
783
602
      assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
784
602
785
602
      // Get the current nearest parent of the Subloop's exits.
786
602
      L = SubloopParents[L];
787
602
      // L could be Unloop if the only exit was an irreducible backedge.
788
602
    }
789
23.7k
    
if (22.1k
L == &Unloop22.1k
) {
790
10
      continue;
791
10
    }
792
22.1k
    // Handle critical edges from Unloop into a sibling loop.
793
22.1k
    if (L && 
!L->contains(&Unloop)18.9k
) {
794
200
      L = L->getParentLoop();
795
200
    }
796
22.1k
    // Remember the nearest parent loop among successors or subloop exits.
797
22.1k
    if (NearLoop == &Unloop || 
!NearLoop7.98k
||
NearLoop->contains(L)6.25k
)
798
20.4k
      NearLoop = L;
799
22.1k
  }
800
15.2k
  if (Subloop) {
801
1.67k
    SubloopParents[Subloop] = NearLoop;
802
1.67k
    return BBLoop;
803
1.67k
  }
804
13.6k
  return NearLoop;
805
13.6k
}
806
807
3.90k
LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
808
809
bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
810
3.61k
                          FunctionAnalysisManager::Invalidator &) {
811
3.61k
  // Check whether the analysis, all analyses on functions, or the function's
812
3.61k
  // CFG have been preserved.
813
3.61k
  auto PAC = PA.getChecker<LoopAnalysis>();
814
3.61k
  return !(PAC.preserved() || 
PAC.preservedSet<AllAnalysesOn<Function>>()2.48k
||
815
3.61k
           
PAC.preservedSet<CFGAnalyses>()2.46k
);
816
3.61k
}
817
818
24.4k
void LoopInfo::erase(Loop *Unloop) {
819
24.4k
  assert(!Unloop->isInvalid() && "Loop has already been erased!");
820
24.4k
821
24.4k
  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
822
24.4k
823
24.4k
  // First handle the special case of no parent loop to simplify the algorithm.
824
24.4k
  if (!Unloop->getParentLoop()) {
825
18.5k
    // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
826
18.5k
    for (Loop::block_iterator I = Unloop->block_begin(),
827
18.5k
                              E = Unloop->block_end();
828
100k
         I != E; 
++I81.9k
) {
829
81.9k
830
81.9k
      // Don't reparent blocks in subloops.
831
81.9k
      if (getLoopFor(*I) != Unloop)
832
3.29k
        continue;
833
78.7k
834
78.7k
      // Blocks no longer have a parent but are still referenced by Unloop until
835
78.7k
      // the Unloop object is deleted.
836
78.7k
      changeLoopFor(*I, nullptr);
837
78.7k
    }
838
18.5k
839
18.5k
    // Remove the loop from the top-level LoopInfo object.
840
745k
    for (iterator I = begin();; 
++I727k
) {
841
745k
      assert(I != end() && "Couldn't find loop");
842
745k
      if (*I == Unloop) {
843
18.5k
        removeLoop(I);
844
18.5k
        break;
845
18.5k
      }
846
745k
    }
847
18.5k
848
18.5k
    // Move all of the subloops to the top-level.
849
20.0k
    while (!Unloop->empty())
850
1.51k
      addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
851
18.5k
852
18.5k
    return;
853
18.5k
  }
854
5.89k
855
5.89k
  // Update the parent loop for all blocks within the loop. Blocks within
856
5.89k
  // subloops will not change parents.
857
5.89k
  UnloopUpdater Updater(Unloop, this);
858
5.89k
  Updater.updateBlockParents();
859
5.89k
860
5.89k
  // Remove blocks from former ancestor loops.
861
5.89k
  Updater.removeBlocksFromAncestors();
862
5.89k
863
5.89k
  // Add direct subloops as children in their new parent loop.
864
5.89k
  Updater.updateSubloopParents();
865
5.89k
866
5.89k
  // Remove unloop from its parent loop.
867
5.89k
  Loop *ParentLoop = Unloop->getParentLoop();
868
7.39k
  for (Loop::iterator I = ParentLoop->begin();; 
++I1.50k
) {
869
7.39k
    assert(I != ParentLoop->end() && "Couldn't find loop");
870
7.39k
    if (*I == Unloop) {
871
5.89k
      ParentLoop->removeChildLoop(I);
872
5.89k
      break;
873
5.89k
    }
874
7.39k
  }
875
5.89k
}
876
877
AnalysisKey LoopAnalysis::Key;
878
879
5.21k
LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
880
5.21k
  // FIXME: Currently we create a LoopInfo from scratch for every function.
881
5.21k
  // This may prove to be too wasteful due to deallocating and re-allocating
882
5.21k
  // memory each time for the underlying map and vector datastructures. At some
883
5.21k
  // point it may prove worthwhile to use a freelist and recycle LoopInfo
884
5.21k
  // objects. I don't want to add that kind of complexity until the scope of
885
5.21k
  // the problem is better understood.
886
5.21k
  LoopInfo LI;
887
5.21k
  LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
888
5.21k
  return LI;
889
5.21k
}
890
891
PreservedAnalyses LoopPrinterPass::run(Function &F,
892
26
                                       FunctionAnalysisManager &AM) {
893
26
  AM.getResult<LoopAnalysis>(F).print(OS);
894
26
  return PreservedAnalyses::all();
895
26
}
896
897
8
void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
898
8
899
8
  if (forcePrintModuleIR()) {
900
1
    // handling -print-module-scope
901
1
    OS << Banner << " (loop: ";
902
1
    L.getHeader()->printAsOperand(OS, false);
903
1
    OS << ")\n";
904
1
905
1
    // printing whole module
906
1
    OS << *L.getHeader()->getModule();
907
1
    return;
908
1
  }
909
7
910
7
  OS << Banner;
911
7
912
7
  auto *PreHeader = L.getLoopPreheader();
913
7
  if (PreHeader) {
914
7
    OS << "\n; Preheader:";
915
7
    PreHeader->print(OS);
916
7
    OS << "\n; Loop:";
917
7
  }
918
7
919
7
  for (auto *Block : L.blocks())
920
9
    if (Block)
921
9
      Block->print(OS);
922
0
    else
923
0
      OS << "Printing <null> block";
924
7
925
7
  SmallVector<BasicBlock *, 8> ExitBlocks;
926
7
  L.getExitBlocks(ExitBlocks);
927
7
  if (!ExitBlocks.empty()) {
928
7
    OS << "\n; Exit blocks";
929
7
    for (auto *Block : ExitBlocks)
930
7
      if (Block)
931
7
        Block->print(OS);
932
0
      else
933
0
        OS << "Printing <null> block";
934
7
  }
935
7
}
936
937
5.59M
MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
938
5.59M
  // No loop metadata node, no loop properties.
939
5.59M
  if (!LoopID)
940
4.57M
    return nullptr;
941
1.02M
942
1.02M
  // First operand should refer to the metadata node itself, for legacy reasons.
943
1.02M
  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
944
1.02M
  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
945
1.02M
946
1.02M
  // Iterate over the metdata node operands and look for MDString metadata.
947
2.71M
  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; 
++i1.68M
) {
948
1.72M
    MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
949
1.72M
    if (!MD || MD->getNumOperands() < 1)
950
0
      continue;
951
1.72M
    MDString *S = dyn_cast<MDString>(MD->getOperand(0));
952
1.72M
    if (!S)
953
862k
      continue;
954
860k
    // Return the operand node if MDString holds expected metadata.
955
860k
    if (Name.equals(S->getString()))
956
33.6k
      return MD;
957
860k
  }
958
1.02M
959
1.02M
  // Loop property not found.
960
1.02M
  
return nullptr987k
;
961
1.02M
}
962
963
5.59M
MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
964
5.59M
  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
965
5.59M
}
966
967
0
bool llvm::isValidAsAccessGroup(MDNode *Node) {
968
0
  return Node->getNumOperands() == 0 && Node->isDistinct();
969
0
}
970
971
MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
972
                                             MDNode *OrigLoopID,
973
                                             ArrayRef<StringRef> RemovePrefixes,
974
35.3k
                                             ArrayRef<MDNode *> AddAttrs) {
975
35.3k
  // First remove any existing loop metadata related to this transformation.
976
35.3k
  SmallVector<Metadata *, 4> MDs;
977
35.3k
978
35.3k
  // Reserve first location for self reference to the LoopID metadata node.
979
35.3k
  TempMDTuple TempNode = MDNode::getTemporary(Context, None);
980
35.3k
  MDs.push_back(TempNode.get());
981
35.3k
982
35.3k
  // Remove metadata for the transformation that has been applied or that became
983
35.3k
  // outdated.
984
35.3k
  if (OrigLoopID) {
985
31.3k
    for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; 
++i16.8k
) {
986
16.8k
      bool IsVectorMetadata = false;
987
16.8k
      Metadata *Op = OrigLoopID->getOperand(i);
988
16.8k
      if (MDNode *MD = dyn_cast<MDNode>(Op)) {
989
16.8k
        const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
990
16.8k
        if (S)
991
12.7k
          IsVectorMetadata =
992
25.4k
              llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
993
25.4k
                return S->getString().startswith(Prefix);
994
25.4k
              });
995
16.8k
      }
996
16.8k
      if (!IsVectorMetadata)
997
16.7k
        MDs.push_back(Op);
998
16.8k
    }
999
14.5k
  }
1000
35.3k
1001
35.3k
  // Add metadata to avoid reapplying a transformation, such as
1002
35.3k
  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1003
35.3k
  MDs.append(AddAttrs.begin(), AddAttrs.end());
1004
35.3k
1005
35.3k
  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1006
35.3k
  // Replace the temporary node with a self-reference.
1007
35.3k
  NewLoopID->replaceOperandWith(0, NewLoopID);
1008
35.3k
  return NewLoopID;
1009
35.3k
}
1010
1011
//===----------------------------------------------------------------------===//
1012
// LoopInfo implementation
1013
//
1014
1015
char LoopInfoWrapperPass::ID = 0;
1016
102k
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1017
102k
                      true, true)
1018
102k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1019
102k
INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1020
                    true, true)
1021
1022
7.17M
bool LoopInfoWrapperPass::runOnFunction(Function &) {
1023
7.17M
  releaseMemory();
1024
7.17M
  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1025
7.17M
  return false;
1026
7.17M
}
1027
1028
0
void LoopInfoWrapperPass::verifyAnalysis() const {
1029
0
  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1030
0
  // function each time verifyAnalysis is called is very expensive. The
1031
0
  // -verify-loop-info option can enable this. In order to perform some
1032
0
  // checking by default, LoopPass has been taught to call verifyLoop manually
1033
0
  // during loop pass sequences.
1034
0
  if (VerifyLoopInfo) {
1035
0
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1036
0
    LI.verify(DT);
1037
0
  }
1038
0
}
1039
1040
344k
void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1041
344k
  AU.setPreservesAll();
1042
344k
  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1043
344k
}
1044
1045
8
void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
1046
8
  LI.print(OS);
1047
8
}
1048
1049
PreservedAnalyses LoopVerifierPass::run(Function &F,
1050
146
                                        FunctionAnalysisManager &AM) {
1051
146
  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1052
146
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1053
146
  LI.verify(DT);
1054
146
  return PreservedAnalyses::all();
1055
146
}
1056
1057
//===----------------------------------------------------------------------===//
1058
// LoopBlocksDFS implementation
1059
//
1060
1061
/// Traverse the loop blocks and store the DFS result.
1062
/// Useful for clients that just want the final DFS result and don't need to
1063
/// visit blocks during the initial traversal.
1064
852k
void LoopBlocksDFS::perform(LoopInfo *LI) {
1065
852k
  LoopBlocksTraversal Traversal(*this, LI);
1066
852k
  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1067
852k
                                        POE = Traversal.end();
1068
4.13M
       POI != POE; 
++POI3.27M
)
1069
3.27M
    ;
1070
852k
}