LoopInfo.h revision 5c7e326585f3a543388ba871c3425f7664cd9143
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" 350bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 38d41b30def3181bce4bf87e8bde664d15663165d0Jeff Cohenclass ETForest; 398fc2f2072de83665ae20e06929e28317f449bcdfChris Lattnerclass LoopInfo; 40e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattnerclass PHINode; 4188d3ef2c744db0289223a4477669f24d542e6d97Chris Lattnerclass Instruction; 420bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 430bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 449769ab22265b313171d201b5928688524a01bd87Misha Brukman/// Loop class - Instances of this class are used to represent loops that are 459769ab22265b313171d201b5928688524a01bd87Misha Brukman/// detected in the flow graph 462b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 470bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerclass Loop { 480bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner Loop *ParentLoop; 49697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<Loop*> SubLoops; // Loops contained entirely within this one 507dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner std::vector<BasicBlock*> Blocks; // First entry is the header node 510bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 520bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner Loop(const Loop &); // DO NOT IMPLEMENT 530bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner const Loop &operator=(const Loop &); // DO NOT IMPLEMENT 540bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 5546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// Loop ctor - This creates an empty loop. 56072b163424491c85df6664a4e056aae5e07dc64dChris Lattner Loop() : ParentLoop(0) {} 574e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner ~Loop() { 584e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 594e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner delete SubLoops[i]; 604e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner } 610bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 62072b163424491c85df6664a4e056aae5e07dc64dChris Lattner unsigned getLoopDepth() const { 63072b163424491c85df6664a4e056aae5e07dc64dChris Lattner unsigned D = 0; 64072b163424491c85df6664a4e056aae5e07dc64dChris Lattner for (const Loop *CurLoop = this; CurLoop; CurLoop = CurLoop->ParentLoop) 65072b163424491c85df6664a4e056aae5e07dc64dChris Lattner ++D; 66072b163424491c85df6664a4e056aae5e07dc64dChris Lattner return D; 67072b163424491c85df6664a4e056aae5e07dc64dChris Lattner } 687dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner BasicBlock *getHeader() const { return Blocks.front(); } 697dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner Loop *getParentLoop() const { return ParentLoop; } 700bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 712b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// contains - Return true of the specified basic block is in this loop 72fbdf4bf1799bf9ea566fc0fc0507752590a6d559Misha Brukman /// 73a51b767df42019eb155281f3a64a16593c14f7e9Chris Lattner bool contains(const BasicBlock *BB) const; 740bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 75329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - Return the loops contained entirely within this loop. 762b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 7721d6ff546d0c9cd1a631fe7940a3988a2472198cTanya Lattner const std::vector<Loop*> &getSubLoops() const { return SubLoops; } 78329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner typedef std::vector<Loop*>::const_iterator iterator; 79329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return SubLoops.begin(); } 80329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return SubLoops.end(); } 81fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 82fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getBlocks - Get a list of the basic blocks which make up this loop. 83fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 84fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner const std::vector<BasicBlock*> &getBlocks() const { return Blocks; } 854e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner typedef std::vector<BasicBlock*>::const_iterator block_iterator; 864e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner block_iterator block_begin() const { return Blocks.begin(); } 874e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner block_iterator block_end() const { return Blocks.end(); } 88fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 892b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// isLoopExit - True if terminator in the block can branch to another block 90f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// that is outside of the current loop. 91fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 926b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman bool isLoopExit(const BasicBlock *BB) const; 936b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman 94fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getNumBackEdges - Calculate the number of back edges to the loop header 95fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 966b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman unsigned getNumBackEdges() const; 979474dd68e8a050193ca4003940ac399e2b17cb6aChris Lattner 9888d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner /// isLoopInvariant - Return true if the specified value is loop invariant 9988d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner /// 10088d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner bool isLoopInvariant(Value *V) const; 101b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng 102e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner //===--------------------------------------------------------------------===// 103e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // APIs for simple analysis of the loop. 104e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // 105e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // Note that all of these methods can fail on general loops (ie, there may not 106e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // be a preheader, etc). For best success, the loop simplification and 107e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // induction variable canonicalization pass should be used to normalize loops 108e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // for easy analysis. These methods assume canonical loops. 109e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 1107466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// getExitingBlocks - Return all blocks inside the loop that have successors 1117466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// outside of the loop. These are the blocks _inside of the current loop_ 1127466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// which branch out. The returned list is always unique. 1137466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// 1147466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner void getExitingBlocks(std::vector<BasicBlock*> &Blocks) const; 1157466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner 116f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// getExitBlocks - Return all of the successor blocks of this loop. These 117f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// are the blocks _outside of the current loop_ which are branched to. 118f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// 119f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner void getExitBlocks(std::vector<BasicBlock*> &Blocks) const; 120f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner 1214b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 1224b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// These are the blocks _outside of the current loop_ which are branched to. 1234b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// This assumes that loop is in canonical form. 1244b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// 1254b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel void getUniqueExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const; 1264b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel 1272b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopPreheader - If there is a preheader for this loop, return it. A 1282b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// loop has a preheader if there is only one edge to the header of the loop 1292b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// from outside of the loop. If this is the case, the block branching to the 130e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// header of the loop is the preheader node. 1312b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 132e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// This method returns null if there is no preheader for the loop. 1332b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1342b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner BasicBlock *getLoopPreheader() const; 1352b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 136331a1833e12b6229986f63f0a156062affbf3142Chris Lattner /// getLoopLatch - If there is a latch block for this loop, return it. A 137331a1833e12b6229986f63f0a156062affbf3142Chris Lattner /// latch block is the canonical backedge for a loop. A loop header in normal 138331a1833e12b6229986f63f0a156062affbf3142Chris Lattner /// form has two edges into it: one from a preheader and one from a latch 139331a1833e12b6229986f63f0a156062affbf3142Chris Lattner /// block. 140331a1833e12b6229986f63f0a156062affbf3142Chris Lattner BasicBlock *getLoopLatch() const; 141331a1833e12b6229986f63f0a156062affbf3142Chris Lattner 142e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getCanonicalInductionVariable - Check to see if the loop has a canonical 143e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// induction variable: an integer recurrence that starts at 0 and increments 144e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// by one each time through the loop. If so, return the phi node that 145e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// corresponds to it. 146e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 147e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner PHINode *getCanonicalInductionVariable() const; 148e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 149e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 150e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// the canonical induction variable value for the "next" iteration of the 151e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// loop. This always succeeds if getCanonicalInductionVariable succeeds. 152e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 153e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner Instruction *getCanonicalInductionVariableIncrement() const; 154e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 155e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getTripCount - Return a loop-invariant LLVM value indicating the number of 156e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// times the loop will be executed. Note that this means that the backedge 157e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// of the loop executes N-1 times. If the trip-count cannot be determined, 158e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// this returns null. 159e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 160e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner Value *getTripCount() const; 161c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 162c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson /// isLCSSAForm - Return true if the Loop is in LCSSA form 163c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson bool isLCSSAForm() const; 164e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 165e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner //===--------------------------------------------------------------------===// 166e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // APIs for updating loop information after changing the CFG 167e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // 168e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 169fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// addBasicBlockToLoop - This method is used by other analyses to update loop 170fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// information. NewBB is set to be a new member of the current loop. 1712b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// Because of this, it is added as a member of all parent loops, and is added 1722b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// to the specified LoopInfo object as being in the current basic block. It 1732b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// is not valid to replace the loop header with this method. 1742b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1752b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI); 1762b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 17746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// replaceChildLoopWith - This is used when splitting loops up. It replaces 17846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// the OldChild entry in our children list with NewChild, and updates the 17946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// parent pointer of OldChild to be null and the NewChild to be this loop. 18046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// This updates the loop depth of the new child. 18146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void replaceChildLoopWith(Loop *OldChild, Loop *NewChild); 18246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 18346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// addChildLoop - Add the specified loop to be a child of this loop. This 18446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// updates the loop depth of the new child. 18546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// 18646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void addChildLoop(Loop *NewChild); 18746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 18846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// removeChildLoop - This removes the specified child from being a subloop of 18946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// this loop. The loop is not deleted, as it will presumably be inserted 19046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// into another loop. 19146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner Loop *removeChildLoop(iterator OldChild); 19246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 19346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// addBlockEntry - This adds a basic block directly to the basic block list. 19446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// This should only be used by transformations that create new loops. Other 19546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// transformations should use addBasicBlockToLoop. 19646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void addBlockEntry(BasicBlock *BB) { 19746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner Blocks.push_back(BB); 19846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner } 19946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 20051a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// moveToHeader - This method is used to move BB (which must be part of this 20151a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// loop) to be the loop header of the loop (the block that dominates all 20251a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// others). 20351a4ad475b095aed49caff176b98c0754e421af4Chris Lattner void moveToHeader(BasicBlock *BB) { 20451a4ad475b095aed49caff176b98c0754e421af4Chris Lattner if (Blocks[0] == BB) return; 20551a4ad475b095aed49caff176b98c0754e421af4Chris Lattner for (unsigned i = 0; ; ++i) { 20651a4ad475b095aed49caff176b98c0754e421af4Chris Lattner assert(i != Blocks.size() && "Loop does not contain BB!"); 20751a4ad475b095aed49caff176b98c0754e421af4Chris Lattner if (Blocks[i] == BB) { 20851a4ad475b095aed49caff176b98c0754e421af4Chris Lattner Blocks[i] = Blocks[0]; 20951a4ad475b095aed49caff176b98c0754e421af4Chris Lattner Blocks[0] = BB; 21051a4ad475b095aed49caff176b98c0754e421af4Chris Lattner return; 21151a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 21251a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 21351a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 21451a4ad475b095aed49caff176b98c0754e421af4Chris Lattner 21546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// removeBlockFromLoop - This removes the specified basic block from the 216f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// current loop, updating the Blocks as appropriate. This does not update 217f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// the mapping in the LoopInfo class. 21846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void removeBlockFromLoop(BasicBlock *BB); 21946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 2207dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void print(std::ostream &O, unsigned Depth = 0) const; 2215c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *O, unsigned Depth = 0) const { 2225c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (O) print(*O, Depth); 2235c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 224f972cbd98c87a2b288943425c1bc92022a8de5c5Chris Lattner void dump() const; 2250bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate: 2260bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner friend class LoopInfo; 22746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner Loop(BasicBlock *BB) : ParentLoop(0) { 228072b163424491c85df6664a4e056aae5e07dc64dChris Lattner Blocks.push_back(BB); 2290bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 2300bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 2310bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2320bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2330bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2340bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 2352b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// LoopInfo - This class builds and contains all of the top level loop 2362b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// structures in the specified function. 2372b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 238f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattnerclass LoopInfo : public FunctionPass { 2390bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // BBMap - Mapping of basic blocks to the inner most loop they occur in 240a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner std::map<BasicBlock*, Loop*> BBMap; 241697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<Loop*> TopLevelLoops; 2422b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner friend class Loop; 2430bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 244918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner ~LoopInfo() { releaseMemory(); } 2450bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 246329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - The interface to the top-level loops in the current 247329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// function. 248329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// 249329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner typedef std::vector<Loop*>::const_iterator iterator; 250329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return TopLevelLoops.begin(); } 251329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return TopLevelLoops.end(); } 2520bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2532b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopFor - Return the inner most loop that BB lives in. If a basic 2542b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// block is in no loop (for example the entry node), null is returned. 2552b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 256072b163424491c85df6664a4e056aae5e07dc64dChris Lattner Loop *getLoopFor(const BasicBlock *BB) const { 257edd5d9ece15f73ec1a31423a4ae39774aa6c521cReid Spencer std::map<BasicBlock *, Loop*>::const_iterator I= 258edd5d9ece15f73ec1a31423a4ae39774aa6c521cReid Spencer BBMap.find(const_cast<BasicBlock*>(BB)); 2590bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return I != BBMap.end() ? I->second : 0; 2600bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 2612b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 2622b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// operator[] - same as getLoopFor... 2632b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 264072b163424491c85df6664a4e056aae5e07dc64dChris Lattner const Loop *operator[](const BasicBlock *BB) const { 2650bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return getLoopFor(BB); 2660bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 2670bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2682b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopDepth - Return the loop nesting level of the specified block... 2692b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 2707e70829632f82de15db187845666aaca6e04b792Chris Lattner unsigned getLoopDepth(const BasicBlock *BB) const { 2710bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner const Loop *L = getLoopFor(BB); 2720bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return L ? L->getLoopDepth() : 0; 2730bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 2740bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2750bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // isLoopHeader - True if the block is a loop header node 276a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner bool isLoopHeader(BasicBlock *BB) const { 27750f5490842d501e269a4c6085d0d132cae0d31f8Chris Lattner const Loop *L = getLoopFor(BB); 27850f5490842d501e269a4c6085d0d132cae0d31f8Chris Lattner return L && L->getHeader() == BB; 2790bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 2800bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 2812b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// runOnFunction - Calculate the natural loop information. 2822b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 2837e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 284facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 285918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner virtual void releaseMemory(); 2865c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling 287ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer void print(std::ostream &O, const Module* = 0) const; 2885c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *O, const Module* M = 0) const { 2895c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (O) print(*O, M); 2905c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 291918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner 292f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 293f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner 2944e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// removeLoop - This removes the specified top-level loop from this loop info 2954e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// object. The loop is not deleted, as it will presumably be inserted into 2964e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// another loop. 2974e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner Loop *removeLoop(iterator I); 2984e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner 29946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// changeLoopFor - Change the top-level loop that contains BB to the 30046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// specified loop. This should be used by transformations that restructure 30146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// the loop hierarchy tree. 30246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void changeLoopFor(BasicBlock *BB, Loop *L); 30346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 30446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// changeTopLevelLoop - Replace the specified loop in the top-level loops 30546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// list with the indicated loop. 30646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop); 30746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 308072b163424491c85df6664a4e056aae5e07dc64dChris Lattner /// addTopLevelLoop - This adds the specified loop to the collection of 309072b163424491c85df6664a4e056aae5e07dc64dChris Lattner /// top-level loops. 310072b163424491c85df6664a4e056aae5e07dc64dChris Lattner void addTopLevelLoop(Loop *New) { 311072b163424491c85df6664a4e056aae5e07dc64dChris Lattner assert(New->getParentLoop() == 0 && "Loop already in subloop!"); 312072b163424491c85df6664a4e056aae5e07dc64dChris Lattner TopLevelLoops.push_back(New); 313072b163424491c85df6664a4e056aae5e07dc64dChris Lattner } 314072b163424491c85df6664a4e056aae5e07dc64dChris Lattner 3159afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// removeBlock - This method completely removes BB from all data structures, 3169afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// including all of the Loop objects it is nested in and our mapping from 3179afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// BasicBlocks to loops. 3189afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner void removeBlock(BasicBlock *BB); 3199afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner 3200bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate: 32125abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner void Calculate(ETForest &EF); 32225abb1dc094a08a3ba5cb426698b4780cbe438bbChris Lattner Loop *ConsiderForLoop(BasicBlock *BB, ETForest &EF); 3237dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent); 3247dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void InsertLoopInto(Loop *L, Loop *Parent); 3250bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 3260bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 327e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla 3281db0a400370466e187ae06c96a1586c2c21409ddChris Lattner// Allow clients to walk the list of nested loops... 3291db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<const Loop*> { 3301db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef const Loop NodeType; 3311db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef std::vector<Loop*>::const_iterator ChildIteratorType; 3321db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 3331db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(const Loop *L) { return L; } 3349769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 335329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 3361db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 3379769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 338329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 3391db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 3401db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 3411db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 3421db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<Loop*> { 3431db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef Loop NodeType; 3441db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef std::vector<Loop*>::const_iterator ChildIteratorType; 3451db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 3461db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(Loop *L) { return L; } 3479769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 348329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 3491db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 3509769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 351329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 3521db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 3531db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 3541db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 355d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 356d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3574f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Make sure that any clients of this file link in LoopInfo.cpp 3584f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerFORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo) 3594f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer 3600bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#endif 361