Add an isLoopSimplifyForm() predicate, following the example of
[oota-llvm.git] / include / llvm / Analysis / LoopInfo.h
1 //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
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 natural
12 // loops may actually be several loops that share the same header node.
13 //
14 // This analysis calculates the nesting structure of loops in a function.  For
15 // each natural loop identified, this analysis identifies natural loops
16 // contained entirely within the loop and the basic blocks the make up the loop.
17 //
18 // It can calculate on the fly various bits of information, for example:
19 //
20 //  * whether there is a preheader for the loop
21 //  * the number of back edges to the header
22 //  * whether or not a particular block branches out of the loop
23 //  * the successor blocks of the loop
24 //  * the loop depth
25 //  * the trip count
26 //  * etc...
27 //
28 //===----------------------------------------------------------------------===//
29
30 #ifndef LLVM_ANALYSIS_LOOP_INFO_H
31 #define LLVM_ANALYSIS_LOOP_INFO_H
32
33 #include "llvm/Pass.h"
34 #include "llvm/ADT/DepthFirstIterator.h"
35 #include "llvm/ADT/GraphTraits.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/Analysis/Dominators.h"
38 #include "llvm/Support/CFG.h"
39 #include "llvm/Support/Streams.h"
40 #include <algorithm>
41 #include <ostream>
42
43 namespace llvm {
44
45 template<typename T>
46 static void RemoveFromVector(std::vector<T*> &V, T *N) {
47   typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
48   assert(I != V.end() && "N is not in this list!");
49   V.erase(I);
50 }
51
52 class DominatorTree;
53 class LoopInfo;
54 class Loop;
55 template<class N, class M> class LoopInfoBase;
56 template<class N, class M> class LoopBase;
57
58 //===----------------------------------------------------------------------===//
59 /// LoopBase class - Instances of this class are used to represent loops that
60 /// are detected in the flow graph
61 ///
62 template<class BlockT, class LoopT>
63 class LoopBase {
64   LoopT *ParentLoop;
65   // SubLoops - Loops contained entirely within this one.
66   std::vector<LoopT *> SubLoops;
67
68   // Blocks - The list of blocks in this loop.  First entry is the header node.
69   std::vector<BlockT*> Blocks;
70
71   // DO NOT IMPLEMENT
72   LoopBase(const LoopBase<BlockT, LoopT> &);
73   // DO NOT IMPLEMENT
74   const LoopBase<BlockT, LoopT>&operator=(const LoopBase<BlockT, LoopT> &);
75 public:
76   /// Loop ctor - This creates an empty loop.
77   LoopBase() : ParentLoop(0) {}
78   ~LoopBase() {
79     for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
80       delete SubLoops[i];
81   }
82
83   /// getLoopDepth - Return the nesting level of this loop.  An outer-most
84   /// loop has depth 1, for consistency with loop depth values used for basic
85   /// blocks, where depth 0 is used for blocks not inside any loops.
86   unsigned getLoopDepth() const {
87     unsigned D = 1;
88     for (const LoopT *CurLoop = ParentLoop; CurLoop;
89          CurLoop = CurLoop->ParentLoop)
90       ++D;
91     return D;
92   }
93   BlockT *getHeader() const { return Blocks.front(); }
94   LoopT *getParentLoop() const { return ParentLoop; }
95
96   /// contains - Return true if the specified basic block is in this loop
97   ///
98   bool contains(const BlockT *BB) const {
99     return std::find(block_begin(), block_end(), BB) != block_end();
100   }
101
102   /// iterator/begin/end - Return the loops contained entirely within this loop.
103   ///
104   const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
105   typedef typename std::vector<LoopT *>::const_iterator iterator;
106   iterator begin() const { return SubLoops.begin(); }
107   iterator end() const { return SubLoops.end(); }
108   bool empty() const { return SubLoops.empty(); }
109
110   /// getBlocks - Get a list of the basic blocks which make up this loop.
111   ///
112   const std::vector<BlockT*> &getBlocks() const { return Blocks; }
113   typedef typename std::vector<BlockT*>::const_iterator block_iterator;
114   block_iterator block_begin() const { return Blocks.begin(); }
115   block_iterator block_end() const { return Blocks.end(); }
116
117   /// isLoopExit - True if terminator in the block can branch to another block
118   /// that is outside of the current loop.
119   ///
120   bool isLoopExit(const BlockT *BB) const {
121     typedef GraphTraits<BlockT*> BlockTraits;
122     for (typename BlockTraits::ChildIteratorType SI =
123          BlockTraits::child_begin(const_cast<BlockT*>(BB)),
124          SE = BlockTraits::child_end(const_cast<BlockT*>(BB)); SI != SE; ++SI) {
125       if (!contains(*SI))
126         return true;
127     }
128     return false;
129   }
130
131   /// getNumBackEdges - Calculate the number of back edges to the loop header
132   ///
133   unsigned getNumBackEdges() const {
134     unsigned NumBackEdges = 0;
135     BlockT *H = getHeader();
136
137     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
138     for (typename InvBlockTraits::ChildIteratorType I =
139          InvBlockTraits::child_begin(const_cast<BlockT*>(H)),
140          E = InvBlockTraits::child_end(const_cast<BlockT*>(H)); I != E; ++I)
141       if (contains(*I))
142         ++NumBackEdges;
143
144     return NumBackEdges;
145   }
146
147   //===--------------------------------------------------------------------===//
148   // APIs for simple analysis of the loop.
149   //
150   // Note that all of these methods can fail on general loops (ie, there may not
151   // be a preheader, etc).  For best success, the loop simplification and
152   // induction variable canonicalization pass should be used to normalize loops
153   // for easy analysis.  These methods assume canonical loops.
154
155   /// getExitingBlocks - Return all blocks inside the loop that have successors
156   /// outside of the loop.  These are the blocks _inside of the current loop_
157   /// which branch out.  The returned list is always unique.
158   ///
159   void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
160     // Sort the blocks vector so that we can use binary search to do quick
161     // lookups.
162     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
163     std::sort(LoopBBs.begin(), LoopBBs.end());
164
165     typedef GraphTraits<BlockT*> BlockTraits;
166     for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
167       for (typename BlockTraits::ChildIteratorType I =
168           BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
169           I != E; ++I)
170         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
171           // Not in current loop? It must be an exit block.
172           ExitingBlocks.push_back(*BI);
173           break;
174         }
175   }
176
177   /// getExitingBlock - If getExitingBlocks would return exactly one block,
178   /// return that block. Otherwise return null.
179   BlockT *getExitingBlock() const {
180     SmallVector<BlockT*, 8> ExitingBlocks;
181     getExitingBlocks(ExitingBlocks);
182     if (ExitingBlocks.size() == 1)
183       return ExitingBlocks[0];
184     return 0;
185   }
186
187   /// getExitBlocks - Return all of the successor blocks of this loop.  These
188   /// are the blocks _outside of the current loop_ which are branched to.
189   ///
190   void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
191     // Sort the blocks vector so that we can use binary search to do quick
192     // lookups.
193     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
194     std::sort(LoopBBs.begin(), LoopBBs.end());
195
196     typedef GraphTraits<BlockT*> BlockTraits;
197     for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
198       for (typename BlockTraits::ChildIteratorType I =
199            BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
200            I != E; ++I)
201         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
202           // Not in current loop? It must be an exit block.
203           ExitBlocks.push_back(*I);
204   }
205
206   /// getExitBlock - If getExitBlocks would return exactly one block,
207   /// return that block. Otherwise return null.
208   BlockT *getExitBlock() const {
209     SmallVector<BlockT*, 8> ExitBlocks;
210     getExitBlocks(ExitBlocks);
211     if (ExitBlocks.size() == 1)
212       return ExitBlocks[0];
213     return 0;
214   }
215
216   /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 
217   /// These are the blocks _outside of the current loop_ which are branched to.
218   /// This assumes that loop is in canonical form.
219   ///
220   void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
221     // Sort the blocks vector so that we can use binary search to do quick
222     // lookups.
223     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
224     std::sort(LoopBBs.begin(), LoopBBs.end());
225
226     std::vector<BlockT*> switchExitBlocks;  
227
228     for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) {
229
230       BlockT *current = *BI;
231       switchExitBlocks.clear();
232
233       typedef GraphTraits<BlockT*> BlockTraits;
234       typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
235       for (typename BlockTraits::ChildIteratorType I =
236            BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
237            I != E; ++I) {
238         if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
239       // If block is inside the loop then it is not a exit block.
240           continue;
241       
242         typename InvBlockTraits::ChildIteratorType PI =
243                                                 InvBlockTraits::child_begin(*I);
244         BlockT *firstPred = *PI;
245
246         // If current basic block is this exit block's first predecessor
247         // then only insert exit block in to the output ExitBlocks vector.
248         // This ensures that same exit block is not inserted twice into
249         // ExitBlocks vector.
250         if (current != firstPred) 
251           continue;
252
253         // If a terminator has more then two successors, for example SwitchInst,
254         // then it is possible that there are multiple edges from current block 
255         // to one exit block. 
256         if (std::distance(BlockTraits::child_begin(current),
257                           BlockTraits::child_end(current)) <= 2) {
258           ExitBlocks.push_back(*I);
259           continue;
260         }
261
262         // In case of multiple edges from current block to exit block, collect
263         // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
264         // duplicate edges.
265         if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 
266             == switchExitBlocks.end()) {
267           switchExitBlocks.push_back(*I);
268           ExitBlocks.push_back(*I);
269         }
270       }
271     }
272   }
273
274   /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one
275   /// block, return that block. Otherwise return null.
276   BlockT *getUniqueExitBlock() const {
277     SmallVector<BlockT*, 8> UniqueExitBlocks;
278     getUniqueExitBlocks(UniqueExitBlocks);
279     if (UniqueExitBlocks.size() == 1)
280       return UniqueExitBlocks[0];
281     return 0;
282   }
283
284   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
285   /// loop has a preheader if there is only one edge to the header of the loop
286   /// from outside of the loop.  If this is the case, the block branching to the
287   /// header of the loop is the preheader node.
288   ///
289   /// This method returns null if there is no preheader for the loop.
290   ///
291   BlockT *getLoopPreheader() const {
292     // Keep track of nodes outside the loop branching to the header...
293     BlockT *Out = 0;
294
295     // Loop over the predecessors of the header node...
296     BlockT *Header = getHeader();
297     typedef GraphTraits<BlockT*> BlockTraits;
298     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
299     for (typename InvBlockTraits::ChildIteratorType PI =
300          InvBlockTraits::child_begin(Header),
301          PE = InvBlockTraits::child_end(Header); PI != PE; ++PI)
302       if (!contains(*PI)) {     // If the block is not in the loop...
303         if (Out && Out != *PI)
304           return 0;             // Multiple predecessors outside the loop
305         Out = *PI;
306       }
307
308     // Make sure there is only one exit out of the preheader.
309     assert(Out && "Header of loop has no predecessors from outside loop?");
310     typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
311     ++SI;
312     if (SI != BlockTraits::child_end(Out))
313       return 0;  // Multiple exits from the block, must not be a preheader.
314
315     // If there is exactly one preheader, return it.  If there was zero, then
316     // Out is still null.
317     return Out;
318   }
319
320   /// getLoopLatch - If there is a single latch block for this loop, return it.
321   /// A latch block is a block that contains a branch back to the header.
322   /// A loop header in normal form has two edges into it: one from a preheader
323   /// and one from a latch block.
324   BlockT *getLoopLatch() const {
325     BlockT *Header = getHeader();
326     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
327     typename InvBlockTraits::ChildIteratorType PI =
328                                             InvBlockTraits::child_begin(Header);
329     typename InvBlockTraits::ChildIteratorType PE =
330                                               InvBlockTraits::child_end(Header);
331     if (PI == PE) return 0;  // no preds?
332
333     BlockT *Latch = 0;
334     if (contains(*PI))
335       Latch = *PI;
336     ++PI;
337     if (PI == PE) return 0;  // only one pred?
338
339     if (contains(*PI)) {
340       if (Latch) return 0;  // multiple backedges
341       Latch = *PI;
342     }
343     ++PI;
344     if (PI != PE) return 0;  // more than two preds
345
346     return Latch;
347   }
348
349   //===--------------------------------------------------------------------===//
350   // APIs for updating loop information after changing the CFG
351   //
352
353   /// addBasicBlockToLoop - This method is used by other analyses to update loop
354   /// information.  NewBB is set to be a new member of the current loop.
355   /// Because of this, it is added as a member of all parent loops, and is added
356   /// to the specified LoopInfo object as being in the current basic block.  It
357   /// is not valid to replace the loop header with this method.
358   ///
359   void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
360
361   /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
362   /// the OldChild entry in our children list with NewChild, and updates the
363   /// parent pointer of OldChild to be null and the NewChild to be this loop.
364   /// This updates the loop depth of the new child.
365   void replaceChildLoopWith(LoopT *OldChild,
366                             LoopT *NewChild) {
367     assert(OldChild->ParentLoop == this && "This loop is already broken!");
368     assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
369     typename std::vector<LoopT *>::iterator I =
370                           std::find(SubLoops.begin(), SubLoops.end(), OldChild);
371     assert(I != SubLoops.end() && "OldChild not in loop!");
372     *I = NewChild;
373     OldChild->ParentLoop = 0;
374     NewChild->ParentLoop = static_cast<LoopT *>(this);
375   }
376
377   /// addChildLoop - Add the specified loop to be a child of this loop.  This
378   /// updates the loop depth of the new child.
379   ///
380   void addChildLoop(LoopT *NewChild) {
381     assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
382     NewChild->ParentLoop = static_cast<LoopT *>(this);
383     SubLoops.push_back(NewChild);
384   }
385
386   /// removeChildLoop - This removes the specified child from being a subloop of
387   /// this loop.  The loop is not deleted, as it will presumably be inserted
388   /// into another loop.
389   LoopT *removeChildLoop(iterator I) {
390     assert(I != SubLoops.end() && "Cannot remove end iterator!");
391     LoopT *Child = *I;
392     assert(Child->ParentLoop == this && "Child is not a child of this loop!");
393     SubLoops.erase(SubLoops.begin()+(I-begin()));
394     Child->ParentLoop = 0;
395     return Child;
396   }
397
398   /// addBlockEntry - This adds a basic block directly to the basic block list.
399   /// This should only be used by transformations that create new loops.  Other
400   /// transformations should use addBasicBlockToLoop.
401   void addBlockEntry(BlockT *BB) {
402     Blocks.push_back(BB);
403   }
404
405   /// moveToHeader - This method is used to move BB (which must be part of this
406   /// loop) to be the loop header of the loop (the block that dominates all
407   /// others).
408   void moveToHeader(BlockT *BB) {
409     if (Blocks[0] == BB) return;
410     for (unsigned i = 0; ; ++i) {
411       assert(i != Blocks.size() && "Loop does not contain BB!");
412       if (Blocks[i] == BB) {
413         Blocks[i] = Blocks[0];
414         Blocks[0] = BB;
415         return;
416       }
417     }
418   }
419
420   /// removeBlockFromLoop - This removes the specified basic block from the
421   /// current loop, updating the Blocks as appropriate.  This does not update
422   /// the mapping in the LoopInfo class.
423   void removeBlockFromLoop(BlockT *BB) {
424     RemoveFromVector(Blocks, BB);
425   }
426
427   /// verifyLoop - Verify loop structure
428   void verifyLoop() const {
429 #ifndef NDEBUG
430     assert (getHeader() && "Loop header is missing");
431     assert (getLoopPreheader() && "Loop preheader is missing");
432     assert (getLoopLatch() && "Loop latch is missing");
433     for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
434       (*I)->verifyLoop();
435 #endif
436   }
437
438   void print(std::ostream &OS, unsigned Depth = 0) const {
439     OS << std::string(Depth*2, ' ') << "Loop at depth " << getLoopDepth()
440        << " containing: ";
441
442     for (unsigned i = 0; i < getBlocks().size(); ++i) {
443       if (i) OS << ",";
444       BlockT *BB = getBlocks()[i];
445       WriteAsOperand(OS, BB, false);
446       if (BB == getHeader())    OS << "<header>";
447       if (BB == getLoopLatch()) OS << "<latch>";
448       if (isLoopExit(BB))       OS << "<exit>";
449     }
450     OS << "\n";
451
452     for (iterator I = begin(), E = end(); I != E; ++I)
453       (*I)->print(OS, Depth+2);
454   }
455   
456   void print(std::ostream *O, unsigned Depth = 0) const {
457     if (O) print(*O, Depth);
458   }
459   
460   void dump() const {
461     print(cerr);
462   }
463   
464 protected:
465   friend class LoopInfoBase<BlockT, LoopT>;
466   explicit LoopBase(BlockT *BB) : ParentLoop(0) {
467     Blocks.push_back(BB);
468   }
469 };
470
471 class Loop : public LoopBase<BasicBlock, Loop> {
472 public:
473   Loop() {}
474
475   /// isLoopInvariant - Return true if the specified value is loop invariant
476   ///
477   bool isLoopInvariant(Value *V) const;
478
479   /// isLoopInvariant - Return true if the specified instruction is
480   /// loop-invariant.
481   ///
482   bool isLoopInvariant(Instruction *I) const;
483
484   /// makeLoopInvariant - If the given value is an instruction inside of the
485   /// loop and it can be hoisted, do so to make it trivially loop-invariant.
486   /// Return true if the value after any hoisting is loop invariant. This
487   /// function can be used as a slightly more aggressive replacement for
488   /// isLoopInvariant.
489   ///
490   /// If InsertPt is specified, it is the point to hoist instructions to.
491   /// If null, the terminator of the loop preheader is used.
492   ///
493   bool makeLoopInvariant(Value *V, bool &Changed,
494                          Instruction *InsertPt = 0) const;
495
496   /// makeLoopInvariant - If the given instruction is inside of the
497   /// loop and it can be hoisted, do so to make it trivially loop-invariant.
498   /// Return true if the instruction after any hoisting is loop invariant. This
499   /// function can be used as a slightly more aggressive replacement for
500   /// isLoopInvariant.
501   ///
502   /// If InsertPt is specified, it is the point to hoist instructions to.
503   /// If null, the terminator of the loop preheader is used.
504   ///
505   bool makeLoopInvariant(Instruction *I, bool &Changed,
506                          Instruction *InsertPt = 0) const;
507
508   /// getCanonicalInductionVariable - Check to see if the loop has a canonical
509   /// induction variable: an integer recurrence that starts at 0 and increments
510   /// by one each time through the loop.  If so, return the phi node that
511   /// corresponds to it.
512   ///
513   /// The IndVarSimplify pass transforms loops to have a canonical induction
514   /// variable.
515   ///
516   PHINode *getCanonicalInductionVariable() const;
517
518   /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds
519   /// the canonical induction variable value for the "next" iteration of the
520   /// loop.  This always succeeds if getCanonicalInductionVariable succeeds.
521   ///
522   Instruction *getCanonicalInductionVariableIncrement() const;
523
524   /// getTripCount - Return a loop-invariant LLVM value indicating the number of
525   /// times the loop will be executed.  Note that this means that the backedge
526   /// of the loop executes N-1 times.  If the trip-count cannot be determined,
527   /// this returns null.
528   ///
529   /// The IndVarSimplify pass transforms loops to have a form that this
530   /// function easily understands.
531   ///
532   Value *getTripCount() const;
533
534   /// getSmallConstantTripCount - Returns the trip count of this loop as a
535   /// normal unsigned value, if possible. Returns 0 if the trip count is unknown
536   /// of not constant. Will also return 0 if the trip count is very large
537   /// (>= 2^32)
538   unsigned getSmallConstantTripCount() const;
539
540   /// getSmallConstantTripMultiple - Returns the largest constant divisor of the
541   /// trip count of this loop as a normal unsigned value, if possible. This
542   /// means that the actual trip count is always a multiple of the returned
543   /// value (don't forget the trip count could very well be zero as well!).
544   ///
545   /// Returns 1 if the trip count is unknown or not guaranteed to be the
546   /// multiple of a constant (which is also the case if the trip count is simply
547   /// constant, use getSmallConstantTripCount for that case), Will also return 1
548   /// if the trip count is very large (>= 2^32).
549   unsigned getSmallConstantTripMultiple() const;
550
551   /// isLCSSAForm - Return true if the Loop is in LCSSA form
552   bool isLCSSAForm() const;
553
554   /// isLoopSimplifyForm - Return true if the Loop is in the form that
555   /// the LoopSimplify form transforms loops to, which is sometimes called
556   /// normal form.
557   bool isLoopSimplifyForm() const;
558
559 private:
560   friend class LoopInfoBase<BasicBlock, Loop>;
561   explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
562 };
563
564 //===----------------------------------------------------------------------===//
565 /// LoopInfo - This class builds and contains all of the top level loop
566 /// structures in the specified function.
567 ///
568
569 template<class BlockT, class LoopT>
570 class LoopInfoBase {
571   // BBMap - Mapping of basic blocks to the inner most loop they occur in
572   std::map<BlockT *, LoopT *> BBMap;
573   std::vector<LoopT *> TopLevelLoops;
574   friend class LoopBase<BlockT, LoopT>;
575
576   void operator=(const LoopInfoBase &); // do not implement
577   LoopInfoBase(const LoopInfo &);       // do not implement
578 public:
579   LoopInfoBase() { }
580   ~LoopInfoBase() { releaseMemory(); }
581   
582   void releaseMemory() {
583     for (typename std::vector<LoopT *>::iterator I =
584          TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I)
585       delete *I;   // Delete all of the loops...
586
587     BBMap.clear();                           // Reset internal state of analysis
588     TopLevelLoops.clear();
589   }
590   
591   /// iterator/begin/end - The interface to the top-level loops in the current
592   /// function.
593   ///
594   typedef typename std::vector<LoopT *>::const_iterator iterator;
595   iterator begin() const { return TopLevelLoops.begin(); }
596   iterator end() const { return TopLevelLoops.end(); }
597   bool empty() const { return TopLevelLoops.empty(); }
598   
599   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
600   /// block is in no loop (for example the entry node), null is returned.
601   ///
602   LoopT *getLoopFor(const BlockT *BB) const {
603     typename std::map<BlockT *, LoopT *>::const_iterator I=
604       BBMap.find(const_cast<BlockT*>(BB));
605     return I != BBMap.end() ? I->second : 0;
606   }
607   
608   /// operator[] - same as getLoopFor...
609   ///
610   const LoopT *operator[](const BlockT *BB) const {
611     return getLoopFor(BB);
612   }
613   
614   /// getLoopDepth - Return the loop nesting level of the specified block.  A
615   /// depth of 0 means the block is not inside any loop.
616   ///
617   unsigned getLoopDepth(const BlockT *BB) const {
618     const LoopT *L = getLoopFor(BB);
619     return L ? L->getLoopDepth() : 0;
620   }
621
622   // isLoopHeader - True if the block is a loop header node
623   bool isLoopHeader(BlockT *BB) const {
624     const LoopT *L = getLoopFor(BB);
625     return L && L->getHeader() == BB;
626   }
627   
628   /// removeLoop - This removes the specified top-level loop from this loop info
629   /// object.  The loop is not deleted, as it will presumably be inserted into
630   /// another loop.
631   LoopT *removeLoop(iterator I) {
632     assert(I != end() && "Cannot remove end iterator!");
633     LoopT *L = *I;
634     assert(L->getParentLoop() == 0 && "Not a top-level loop!");
635     TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
636     return L;
637   }
638   
639   /// changeLoopFor - Change the top-level loop that contains BB to the
640   /// specified loop.  This should be used by transformations that restructure
641   /// the loop hierarchy tree.
642   void changeLoopFor(BlockT *BB, LoopT *L) {
643     LoopT *&OldLoop = BBMap[BB];
644     assert(OldLoop && "Block not in a loop yet!");
645     OldLoop = L;
646   }
647   
648   /// changeTopLevelLoop - Replace the specified loop in the top-level loops
649   /// list with the indicated loop.
650   void changeTopLevelLoop(LoopT *OldLoop,
651                           LoopT *NewLoop) {
652     typename std::vector<LoopT *>::iterator I =
653                  std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop);
654     assert(I != TopLevelLoops.end() && "Old loop not at top level!");
655     *I = NewLoop;
656     assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
657            "Loops already embedded into a subloop!");
658   }
659   
660   /// addTopLevelLoop - This adds the specified loop to the collection of
661   /// top-level loops.
662   void addTopLevelLoop(LoopT *New) {
663     assert(New->getParentLoop() == 0 && "Loop already in subloop!");
664     TopLevelLoops.push_back(New);
665   }
666   
667   /// removeBlock - This method completely removes BB from all data structures,
668   /// including all of the Loop objects it is nested in and our mapping from
669   /// BasicBlocks to loops.
670   void removeBlock(BlockT *BB) {
671     typename std::map<BlockT *, LoopT *>::iterator I = BBMap.find(BB);
672     if (I != BBMap.end()) {
673       for (LoopT *L = I->second; L; L = L->getParentLoop())
674         L->removeBlockFromLoop(BB);
675
676       BBMap.erase(I);
677     }
678   }
679   
680   // Internals
681   
682   static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
683                                       const LoopT *ParentLoop) {
684     if (SubLoop == 0) return true;
685     if (SubLoop == ParentLoop) return false;
686     return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
687   }
688   
689   void Calculate(DominatorTreeBase<BlockT> &DT) {
690     BlockT *RootNode = DT.getRootNode()->getBlock();
691
692     for (df_iterator<BlockT*> NI = df_begin(RootNode),
693            NE = df_end(RootNode); NI != NE; ++NI)
694       if (LoopT *L = ConsiderForLoop(*NI, DT))
695         TopLevelLoops.push_back(L);
696   }
697   
698   LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
699     if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node?
700
701     std::vector<BlockT *> TodoStack;
702
703     // Scan the predecessors of BB, checking to see if BB dominates any of
704     // them.  This identifies backedges which target this node...
705     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
706     for (typename InvBlockTraits::ChildIteratorType I =
707          InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
708          I != E; ++I)
709       if (DT.dominates(BB, *I))   // If BB dominates it's predecessor...
710         TodoStack.push_back(*I);
711
712     if (TodoStack.empty()) return 0;  // No backedges to this block...
713
714     // Create a new loop to represent this basic block...
715     LoopT *L = new LoopT(BB);
716     BBMap[BB] = L;
717
718     BlockT *EntryBlock = BB->getParent()->begin();
719
720     while (!TodoStack.empty()) {  // Process all the nodes in the loop
721       BlockT *X = TodoStack.back();
722       TodoStack.pop_back();
723
724       if (!L->contains(X) &&         // As of yet unprocessed??
725           DT.dominates(EntryBlock, X)) {   // X is reachable from entry block?
726         // Check to see if this block already belongs to a loop.  If this occurs
727         // then we have a case where a loop that is supposed to be a child of
728         // the current loop was processed before the current loop.  When this
729         // occurs, this child loop gets added to a part of the current loop,
730         // making it a sibling to the current loop.  We have to reparent this
731         // loop.
732         if (LoopT *SubLoop =
733             const_cast<LoopT *>(getLoopFor(X)))
734           if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
735             // Remove the subloop from it's current parent...
736             assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
737             LoopT *SLP = SubLoop->ParentLoop;  // SubLoopParent
738             typename std::vector<LoopT *>::iterator I =
739               std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
740             assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
741             SLP->SubLoops.erase(I);   // Remove from parent...
742
743             // Add the subloop to THIS loop...
744             SubLoop->ParentLoop = L;
745             L->SubLoops.push_back(SubLoop);
746           }
747
748         // Normal case, add the block to our loop...
749         L->Blocks.push_back(X);
750         
751         typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
752         
753         // Add all of the predecessors of X to the end of the work stack...
754         TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
755                          InvBlockTraits::child_end(X));
756       }
757     }
758
759     // If there are any loops nested within this loop, create them now!
760     for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
761          E = L->Blocks.end(); I != E; ++I)
762       if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {
763         L->SubLoops.push_back(NewLoop);
764         NewLoop->ParentLoop = L;
765       }
766
767     // Add the basic blocks that comprise this loop to the BBMap so that this
768     // loop can be found for them.
769     //
770     for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
771            E = L->Blocks.end(); I != E; ++I) {
772       typename std::map<BlockT*, LoopT *>::iterator BBMI = BBMap.find(*I);
773       if (BBMI == BBMap.end())                       // Not in map yet...
774         BBMap.insert(BBMI, std::make_pair(*I, L));   // Must be at this level
775     }
776
777     // Now that we have a list of all of the child loops of this loop, check to
778     // see if any of them should actually be nested inside of each other.  We
779     // can accidentally pull loops our of their parents, so we must make sure to
780     // organize the loop nests correctly now.
781     {
782       std::map<BlockT *, LoopT *> ContainingLoops;
783       for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
784         LoopT *Child = L->SubLoops[i];
785         assert(Child->getParentLoop() == L && "Not proper child loop?");
786
787         if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
788           // If there is already a loop which contains this loop, move this loop
789           // into the containing loop.
790           MoveSiblingLoopInto(Child, ContainingLoop);
791           --i;  // The loop got removed from the SubLoops list.
792         } else {
793           // This is currently considered to be a top-level loop.  Check to see
794           // if any of the contained blocks are loop headers for subloops we
795           // have already processed.
796           for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
797             LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
798             if (BlockLoop == 0) {   // Child block not processed yet...
799               BlockLoop = Child;
800             } else if (BlockLoop != Child) {
801               LoopT *SubLoop = BlockLoop;
802               // Reparent all of the blocks which used to belong to BlockLoops
803               for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j)
804                 ContainingLoops[SubLoop->Blocks[j]] = Child;
805
806               // There is already a loop which contains this block, that means
807               // that we should reparent the loop which the block is currently
808               // considered to belong to to be a child of this loop.
809               MoveSiblingLoopInto(SubLoop, Child);
810               --i;  // We just shrunk the SubLoops list.
811             }
812           }
813         }
814       }
815     }
816
817     return L;
818   }
819   
820   /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
821   /// of the NewParent Loop, instead of being a sibling of it.
822   void MoveSiblingLoopInto(LoopT *NewChild,
823                            LoopT *NewParent) {
824     LoopT *OldParent = NewChild->getParentLoop();
825     assert(OldParent && OldParent == NewParent->getParentLoop() &&
826            NewChild != NewParent && "Not sibling loops!");
827
828     // Remove NewChild from being a child of OldParent
829     typename std::vector<LoopT *>::iterator I =
830       std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
831                 NewChild);
832     assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
833     OldParent->SubLoops.erase(I);   // Remove from parent's subloops list
834     NewChild->ParentLoop = 0;
835
836     InsertLoopInto(NewChild, NewParent);
837   }
838   
839   /// InsertLoopInto - This inserts loop L into the specified parent loop.  If
840   /// the parent loop contains a loop which should contain L, the loop gets
841   /// inserted into L instead.
842   void InsertLoopInto(LoopT *L, LoopT *Parent) {
843     BlockT *LHeader = L->getHeader();
844     assert(Parent->contains(LHeader) &&
845            "This loop should not be inserted here!");
846
847     // Check to see if it belongs in a child loop...
848     for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
849          i != e; ++i)
850       if (Parent->SubLoops[i]->contains(LHeader)) {
851         InsertLoopInto(L, Parent->SubLoops[i]);
852         return;
853       }
854
855     // If not, insert it here!
856     Parent->SubLoops.push_back(L);
857     L->ParentLoop = Parent;
858   }
859   
860   // Debugging
861   
862   void print(std::ostream &OS, const Module* ) const {
863     for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
864       TopLevelLoops[i]->print(OS);
865   #if 0
866     for (std::map<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
867            E = BBMap.end(); I != E; ++I)
868       OS << "BB '" << I->first->getName() << "' level = "
869          << I->second->getLoopDepth() << "\n";
870   #endif
871   }
872 };
873
874 class LoopInfo : public FunctionPass {
875   LoopInfoBase<BasicBlock, Loop> LI;
876   friend class LoopBase<BasicBlock, Loop>;
877
878   void operator=(const LoopInfo &); // do not implement
879   LoopInfo(const LoopInfo &);       // do not implement
880 public:
881   static char ID; // Pass identification, replacement for typeid
882
883   LoopInfo() : FunctionPass(&ID) {}
884
885   LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; }
886
887   /// iterator/begin/end - The interface to the top-level loops in the current
888   /// function.
889   ///
890   typedef LoopInfoBase<BasicBlock, Loop>::iterator iterator;
891   inline iterator begin() const { return LI.begin(); }
892   inline iterator end() const { return LI.end(); }
893   bool empty() const { return LI.empty(); }
894
895   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
896   /// block is in no loop (for example the entry node), null is returned.
897   ///
898   inline Loop *getLoopFor(const BasicBlock *BB) const {
899     return LI.getLoopFor(BB);
900   }
901
902   /// operator[] - same as getLoopFor...
903   ///
904   inline const Loop *operator[](const BasicBlock *BB) const {
905     return LI.getLoopFor(BB);
906   }
907
908   /// getLoopDepth - Return the loop nesting level of the specified block.  A
909   /// depth of 0 means the block is not inside any loop.
910   ///
911   inline unsigned getLoopDepth(const BasicBlock *BB) const {
912     return LI.getLoopDepth(BB);
913   }
914
915   // isLoopHeader - True if the block is a loop header node
916   inline bool isLoopHeader(BasicBlock *BB) const {
917     return LI.isLoopHeader(BB);
918   }
919
920   /// runOnFunction - Calculate the natural loop information.
921   ///
922   virtual bool runOnFunction(Function &F);
923
924   virtual void releaseMemory() { LI.releaseMemory(); }
925
926   virtual void print(std::ostream &O, const Module* M = 0) const {
927     LI.print(O, M);
928   }
929
930   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
931
932   /// removeLoop - This removes the specified top-level loop from this loop info
933   /// object.  The loop is not deleted, as it will presumably be inserted into
934   /// another loop.
935   inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); }
936
937   /// changeLoopFor - Change the top-level loop that contains BB to the
938   /// specified loop.  This should be used by transformations that restructure
939   /// the loop hierarchy tree.
940   inline void changeLoopFor(BasicBlock *BB, Loop *L) {
941     LI.changeLoopFor(BB, L);
942   }
943
944   /// changeTopLevelLoop - Replace the specified loop in the top-level loops
945   /// list with the indicated loop.
946   inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
947     LI.changeTopLevelLoop(OldLoop, NewLoop);
948   }
949
950   /// addTopLevelLoop - This adds the specified loop to the collection of
951   /// top-level loops.
952   inline void addTopLevelLoop(Loop *New) {
953     LI.addTopLevelLoop(New);
954   }
955
956   /// removeBlock - This method completely removes BB from all data structures,
957   /// including all of the Loop objects it is nested in and our mapping from
958   /// BasicBlocks to loops.
959   void removeBlock(BasicBlock *BB) {
960     LI.removeBlock(BB);
961   }
962
963   static bool isNotAlreadyContainedIn(const Loop *SubLoop,
964                                       const Loop *ParentLoop) {
965     return
966       LoopInfoBase<BasicBlock, Loop>::isNotAlreadyContainedIn(SubLoop,
967                                                               ParentLoop);
968   }
969 };
970
971
972 // Allow clients to walk the list of nested loops...
973 template <> struct GraphTraits<const Loop*> {
974   typedef const Loop NodeType;
975   typedef LoopInfo::iterator ChildIteratorType;
976
977   static NodeType *getEntryNode(const Loop *L) { return L; }
978   static inline ChildIteratorType child_begin(NodeType *N) {
979     return N->begin();
980   }
981   static inline ChildIteratorType child_end(NodeType *N) {
982     return N->end();
983   }
984 };
985
986 template <> struct GraphTraits<Loop*> {
987   typedef Loop NodeType;
988   typedef LoopInfo::iterator ChildIteratorType;
989
990   static NodeType *getEntryNode(Loop *L) { return L; }
991   static inline ChildIteratorType child_begin(NodeType *N) {
992     return N->begin();
993   }
994   static inline ChildIteratorType child_end(NodeType *N) {
995     return N->end();
996   }
997 };
998
999 template<class BlockT, class LoopT>
1000 void
1001 LoopBase<BlockT, LoopT>::addBasicBlockToLoop(BlockT *NewBB,
1002                                              LoopInfoBase<BlockT, LoopT> &LIB) {
1003   assert((Blocks.empty() || LIB[getHeader()] == this) &&
1004          "Incorrect LI specified for this loop!");
1005   assert(NewBB && "Cannot add a null basic block to the loop!");
1006   assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
1007
1008   LoopT *L = static_cast<LoopT *>(this);
1009
1010   // Add the loop mapping to the LoopInfo object...
1011   LIB.BBMap[NewBB] = L;
1012
1013   // Add the basic block to this loop and all parent loops...
1014   while (L) {
1015     L->Blocks.push_back(NewBB);
1016     L = L->getParentLoop();
1017   }
1018 }
1019
1020 } // End llvm namespace
1021
1022 #endif