Bug Summary

File:lib/Analysis/LoopInfo.cpp
Location:line 548, column 24
Description:Called C++ object pointer is null

Annotated Source Code

1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
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// This file defines the LoopInfo class that is used to identify natural loops
11// and determine the loop depth of various nodes of the CFG. Note that the
12// loops identified may actually be several natural loops that share the same
13// header node... not just a single natural loop.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/ADT/DepthFirstIterator.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/LoopInfoImpl.h"
21#include "llvm/Analysis/LoopIterator.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/CFG.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/Instructions.h"
27#include "llvm/IR/LLVMContext.h"
28#include "llvm/IR/Metadata.h"
29#include "llvm/IR/PassManager.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/raw_ostream.h"
33#include <algorithm>
34using namespace llvm;
35
36// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
37template class llvm::LoopBase<BasicBlock, Loop>;
38template class llvm::LoopInfoBase<BasicBlock, Loop>;
39
40// Always verify loopinfo if expensive checking is enabled.
41#ifdef XDEBUG
42static bool VerifyLoopInfo = true;
43#else
44static bool VerifyLoopInfo = false;
45#endif
46static cl::opt<bool,true>
47VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
48 cl::desc("Verify loop info (time consuming)"));
49
50//===----------------------------------------------------------------------===//
51// Loop implementation
52//
53
54bool Loop::isLoopInvariant(const Value *V) const {
55 if (const Instruction *I = dyn_cast<Instruction>(V))
56 return !contains(I);
57 return true; // All non-instructions are loop invariant
58}
59
60bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
61 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
62}
63
64bool Loop::makeLoopInvariant(Value *V, bool &Changed,
65 Instruction *InsertPt) const {
66 if (Instruction *I = dyn_cast<Instruction>(V))
67 return makeLoopInvariant(I, Changed, InsertPt);
68 return true; // All non-instructions are loop-invariant.
69}
70
71bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
72 Instruction *InsertPt) const {
73 // Test if the value is already loop-invariant.
74 if (isLoopInvariant(I))
75 return true;
76 if (!isSafeToSpeculativelyExecute(I))
77 return false;
78 if (I->mayReadFromMemory())
79 return false;
80 // EH block instructions are immobile.
81 if (I->isEHPad())
82 return false;
83 // Determine the insertion point, unless one was given.
84 if (!InsertPt) {
85 BasicBlock *Preheader = getLoopPreheader();
86 // Without a preheader, hoisting is not feasible.
87 if (!Preheader)
88 return false;
89 InsertPt = Preheader->getTerminator();
90 }
91 // Don't hoist instructions with loop-variant operands.
92 for (Value *Operand : I->operands())
93 if (!makeLoopInvariant(Operand, Changed, InsertPt))
94 return false;
95
96 // Hoist.
97 I->moveBefore(InsertPt);
98
99 // There is possibility of hoisting this instruction above some arbitrary
100 // condition. Any metadata defined on it can be control dependent on this
101 // condition. Conservatively strip it here so that we don't give any wrong
102 // information to the optimizer.
103 I->dropUnknownNonDebugMetadata();
104
105 Changed = true;
106 return true;
107}
108
109PHINode *Loop::getCanonicalInductionVariable() const {
110 BasicBlock *H = getHeader();
111
112 BasicBlock *Incoming = nullptr, *Backedge = nullptr;
113 pred_iterator PI = pred_begin(H);
114 assert(PI != pred_end(H) &&((PI != pred_end(H) && "Loop must have at least one backedge!"
) ? static_cast<void> (0) : __assert_fail ("PI != pred_end(H) && \"Loop must have at least one backedge!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 115, __PRETTY_FUNCTION__))
115 "Loop must have at least one backedge!")((PI != pred_end(H) && "Loop must have at least one backedge!"
) ? static_cast<void> (0) : __assert_fail ("PI != pred_end(H) && \"Loop must have at least one backedge!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 115, __PRETTY_FUNCTION__))
;
116 Backedge = *PI++;
117 if (PI == pred_end(H)) return nullptr; // dead loop
118 Incoming = *PI++;
119 if (PI != pred_end(H)) return nullptr; // multiple backedges?
120
121 if (contains(Incoming)) {
122 if (contains(Backedge))
123 return nullptr;
124 std::swap(Incoming, Backedge);
125 } else if (!contains(Backedge))
126 return nullptr;
127
128 // Loop over all of the PHI nodes, looking for a canonical indvar.
129 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
130 PHINode *PN = cast<PHINode>(I);
131 if (ConstantInt *CI =
132 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
133 if (CI->isNullValue())
134 if (Instruction *Inc =
135 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
136 if (Inc->getOpcode() == Instruction::Add &&
137 Inc->getOperand(0) == PN)
138 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
139 if (CI->equalsInt(1))
140 return PN;
141 }
142 return nullptr;
143}
144
145bool Loop::isLCSSAForm(DominatorTree &DT) const {
146 for (BasicBlock *BB : this->blocks()) {
147 for (Instruction &I : *BB) {
148 // Tokens can't be used in PHI nodes and live-out tokens prevent loop
149 // optimizations, so for the purposes of considered LCSSA form, we
150 // can ignore them.
151 if (I.getType()->isTokenTy())
152 continue;
153
154 for (Use &U : I.uses()) {
155 Instruction *UI = cast<Instruction>(U.getUser());
156 BasicBlock *UserBB = UI->getParent();
157 if (PHINode *P = dyn_cast<PHINode>(UI))
158 UserBB = P->getIncomingBlock(U);
159
160 // Check the current block, as a fast-path, before checking whether
161 // the use is anywhere in the loop. Most values are used in the same
162 // block they are defined in. Also, blocks not reachable from the
163 // entry are special; uses in them don't need to go through PHIs.
164 if (UserBB != BB &&
165 !contains(UserBB) &&
166 DT.isReachableFromEntry(UserBB))
167 return false;
168 }
169 }
170 }
171
172 return true;
173}
174
175bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
176 if (!isLCSSAForm(DT))
177 return false;
178
179 return std::all_of(begin(), end(), [&](const Loop *L) {
180 return L->isRecursivelyLCSSAForm(DT);
181 });
182}
183
184bool Loop::isLoopSimplifyForm() const {
185 // Normal-form loops have a preheader, a single backedge, and all of their
186 // exits have all their predecessors inside the loop.
187 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
188}
189
190// Routines that reform the loop CFG and split edges often fail on indirectbr.
191bool Loop::isSafeToClone() const {
192 // Return false if any loop blocks contain indirectbrs, or there are any calls
193 // to noduplicate functions.
194 for (BasicBlock *BB : this->blocks()) {
195 if (isa<IndirectBrInst>(BB->getTerminator()))
196 return false;
197
198 if (const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
199 if (II->cannotDuplicate())
200 return false;
201 // Return false if any loop blocks contain invokes to EH-pads other than
202 // landingpads; we don't know how to split those edges yet.
203 auto *FirstNonPHI = II->getUnwindDest()->getFirstNonPHI();
204 if (FirstNonPHI->isEHPad() && !isa<LandingPadInst>(FirstNonPHI))
205 return false;
206 }
207 for (Instruction &I : *BB) {
208 if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
209 if (CI->cannotDuplicate())
210 return false;
211 }
212 if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
213 return false;
214 }
215 }
216 return true;
217}
218
219MDNode *Loop::getLoopID() const {
220 MDNode *LoopID = nullptr;
221 if (isLoopSimplifyForm()) {
222 LoopID = getLoopLatch()->getTerminator()->getMetadata(LLVMContext::MD_loop);
223 } else {
224 // Go through each predecessor of the loop header and check the
225 // terminator for the metadata.
226 BasicBlock *H = getHeader();
227 for (BasicBlock *BB : this->blocks()) {
228 TerminatorInst *TI = BB->getTerminator();
229 MDNode *MD = nullptr;
230
231 // Check if this terminator branches to the loop header.
232 for (BasicBlock *Successor : TI->successors()) {
233 if (Successor == H) {
234 MD = TI->getMetadata(LLVMContext::MD_loop);
235 break;
236 }
237 }
238 if (!MD)
239 return nullptr;
240
241 if (!LoopID)
242 LoopID = MD;
243 else if (MD != LoopID)
244 return nullptr;
245 }
246 }
247 if (!LoopID || LoopID->getNumOperands() == 0 ||
248 LoopID->getOperand(0) != LoopID)
249 return nullptr;
250 return LoopID;
251}
252
253void Loop::setLoopID(MDNode *LoopID) const {
254 assert(LoopID && "Loop ID should not be null")((LoopID && "Loop ID should not be null") ? static_cast
<void> (0) : __assert_fail ("LoopID && \"Loop ID should not be null\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 254, __PRETTY_FUNCTION__))
;
255 assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand")((LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getNumOperands() > 0 && \"Loop ID needs at least one operand\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 255, __PRETTY_FUNCTION__))
;
256 assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself")((LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getOperand(0) == LoopID && \"Loop ID should refer to itself\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 256, __PRETTY_FUNCTION__))
;
257
258 if (isLoopSimplifyForm()) {
259 getLoopLatch()->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
260 return;
261 }
262
263 BasicBlock *H = getHeader();
264 for (BasicBlock *BB : this->blocks()) {
265 TerminatorInst *TI = BB->getTerminator();
266 for (BasicBlock *Successor : TI->successors()) {
267 if (Successor == H)
268 TI->setMetadata(LLVMContext::MD_loop, LoopID);
269 }
270 }
271}
272
273bool Loop::isAnnotatedParallel() const {
274 MDNode *DesiredLoopIdMetadata = getLoopID();
275
276 if (!DesiredLoopIdMetadata)
277 return false;
278
279 // The loop branch contains the parallel loop metadata. In order to ensure
280 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
281 // dependencies (thus converted the loop back to a sequential loop), check
282 // that all the memory instructions in the loop contain parallelism metadata
283 // that point to the same unique "loop id metadata" the loop branch does.
284 for (BasicBlock *BB : this->blocks()) {
285 for (Instruction &I : *BB) {
286 if (!I.mayReadOrWriteMemory())
287 continue;
288
289 // The memory instruction can refer to the loop identifier metadata
290 // directly or indirectly through another list metadata (in case of
291 // nested parallel loops). The loop identifier metadata refers to
292 // itself so we can check both cases with the same routine.
293 MDNode *LoopIdMD =
294 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
295
296 if (!LoopIdMD)
297 return false;
298
299 bool LoopIdMDFound = false;
300 for (const MDOperand &MDOp : LoopIdMD->operands()) {
301 if (MDOp == DesiredLoopIdMetadata) {
302 LoopIdMDFound = true;
303 break;
304 }
305 }
306
307 if (!LoopIdMDFound)
308 return false;
309 }
310 }
311 return true;
312}
313
314bool Loop::hasDedicatedExits() const {
315 // Each predecessor of each exit block of a normal loop is contained
316 // within the loop.
317 SmallVector<BasicBlock *, 4> ExitBlocks;
318 getExitBlocks(ExitBlocks);
319 for (BasicBlock *BB : ExitBlocks)
320 for (BasicBlock *Predecessor : predecessors(BB))
321 if (!contains(Predecessor))
322 return false;
323 // All the requirements are met.
324 return true;
325}
326
327void
328Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
329 assert(hasDedicatedExits() &&((hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"
) ? static_cast<void> (0) : __assert_fail ("hasDedicatedExits() && \"getUniqueExitBlocks assumes the loop has canonical form exits!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 330, __PRETTY_FUNCTION__))
330 "getUniqueExitBlocks assumes the loop has canonical form exits!")((hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"
) ? static_cast<void> (0) : __assert_fail ("hasDedicatedExits() && \"getUniqueExitBlocks assumes the loop has canonical form exits!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 330, __PRETTY_FUNCTION__))
;
331
332 SmallVector<BasicBlock *, 32> SwitchExitBlocks;
333 for (BasicBlock *BB : this->blocks()) {
334 SwitchExitBlocks.clear();
335 for (BasicBlock *Successor : successors(BB)) {
336 // If block is inside the loop then it is not an exit block.
337 if (contains(Successor))
338 continue;
339
340 pred_iterator PI = pred_begin(Successor);
341 BasicBlock *FirstPred = *PI;
342
343 // If current basic block is this exit block's first predecessor
344 // then only insert exit block in to the output ExitBlocks vector.
345 // This ensures that same exit block is not inserted twice into
346 // ExitBlocks vector.
347 if (BB != FirstPred)
348 continue;
349
350 // If a terminator has more then two successors, for example SwitchInst,
351 // then it is possible that there are multiple edges from current block
352 // to one exit block.
353 if (std::distance(succ_begin(BB), succ_end(BB)) <= 2) {
354 ExitBlocks.push_back(Successor);
355 continue;
356 }
357
358 // In case of multiple edges from current block to exit block, collect
359 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
360 // duplicate edges.
361 if (std::find(SwitchExitBlocks.begin(), SwitchExitBlocks.end(), Successor)
362 == SwitchExitBlocks.end()) {
363 SwitchExitBlocks.push_back(Successor);
364 ExitBlocks.push_back(Successor);
365 }
366 }
367 }
368}
369
370BasicBlock *Loop::getUniqueExitBlock() const {
371 SmallVector<BasicBlock *, 8> UniqueExitBlocks;
372 getUniqueExitBlocks(UniqueExitBlocks);
373 if (UniqueExitBlocks.size() == 1)
374 return UniqueExitBlocks[0];
375 return nullptr;
376}
377
378#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
379LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dump() const {
380 print(dbgs());
381}
382#endif
383
384//===----------------------------------------------------------------------===//
385// UnloopUpdater implementation
386//
387
388namespace {
389/// Find the new parent loop for all blocks within the "unloop" whose last
390/// backedges has just been removed.
391class UnloopUpdater {
392 Loop *Unloop;
393 LoopInfo *LI;
394
395 LoopBlocksDFS DFS;
396
397 // Map unloop's immediate subloops to their nearest reachable parents. Nested
398 // loops within these subloops will not change parents. However, an immediate
399 // subloop's new parent will be the nearest loop reachable from either its own
400 // exits *or* any of its nested loop's exits.
401 DenseMap<Loop*, Loop*> SubloopParents;
402
403 // Flag the presence of an irreducible backedge whose destination is a block
404 // directly contained by the original unloop.
405 bool FoundIB;
406
407public:
408 UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
409 Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {}
410
411 void updateBlockParents();
412
413 void removeBlocksFromAncestors();
414
415 void updateSubloopParents();
416
417protected:
418 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
419};
420} // end anonymous namespace
421
422/// Update the parent loop for all blocks that are directly contained within the
423/// original "unloop".
424void UnloopUpdater::updateBlockParents() {
425 if (Unloop->getNumBlocks()) {
426 // Perform a post order CFG traversal of all blocks within this loop,
427 // propagating the nearest loop from sucessors to predecessors.
428 LoopBlocksTraversal Traversal(DFS, LI);
429 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
430 POE = Traversal.end(); POI != POE; ++POI) {
431
432 Loop *L = LI->getLoopFor(*POI);
433 Loop *NL = getNearestLoop(*POI, L);
434
435 if (NL != L) {
436 // For reducible loops, NL is now an ancestor of Unloop.
437 assert((NL != Unloop && (!NL || NL->contains(Unloop))) &&(((NL != Unloop && (!NL || NL->contains(Unloop))) &&
"uninitialized successor") ? static_cast<void> (0) : __assert_fail
("(NL != Unloop && (!NL || NL->contains(Unloop))) && \"uninitialized successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 438, __PRETTY_FUNCTION__))
438 "uninitialized successor")(((NL != Unloop && (!NL || NL->contains(Unloop))) &&
"uninitialized successor") ? static_cast<void> (0) : __assert_fail
("(NL != Unloop && (!NL || NL->contains(Unloop))) && \"uninitialized successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 438, __PRETTY_FUNCTION__))
;
439 LI->changeLoopFor(*POI, NL);
440 }
441 else {
442 // Or the current block is part of a subloop, in which case its parent
443 // is unchanged.
444 assert((FoundIB || Unloop->contains(L)) && "uninitialized successor")(((FoundIB || Unloop->contains(L)) && "uninitialized successor"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || Unloop->contains(L)) && \"uninitialized successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 444, __PRETTY_FUNCTION__))
;
445 }
446 }
447 }
448 // Each irreducible loop within the unloop induces a round of iteration using
449 // the DFS result cached by Traversal.
450 bool Changed = FoundIB;
451 for (unsigned NIters = 0; Changed; ++NIters) {
452 assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm")((NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"
) ? static_cast<void> (0) : __assert_fail ("NIters < Unloop->getNumBlocks() && \"runaway iterative algorithm\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 452, __PRETTY_FUNCTION__))
;
453
454 // Iterate over the postorder list of blocks, propagating the nearest loop
455 // from successors to predecessors as before.
456 Changed = false;
457 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
458 POE = DFS.endPostorder(); POI != POE; ++POI) {
459
460 Loop *L = LI->getLoopFor(*POI);
461 Loop *NL = getNearestLoop(*POI, L);
462 if (NL != L) {
463 assert(NL != Unloop && (!NL || NL->contains(Unloop)) &&((NL != Unloop && (!NL || NL->contains(Unloop)) &&
"uninitialized successor") ? static_cast<void> (0) : __assert_fail
("NL != Unloop && (!NL || NL->contains(Unloop)) && \"uninitialized successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 464, __PRETTY_FUNCTION__))
464 "uninitialized successor")((NL != Unloop && (!NL || NL->contains(Unloop)) &&
"uninitialized successor") ? static_cast<void> (0) : __assert_fail
("NL != Unloop && (!NL || NL->contains(Unloop)) && \"uninitialized successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 464, __PRETTY_FUNCTION__))
;
465 LI->changeLoopFor(*POI, NL);
466 Changed = true;
467 }
468 }
469 }
470}
471
472/// Remove unloop's blocks from all ancestors below their new parents.
473void UnloopUpdater::removeBlocksFromAncestors() {
474 // Remove all unloop's blocks (including those in nested subloops) from
475 // ancestors below the new parent loop.
476 for (Loop::block_iterator BI = Unloop->block_begin(),
477 BE = Unloop->block_end(); BI != BE; ++BI) {
478 Loop *OuterParent = LI->getLoopFor(*BI);
479 if (Unloop->contains(OuterParent)) {
480 while (OuterParent->getParentLoop() != Unloop)
481 OuterParent = OuterParent->getParentLoop();
482 OuterParent = SubloopParents[OuterParent];
483 }
484 // Remove blocks from former Ancestors except Unloop itself which will be
485 // deleted.
486 for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
487 OldParent = OldParent->getParentLoop()) {
488 assert(OldParent && "new loop is not an ancestor of the original")((OldParent && "new loop is not an ancestor of the original"
) ? static_cast<void> (0) : __assert_fail ("OldParent && \"new loop is not an ancestor of the original\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 488, __PRETTY_FUNCTION__))
;
489 OldParent->removeBlockFromLoop(*BI);
490 }
491 }
492}
493
494/// Update the parent loop for all subloops directly nested within unloop.
495void UnloopUpdater::updateSubloopParents() {
496 while (!Unloop->empty()) {
497 Loop *Subloop = *std::prev(Unloop->end());
498 Unloop->removeChildLoop(std::prev(Unloop->end()));
499
500 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop")((SubloopParents.count(Subloop) && "DFS failed to visit subloop"
) ? static_cast<void> (0) : __assert_fail ("SubloopParents.count(Subloop) && \"DFS failed to visit subloop\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 500, __PRETTY_FUNCTION__))
;
501 if (Loop *Parent = SubloopParents[Subloop])
502 Parent->addChildLoop(Subloop);
503 else
504 LI->addTopLevelLoop(Subloop);
505 }
506}
507
508/// Return the nearest parent loop among this block's successors. If a successor
509/// is a subloop header, consider its parent to be the nearest parent of the
510/// subloop's exits.
511///
512/// For subloop blocks, simply update SubloopParents and return NULL.
513Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
514
515 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
516 // is considered uninitialized.
517 Loop *NearLoop = BBLoop;
518
519 Loop *Subloop = nullptr;
520 if (NearLoop != Unloop && Unloop->contains(NearLoop)) {
521 Subloop = NearLoop;
522 // Find the subloop ancestor that is directly contained within Unloop.
523 while (Subloop->getParentLoop() != Unloop) {
524 Subloop = Subloop->getParentLoop();
525 assert(Subloop && "subloop is not an ancestor of the original loop")((Subloop && "subloop is not an ancestor of the original loop"
) ? static_cast<void> (0) : __assert_fail ("Subloop && \"subloop is not an ancestor of the original loop\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 525, __PRETTY_FUNCTION__))
;
526 }
527 // Get the current nearest parent of the Subloop exits, initially Unloop.
528 NearLoop =
529 SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second;
530 }
531
532 succ_iterator I = succ_begin(BB), E = succ_end(BB);
533 if (I == E) {
1
Taking false branch
534 assert(!Subloop && "subloop blocks must have a successor")((!Subloop && "subloop blocks must have a successor")
? static_cast<void> (0) : __assert_fail ("!Subloop && \"subloop blocks must have a successor\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 534, __PRETTY_FUNCTION__))
;
535 NearLoop = nullptr; // unloop blocks may now exit the function.
536 }
537 for (; I != E; ++I) {
2
Loop condition is true. Entering loop body
7
Loop condition is true. Entering loop body
15
Loop condition is true. Entering loop body
538 if (*I == BB)
3
Taking false branch
8
Taking false branch
16
Taking false branch
539 continue; // self loops are uninteresting
540
541 Loop *L = LI->getLoopFor(*I);
542 if (L == Unloop) {
4
Taking false branch
9
Taking false branch
17
Taking false branch
543 // This successor has not been processed. This path must lead to an
544 // irreducible backedge.
545 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB")(((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || !DFS.hasPostorder(*I)) && \"should have seen IB\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 545, __PRETTY_FUNCTION__))
;
546 FoundIB = true;
547 }
548 if (L != Unloop && Unloop->contains(L)) {
5
Taking false branch
10
Taking true branch
18
Called C++ object pointer is null
549 // Successor is in a subloop.
550 if (Subloop)
11
Taking false branch
551 continue; // Branching within subloops. Ignore it.
552
553 // BB branches from the original into a subloop header.
554 assert(L->getParentLoop() == Unloop && "cannot skip into nested loops")((L->getParentLoop() == Unloop && "cannot skip into nested loops"
) ? static_cast<void> (0) : __assert_fail ("L->getParentLoop() == Unloop && \"cannot skip into nested loops\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 554, __PRETTY_FUNCTION__))
;
555
556 // Get the current nearest parent of the Subloop's exits.
557 L = SubloopParents[L];
12
Value assigned to field 'Unloop'
558 // L could be Unloop if the only exit was an irreducible backedge.
559 }
560 if (L == Unloop) {
6
Taking false branch
13
Taking false branch
561 continue;
562 }
563 // Handle critical edges from Unloop into a sibling loop.
564 if (L && !L->contains(Unloop)) {
565 L = L->getParentLoop();
566 }
567 // Remember the nearest parent loop among successors or subloop exits.
568 if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L))
14
Assuming pointer value is null
569 NearLoop = L;
570 }
571 if (Subloop) {
572 SubloopParents[Subloop] = NearLoop;
573 return BBLoop;
574 }
575 return NearLoop;
576}
577
578LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) {
579 analyze(DomTree);
580}
581
582void LoopInfo::markAsRemoved(Loop *Unloop) {
583 assert(!Unloop->isInvalid() && "Loop has already been removed")((!Unloop->isInvalid() && "Loop has already been removed"
) ? static_cast<void> (0) : __assert_fail ("!Unloop->isInvalid() && \"Loop has already been removed\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 583, __PRETTY_FUNCTION__))
;
584 Unloop->invalidate();
585 RemovedLoops.push_back(Unloop);
586
587 // First handle the special case of no parent loop to simplify the algorithm.
588 if (!Unloop->getParentLoop()) {
589 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
590 for (Loop::block_iterator I = Unloop->block_begin(),
591 E = Unloop->block_end();
592 I != E; ++I) {
593
594 // Don't reparent blocks in subloops.
595 if (getLoopFor(*I) != Unloop)
596 continue;
597
598 // Blocks no longer have a parent but are still referenced by Unloop until
599 // the Unloop object is deleted.
600 changeLoopFor(*I, nullptr);
601 }
602
603 // Remove the loop from the top-level LoopInfo object.
604 for (iterator I = begin();; ++I) {
605 assert(I != end() && "Couldn't find loop")((I != end() && "Couldn't find loop") ? static_cast<
void> (0) : __assert_fail ("I != end() && \"Couldn't find loop\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 605, __PRETTY_FUNCTION__))
;
606 if (*I == Unloop) {
607 removeLoop(I);
608 break;
609 }
610 }
611
612 // Move all of the subloops to the top-level.
613 while (!Unloop->empty())
614 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
615
616 return;
617 }
618
619 // Update the parent loop for all blocks within the loop. Blocks within
620 // subloops will not change parents.
621 UnloopUpdater Updater(Unloop, this);
622 Updater.updateBlockParents();
623
624 // Remove blocks from former ancestor loops.
625 Updater.removeBlocksFromAncestors();
626
627 // Add direct subloops as children in their new parent loop.
628 Updater.updateSubloopParents();
629
630 // Remove unloop from its parent loop.
631 Loop *ParentLoop = Unloop->getParentLoop();
632 for (Loop::iterator I = ParentLoop->begin();; ++I) {
633 assert(I != ParentLoop->end() && "Couldn't find loop")((I != ParentLoop->end() && "Couldn't find loop") ?
static_cast<void> (0) : __assert_fail ("I != ParentLoop->end() && \"Couldn't find loop\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Analysis/LoopInfo.cpp"
, 633, __PRETTY_FUNCTION__))
;
634 if (*I == Unloop) {
635 ParentLoop->removeChildLoop(I);
636 break;
637 }
638 }
639}
640
641char LoopAnalysis::PassID;
642
643LoopInfo LoopAnalysis::run(Function &F, AnalysisManager<Function> &AM) {
644 // FIXME: Currently we create a LoopInfo from scratch for every function.
645 // This may prove to be too wasteful due to deallocating and re-allocating
646 // memory each time for the underlying map and vector datastructures. At some
647 // point it may prove worthwhile to use a freelist and recycle LoopInfo
648 // objects. I don't want to add that kind of complexity until the scope of
649 // the problem is better understood.
650 LoopInfo LI;
651 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
652 return LI;
653}
654
655PreservedAnalyses LoopPrinterPass::run(Function &F,
656 AnalysisManager<Function> &AM) {
657 AM.getResult<LoopAnalysis>(F).print(OS);
658 return PreservedAnalyses::all();
659}
660
661PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
662PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
663 : OS(OS), Banner(Banner) {}
664
665PreservedAnalyses PrintLoopPass::run(Loop &L) {
666 OS << Banner;
667 for (auto *Block : L.blocks())
668 if (Block)
669 Block->print(OS);
670 else
671 OS << "Printing <null> block";
672 return PreservedAnalyses::all();
673}
674
675//===----------------------------------------------------------------------===//
676// LoopInfo implementation
677//
678
679char LoopInfoWrapperPass::ID = 0;
680INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void* initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
681 true, true)static void* initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
682INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
683INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",PassInfo *PI = new PassInfo("Natural Loop Information", "loops"
, & LoopInfoWrapperPass ::ID, PassInfo::NormalCtor_t(callDefaultCtor
< LoopInfoWrapperPass >), true, true); Registry.registerPass
(*PI, true); return PI; } void llvm::initializeLoopInfoWrapperPassPass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopInfoWrapperPassPassOnce
(Registry); sys::MemoryFence(); ; ; initialized = 2; ; } else
{ sys::cas_flag tmp = initialized; sys::MemoryFence(); while
(tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
684 true, true)PassInfo *PI = new PassInfo("Natural Loop Information", "loops"
, & LoopInfoWrapperPass ::ID, PassInfo::NormalCtor_t(callDefaultCtor
< LoopInfoWrapperPass >), true, true); Registry.registerPass
(*PI, true); return PI; } void llvm::initializeLoopInfoWrapperPassPass
(PassRegistry &Registry) { static volatile sys::cas_flag initialized
= 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized
, 1, 0); if (old_val == 0) { initializeLoopInfoWrapperPassPassOnce
(Registry); sys::MemoryFence(); ; ; initialized = 2; ; } else
{ sys::cas_flag tmp = initialized; sys::MemoryFence(); while
(tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; }
685
686bool LoopInfoWrapperPass::runOnFunction(Function &) {
687 releaseMemory();
688 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
689 return false;
690}
691
692void LoopInfoWrapperPass::verifyAnalysis() const {
693 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
694 // function each time verifyAnalysis is called is very expensive. The
695 // -verify-loop-info option can enable this. In order to perform some
696 // checking by default, LoopPass has been taught to call verifyLoop manually
697 // during loop pass sequences.
698 if (VerifyLoopInfo)
699 LI.verify();
700}
701
702void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
703 AU.setPreservesAll();
704 AU.addRequired<DominatorTreeWrapperPass>();
705}
706
707void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
708 LI.print(OS);
709}
710
711//===----------------------------------------------------------------------===//
712// LoopBlocksDFS implementation
713//
714
715/// Traverse the loop blocks and store the DFS result.
716/// Useful for clients that just want the final DFS result and don't need to
717/// visit blocks during the initial traversal.
718void LoopBlocksDFS::perform(LoopInfo *LI) {
719 LoopBlocksTraversal Traversal(*this, LI);
720 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
721 POE = Traversal.end(); POI != POE; ++POI) ;
722}