LoopInfo.h revision 21c276d2fa99914d5ed958ac0aec7d78e3dd87cf
148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
29769ab22265b313171d201b5928688524a01bd87Misha Brukman//
36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//                     The LLVM Compiler Infrastructure
46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//
56fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// This file was developed by the LLVM research group and is distributed under
66fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details.
79769ab22265b313171d201b5928688524a01bd87Misha Brukman//
86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===//
90bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//
100bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner// This file defines the LoopInfo class that is used to identify natural loops
11fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// and determine the loop depth of various nodes of the CFG.  Note that natural
1246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner// loops may actually be several loops that share the same header node.
13fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner//
14fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// This analysis calculates the nesting structure of loops in a function.  For
15fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// each natural loop identified, this analysis identifies natural loops
16072b163424491c85df6664a4e056aae5e07dc64dChris Lattner// contained entirely within the loop and the basic blocks the make up the loop.
17fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner//
18072b163424491c85df6664a4e056aae5e07dc64dChris Lattner// It can calculate on the fly various bits of information, for example:
19072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//
20072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * whether there is a preheader for the loop
21072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * the number of back edges to the header
22072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * whether or not a particular block branches out of the loop
23072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * the successor blocks of the loop
24072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * the loop depth
25072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * the trip count
26072b163424491c85df6664a4e056aae5e07dc64dChris Lattner//  * etc...
270bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//
280bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===//
290bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
300bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#ifndef LLVM_ANALYSIS_LOOP_INFO_H
310bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#define LLVM_ANALYSIS_LOOP_INFO_H
320bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
33facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner#include "llvm/Pass.h"
34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h"
35b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel#include "llvm/ADT/SmallVector.h"
360bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm {
38d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke
3953c279b1949f7fa626ccbc399ebbe2d7dc9599a4Devang Patelclass DominatorTree;
408fc2f2072de83665ae20e06929e28317f449bcdfChris Lattnerclass LoopInfo;
41e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattnerclass PHINode;
4288d3ef2c744db0289223a4477669f24d542e6d97Chris Lattnerclass Instruction;
430bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
440bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===//
459769ab22265b313171d201b5928688524a01bd87Misha Brukman/// Loop class - Instances of this class are used to represent loops that are
469769ab22265b313171d201b5928688524a01bd87Misha Brukman/// detected in the flow graph
472b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner///
480bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerclass Loop {
490bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  Loop *ParentLoop;
50697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner  std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
517dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  std::vector<BasicBlock*> Blocks;   // First entry is the header node
520bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
530bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  Loop(const Loop &);                  // DO NOT IMPLEMENT
540bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
550bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic:
5646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// Loop ctor - This creates an empty loop.
57072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  Loop() : ParentLoop(0) {}
584e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  ~Loop() {
594e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner    for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
604e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner      delete SubLoops[i];
614e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  }
620bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
63072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  unsigned getLoopDepth() const {
64072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    unsigned D = 0;
65072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    for (const Loop *CurLoop = this; CurLoop; CurLoop = CurLoop->ParentLoop)
66072b163424491c85df6664a4e056aae5e07dc64dChris Lattner      ++D;
67072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    return D;
68072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  }
697dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  BasicBlock *getHeader() const { return Blocks.front(); }
707dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  Loop *getParentLoop() const { return ParentLoop; }
710bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
722b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// contains - Return true of the specified basic block is in this loop
73fbdf4bf1799bf9ea566fc0fc0507752590a6d559Misha Brukman  ///
74a51b767df42019eb155281f3a64a16593c14f7e9Chris Lattner  bool contains(const BasicBlock *BB) const;
750bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
76329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  /// iterator/begin/end - Return the loops contained entirely within this loop.
772b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
7821d6ff546d0c9cd1a631fe7940a3988a2472198cTanya Lattner  const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
79329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  typedef std::vector<Loop*>::const_iterator iterator;
80329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  iterator begin() const { return SubLoops.begin(); }
81329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  iterator end() const { return SubLoops.end(); }
8221c276d2fa99914d5ed958ac0aec7d78e3dd87cfDan Gohman  bool empty() const { return SubLoops.empty(); }
83fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner
84fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  /// getBlocks - Get a list of the basic blocks which make up this loop.
85fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  ///
86fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
874e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner  typedef std::vector<BasicBlock*>::const_iterator block_iterator;
884e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner  block_iterator block_begin() const { return Blocks.begin(); }
894e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner  block_iterator block_end() const { return Blocks.end(); }
90fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner
912b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// isLoopExit - True if terminator in the block can branch to another block
92f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  /// that is outside of the current loop.
93fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  ///
946b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman  bool isLoopExit(const BasicBlock *BB) const;
956b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman
96fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  /// getNumBackEdges - Calculate the number of back edges to the loop header
97fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  ///
986b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman  unsigned getNumBackEdges() const;
999474dd68e8a050193ca4003940ac399e2b17cb6aChris Lattner
10088d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner  /// isLoopInvariant - Return true if the specified value is loop invariant
10188d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner  ///
10288d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner  bool isLoopInvariant(Value *V) const;
103b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng
104e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  //===--------------------------------------------------------------------===//
105e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // APIs for simple analysis of the loop.
106e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  //
107e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // Note that all of these methods can fail on general loops (ie, there may not
108e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // be a preheader, etc).  For best success, the loop simplification and
109e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // induction variable canonicalization pass should be used to normalize loops
110e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // for easy analysis.  These methods assume canonical loops.
111e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner
1127466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner  /// getExitingBlocks - Return all blocks inside the loop that have successors
1137466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner  /// outside of the loop.  These are the blocks _inside of the current loop_
1147466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner  /// which branch out.  The returned list is always unique.
1157466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner  ///
1167c6c55db4df35c9e0bbff89ceec52b0504862d7dDevang Patel  void getExitingBlocks(SmallVectorImpl<BasicBlock *> &Blocks) const;
1177466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner
118f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  /// getExitBlocks - Return all of the successor blocks of this loop.  These
119f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  /// are the blocks _outside of the current loop_ which are branched to.
120f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  ///
1217c6c55db4df35c9e0bbff89ceec52b0504862d7dDevang Patel  void getExitBlocks(SmallVectorImpl<BasicBlock* > &Blocks) const;
122f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner
1234b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel  /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
1244b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel  /// These are the blocks _outside of the current loop_ which are branched to.
1254b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel  /// This assumes that loop is in canonical form.
1264b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel  ///
1277c6c55db4df35c9e0bbff89ceec52b0504862d7dDevang Patel  void getUniqueExitBlocks(SmallVectorImpl<BasicBlock*> &ExitBlocks) const;
1284b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel
1292b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// getLoopPreheader - If there is a preheader for this loop, return it.  A
1302b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// loop has a preheader if there is only one edge to the header of the loop
1312b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// from outside of the loop.  If this is the case, the block branching to the
132e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// header of the loop is the preheader node.
1332b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
134e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// This method returns null if there is no preheader for the loop.
1352b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
1362b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  BasicBlock *getLoopPreheader() const;
1372b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner
138331a1833e12b6229986f63f0a156062affbf3142Chris Lattner  /// getLoopLatch - If there is a latch block for this loop, return it.  A
139331a1833e12b6229986f63f0a156062affbf3142Chris Lattner  /// latch block is the canonical backedge for a loop.  A loop header in normal
140331a1833e12b6229986f63f0a156062affbf3142Chris Lattner  /// form has two edges into it: one from a preheader and one from a latch
141331a1833e12b6229986f63f0a156062affbf3142Chris Lattner  /// block.
142331a1833e12b6229986f63f0a156062affbf3142Chris Lattner  BasicBlock *getLoopLatch() const;
143331a1833e12b6229986f63f0a156062affbf3142Chris Lattner
144e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// getCanonicalInductionVariable - Check to see if the loop has a canonical
145e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// induction variable: an integer recurrence that starts at 0 and increments
146e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// by one each time through the loop.  If so, return the phi node that
147e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// corresponds to it.
148e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  ///
149e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  PHINode *getCanonicalInductionVariable() const;
150e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner
151e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds
152e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// the canonical induction variable value for the "next" iteration of the
153e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// loop.  This always succeeds if getCanonicalInductionVariable succeeds.
154e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  ///
155e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  Instruction *getCanonicalInductionVariableIncrement() const;
156e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner
157e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// getTripCount - Return a loop-invariant LLVM value indicating the number of
158e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// times the loop will be executed.  Note that this means that the backedge
159e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// of the loop executes N-1 times.  If the trip-count cannot be determined,
160e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  /// this returns null.
161e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  ///
162e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  Value *getTripCount() const;
163c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson
164c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson  /// isLCSSAForm - Return true if the Loop is in LCSSA form
165c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson  bool isLCSSAForm() const;
166e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner
167e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  //===--------------------------------------------------------------------===//
168e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  // APIs for updating loop information after changing the CFG
169e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner  //
170e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner
171fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  /// addBasicBlockToLoop - This method is used by other analyses to update loop
172fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner  /// information.  NewBB is set to be a new member of the current loop.
1732b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// Because of this, it is added as a member of all parent loops, and is added
1742b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// to the specified LoopInfo object as being in the current basic block.  It
1752b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// is not valid to replace the loop header with this method.
1762b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
1772b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI);
1782b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner
17946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
18046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// the OldChild entry in our children list with NewChild, and updates the
18146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// parent pointer of OldChild to be null and the NewChild to be this loop.
18246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// This updates the loop depth of the new child.
18346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void replaceChildLoopWith(Loop *OldChild, Loop *NewChild);
18446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
18546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// addChildLoop - Add the specified loop to be a child of this loop.  This
18646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// updates the loop depth of the new child.
18746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  ///
18846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void addChildLoop(Loop *NewChild);
18946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
19046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// removeChildLoop - This removes the specified child from being a subloop of
19146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// this loop.  The loop is not deleted, as it will presumably be inserted
19246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// into another loop.
19346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  Loop *removeChildLoop(iterator OldChild);
19446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
19546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// addBlockEntry - This adds a basic block directly to the basic block list.
19646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// This should only be used by transformations that create new loops.  Other
19746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// transformations should use addBasicBlockToLoop.
19846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void addBlockEntry(BasicBlock *BB) {
19946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner    Blocks.push_back(BB);
20046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  }
20146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
20251a4ad475b095aed49caff176b98c0754e421af4Chris Lattner  /// moveToHeader - This method is used to move BB (which must be part of this
20351a4ad475b095aed49caff176b98c0754e421af4Chris Lattner  /// loop) to be the loop header of the loop (the block that dominates all
20451a4ad475b095aed49caff176b98c0754e421af4Chris Lattner  /// others).
20551a4ad475b095aed49caff176b98c0754e421af4Chris Lattner  void moveToHeader(BasicBlock *BB) {
20651a4ad475b095aed49caff176b98c0754e421af4Chris Lattner    if (Blocks[0] == BB) return;
20751a4ad475b095aed49caff176b98c0754e421af4Chris Lattner    for (unsigned i = 0; ; ++i) {
20851a4ad475b095aed49caff176b98c0754e421af4Chris Lattner      assert(i != Blocks.size() && "Loop does not contain BB!");
20951a4ad475b095aed49caff176b98c0754e421af4Chris Lattner      if (Blocks[i] == BB) {
21051a4ad475b095aed49caff176b98c0754e421af4Chris Lattner        Blocks[i] = Blocks[0];
21151a4ad475b095aed49caff176b98c0754e421af4Chris Lattner        Blocks[0] = BB;
21251a4ad475b095aed49caff176b98c0754e421af4Chris Lattner        return;
21351a4ad475b095aed49caff176b98c0754e421af4Chris Lattner      }
21451a4ad475b095aed49caff176b98c0754e421af4Chris Lattner    }
21551a4ad475b095aed49caff176b98c0754e421af4Chris Lattner  }
21651a4ad475b095aed49caff176b98c0754e421af4Chris Lattner
21746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// removeBlockFromLoop - This removes the specified basic block from the
218f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  /// current loop, updating the Blocks as appropriate.  This does not update
219f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner  /// the mapping in the LoopInfo class.
22046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void removeBlockFromLoop(BasicBlock *BB);
22146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
22258e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel  /// verifyLoop - Verify loop structure
22358e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel  void verifyLoop() const;
22458e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel
2257dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  void print(std::ostream &O, unsigned Depth = 0) const;
2265c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling  void print(std::ostream *O, unsigned Depth = 0) const {
2275c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling    if (O) print(*O, Depth);
2285c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling  }
229f972cbd98c87a2b288943425c1bc92022a8de5c5Chris Lattner  void dump() const;
2300bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate:
2310bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  friend class LoopInfo;
23246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  Loop(BasicBlock *BB) : ParentLoop(0) {
233072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    Blocks.push_back(BB);
2340bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  }
2350bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner};
2360bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2370bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2380bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2390bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===//
2402b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// LoopInfo - This class builds and contains all of the top level loop
2412b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// structures in the specified function.
2422b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner///
243f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattnerclass LoopInfo : public FunctionPass {
2440bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  // BBMap - Mapping of basic blocks to the inner most loop they occur in
245a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner  std::map<BasicBlock*, Loop*> BBMap;
246697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner  std::vector<Loop*> TopLevelLoops;
2472b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  friend class Loop;
2480bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic:
249ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky  static char ID; // Pass identification, replacement for typeid
250794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel
251276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer  LoopInfo() : FunctionPass(intptr_t(&ID)) {}
252918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner  ~LoopInfo() { releaseMemory(); }
2530bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
254329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  /// iterator/begin/end - The interface to the top-level loops in the current
255329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  /// function.
256329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  ///
257329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  typedef std::vector<Loop*>::const_iterator iterator;
258329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  iterator begin() const { return TopLevelLoops.begin(); }
259329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner  iterator end() const { return TopLevelLoops.end(); }
2600bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2612b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
2622b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// block is in no loop (for example the entry node), null is returned.
2632b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
264072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  Loop *getLoopFor(const BasicBlock *BB) const {
265edd5d9ece15f73ec1a31423a4ae39774aa6c521cReid Spencer    std::map<BasicBlock *, Loop*>::const_iterator I=
266edd5d9ece15f73ec1a31423a4ae39774aa6c521cReid Spencer      BBMap.find(const_cast<BasicBlock*>(BB));
2670bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner    return I != BBMap.end() ? I->second : 0;
2680bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  }
2692b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner
2702b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// operator[] - same as getLoopFor...
2712b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
272072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  const Loop *operator[](const BasicBlock *BB) const {
2730bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner    return getLoopFor(BB);
2740bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  }
2750bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2762b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// getLoopDepth - Return the loop nesting level of the specified block...
2772b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
2787e70829632f82de15db187845666aaca6e04b792Chris Lattner  unsigned getLoopDepth(const BasicBlock *BB) const {
2790bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner    const Loop *L = getLoopFor(BB);
2800bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner    return L ? L->getLoopDepth() : 0;
2810bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  }
2820bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2830bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  // isLoopHeader - True if the block is a loop header node
284a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner  bool isLoopHeader(BasicBlock *BB) const {
28550f5490842d501e269a4c6085d0d132cae0d31f8Chris Lattner    const Loop *L = getLoopFor(BB);
28650f5490842d501e269a4c6085d0d132cae0d31f8Chris Lattner    return L && L->getHeader() == BB;
2870bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner  }
2880bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
2892b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  /// runOnFunction - Calculate the natural loop information.
2902b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner  ///
2917e70829632f82de15db187845666aaca6e04b792Chris Lattner  virtual bool runOnFunction(Function &F);
292facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner
293918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner  virtual void releaseMemory();
2945c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling
295ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer  void print(std::ostream &O, const Module* = 0) const;
2965c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling  void print(std::ostream *O, const Module* M = 0) const {
2975c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling    if (O) print(*O, M);
2985c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling  }
299918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner
300f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
301f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner
3024e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  /// removeLoop - This removes the specified top-level loop from this loop info
3034e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  /// object.  The loop is not deleted, as it will presumably be inserted into
3044e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  /// another loop.
3054e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner  Loop *removeLoop(iterator I);
3064e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner
30746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// changeLoopFor - Change the top-level loop that contains BB to the
30846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// specified loop.  This should be used by transformations that restructure
30946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// the loop hierarchy tree.
31046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void changeLoopFor(BasicBlock *BB, Loop *L);
31146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
31246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// changeTopLevelLoop - Replace the specified loop in the top-level loops
31346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  /// list with the indicated loop.
31446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner  void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop);
31546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner
316072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  /// addTopLevelLoop - This adds the specified loop to the collection of
317072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  /// top-level loops.
318072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  void addTopLevelLoop(Loop *New) {
319072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    assert(New->getParentLoop() == 0 && "Loop already in subloop!");
320072b163424491c85df6664a4e056aae5e07dc64dChris Lattner    TopLevelLoops.push_back(New);
321072b163424491c85df6664a4e056aae5e07dc64dChris Lattner  }
322072b163424491c85df6664a4e056aae5e07dc64dChris Lattner
3239afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner  /// removeBlock - This method completely removes BB from all data structures,
3249afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner  /// including all of the Loop objects it is nested in and our mapping from
3259afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner  /// BasicBlocks to loops.
3269afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner  void removeBlock(BasicBlock *BB);
3279afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner
3280bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate:
32953c279b1949f7fa626ccbc399ebbe2d7dc9599a4Devang Patel  void Calculate(DominatorTree &DT);
33053c279b1949f7fa626ccbc399ebbe2d7dc9599a4Devang Patel  Loop *ConsiderForLoop(BasicBlock *BB, DominatorTree &DT);
3317dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
3327dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner  void InsertLoopInto(Loop *L, Loop *Parent);
3330bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner};
3340bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner
335e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla
3361db0a400370466e187ae06c96a1586c2c21409ddChris Lattner// Allow clients to walk the list of nested loops...
3371db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<const Loop*> {
3381db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  typedef const Loop NodeType;
3391db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
3401db0a400370466e187ae06c96a1586c2c21409ddChris Lattner
3411db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  static NodeType *getEntryNode(const Loop *L) { return L; }
3429769ab22265b313171d201b5928688524a01bd87Misha Brukman  static inline ChildIteratorType child_begin(NodeType *N) {
343329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner    return N->begin();
3441db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  }
3459769ab22265b313171d201b5928688524a01bd87Misha Brukman  static inline ChildIteratorType child_end(NodeType *N) {
346329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner    return N->end();
3471db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  }
3481db0a400370466e187ae06c96a1586c2c21409ddChris Lattner};
3491db0a400370466e187ae06c96a1586c2c21409ddChris Lattner
3501db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<Loop*> {
3511db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  typedef Loop NodeType;
3521db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
3531db0a400370466e187ae06c96a1586c2c21409ddChris Lattner
3541db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  static NodeType *getEntryNode(Loop *L) { return L; }
3559769ab22265b313171d201b5928688524a01bd87Misha Brukman  static inline ChildIteratorType child_begin(NodeType *N) {
356329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner    return N->begin();
3571db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  }
3589769ab22265b313171d201b5928688524a01bd87Misha Brukman  static inline ChildIteratorType child_end(NodeType *N) {
359329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner    return N->end();
3601db0a400370466e187ae06c96a1586c2c21409ddChris Lattner  }
3611db0a400370466e187ae06c96a1586c2c21409ddChris Lattner};
3621db0a400370466e187ae06c96a1586c2c21409ddChris Lattner
363d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace
364d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke
3654f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Make sure that any clients of this file link in LoopInfo.cpp
3664f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerFORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo)
3674f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer
3680bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#endif
369