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