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