File: | lib/Analysis/LoopInfo.cpp |
Location: | line 548, column 24 |
Description: | Called C++ object pointer is null |
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> | |||
34 | using namespace llvm; | |||
35 | ||||
36 | // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. | |||
37 | template class llvm::LoopBase<BasicBlock, Loop>; | |||
38 | template class llvm::LoopInfoBase<BasicBlock, Loop>; | |||
39 | ||||
40 | // Always verify loopinfo if expensive checking is enabled. | |||
41 | #ifdef XDEBUG | |||
42 | static bool VerifyLoopInfo = true; | |||
43 | #else | |||
44 | static bool VerifyLoopInfo = false; | |||
45 | #endif | |||
46 | static cl::opt<bool,true> | |||
47 | VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), | |||
48 | cl::desc("Verify loop info (time consuming)")); | |||
49 | ||||
50 | //===----------------------------------------------------------------------===// | |||
51 | // Loop implementation | |||
52 | // | |||
53 | ||||
54 | bool 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 | ||||
60 | bool Loop::hasLoopInvariantOperands(const Instruction *I) const { | |||
61 | return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); }); | |||
62 | } | |||
63 | ||||
64 | bool 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 | ||||
71 | bool 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 | ||||
109 | PHINode *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 | ||||
145 | bool 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 | ||||
175 | bool 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 | ||||
184 | bool 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. | |||
191 | bool 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 | ||||
219 | MDNode *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 | ||||
253 | void 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 | ||||
273 | bool 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 | ||||
314 | bool 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 | ||||
327 | void | |||
328 | Loop::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 | ||||
370 | BasicBlock *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) | |||
379 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dump() const { | |||
380 | print(dbgs()); | |||
381 | } | |||
382 | #endif | |||
383 | ||||
384 | //===----------------------------------------------------------------------===// | |||
385 | // UnloopUpdater implementation | |||
386 | // | |||
387 | ||||
388 | namespace { | |||
389 | /// Find the new parent loop for all blocks within the "unloop" whose last | |||
390 | /// backedges has just been removed. | |||
391 | class 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 | ||||
407 | public: | |||
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 | ||||
417 | protected: | |||
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". | |||
424 | void 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. | |||
473 | void 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. | |||
495 | void 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. | |||
513 | Loop *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) { | |||
| ||||
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) { | |||
538 | if (*I == BB) | |||
539 | continue; // self loops are uninteresting | |||
540 | ||||
541 | Loop *L = LI->getLoopFor(*I); | |||
542 | if (L == Unloop) { | |||
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)) { | |||
| ||||
549 | // Successor is in a subloop. | |||
550 | if (Subloop) | |||
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]; | |||
558 | // L could be Unloop if the only exit was an irreducible backedge. | |||
559 | } | |||
560 | if (L == Unloop) { | |||
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)) | |||
569 | NearLoop = L; | |||
570 | } | |||
571 | if (Subloop) { | |||
572 | SubloopParents[Subloop] = NearLoop; | |||
573 | return BBLoop; | |||
574 | } | |||
575 | return NearLoop; | |||
576 | } | |||
577 | ||||
578 | LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) { | |||
579 | analyze(DomTree); | |||
580 | } | |||
581 | ||||
582 | void 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 | ||||
641 | char LoopAnalysis::PassID; | |||
642 | ||||
643 | LoopInfo 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 | ||||
655 | PreservedAnalyses LoopPrinterPass::run(Function &F, | |||
656 | AnalysisManager<Function> &AM) { | |||
657 | AM.getResult<LoopAnalysis>(F).print(OS); | |||
658 | return PreservedAnalyses::all(); | |||
659 | } | |||
660 | ||||
661 | PrintLoopPass::PrintLoopPass() : OS(dbgs()) {} | |||
662 | PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner) | |||
663 | : OS(OS), Banner(Banner) {} | |||
664 | ||||
665 | PreservedAnalyses 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 | ||||
679 | char LoopInfoWrapperPass::ID = 0; | |||
680 | INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void* initializeLoopInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
681 | true, true)static void* initializeLoopInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
682 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
683 | INITIALIZE_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 | ||||
686 | bool LoopInfoWrapperPass::runOnFunction(Function &) { | |||
687 | releaseMemory(); | |||
688 | LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); | |||
689 | return false; | |||
690 | } | |||
691 | ||||
692 | void 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 | ||||
702 | void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
703 | AU.setPreservesAll(); | |||
704 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
705 | } | |||
706 | ||||
707 | void 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. | |||
718 | void LoopBlocksDFS::perform(LoopInfo *LI) { | |||
719 | LoopBlocksTraversal Traversal(*this, LI); | |||
720 | for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), | |||
721 | POE = Traversal.end(); POI != POE; ++POI) ; | |||
722 | } |