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