LoopInfo.h revision 9d59d9f8495b0361c9ffd1dc82888d8e7ba5070e
148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// 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" 34019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Constants.h" 35019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Instructions.h" 3644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson#include "llvm/ADT/DepthFirstIterator.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h" 38019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 39b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel#include "llvm/ADT/SmallVector.h" 4044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson#include "llvm/Analysis/Dominators.h" 41019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Support/CFG.h" 42019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include "llvm/Support/Streams.h" 43019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include <algorithm> 44019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#include <ostream> 45019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 461d5562f72e3f7d9e17a2bf95afa54a98dac95894Dan Gohmannamespace llvm { 471d5562f72e3f7d9e17a2bf95afa54a98dac95894Dan Gohman 48019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Andersontemplate<typename T> 49019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Andersonstatic void RemoveFromVector(std::vector<T*> &V, T *N) { 50019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N); 51019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(I != V.end() && "N is not in this list!"); 52019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson V.erase(I); 53019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson} 540bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 5553c279b1949f7fa626ccbc399ebbe2d7dc9599a4Devang Patelclass DominatorTree; 568fc2f2072de83665ae20e06929e28317f449bcdfChris Lattnerclass LoopInfo; 5744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersontemplate<class N> class LoopInfoBase; 58fadcd4e60be40bcab198dcb0eef6e4a51b4c0627Chris Lattnertemplate<class N> class LoopBase; 59fadcd4e60be40bcab198dcb0eef6e4a51b4c0627Chris Lattner 60fadcd4e60be40bcab198dcb0eef6e4a51b4c0627Chris Lattnertypedef LoopBase<BasicBlock> Loop; 610bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 620bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 63131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner/// LoopBase class - Instances of this class are used to represent loops that 64131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner/// are detected in the flow graph 652b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 66019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Andersontemplate<class BlockT> 67019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Andersonclass LoopBase { 68019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *ParentLoop; 69131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // SubLoops - Loops contained entirely within this one. 70131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner std::vector<LoopBase<BlockT>*> SubLoops; 71131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner 72131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // Blocks - The list of blocks in this loop. First entry is the header node. 73131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner std::vector<BlockT*> Blocks; 74019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 75019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase(const LoopBase<BlockT> &); // DO NOT IMPLEMENT 76131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner const LoopBase<BlockT>&operator=(const LoopBase<BlockT> &);// DO NOT IMPLEMENT 770bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 7846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// Loop ctor - This creates an empty loop. 79019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase() : ParentLoop(0) {} 80019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ~LoopBase() { 8134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (size_t i = 0, e = SubLoops.size(); i != e; ++i) 824e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner delete SubLoops[i]; 834e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner } 840bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 85ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// getLoopDepth - Return the nesting level of this loop. An outer-most 86ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// loop has depth 1, for consistency with loop depth values used for basic 87ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// blocks, where depth 0 is used for blocks not inside any loops. 88072b163424491c85df6664a4e056aae5e07dc64dChris Lattner unsigned getLoopDepth() const { 89ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman unsigned D = 1; 90ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman for (const LoopBase<BlockT> *CurLoop = ParentLoop; CurLoop; 91019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson CurLoop = CurLoop->ParentLoop) 92072b163424491c85df6664a4e056aae5e07dc64dChris Lattner ++D; 93072b163424491c85df6664a4e056aae5e07dc64dChris Lattner return D; 94072b163424491c85df6664a4e056aae5e07dc64dChris Lattner } 95019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *getHeader() const { return Blocks.front(); } 96019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *getParentLoop() const { return ParentLoop; } 970bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 98b670a1737bae5c3ecc65042d3a1b10d774ecd252Wojciech Matyjewicz /// contains - Return true if the specified basic block is in this loop 99fbdf4bf1799bf9ea566fc0fc0507752590a6d559Misha Brukman /// 100019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson bool contains(const BlockT *BB) const { 101f3ab3a937203d690744357844948faaf96fb73f9Dan Gohman return std::find(block_begin(), block_end(), BB) != block_end(); 102019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 1030bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 104329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - Return the loops contained entirely within this loop. 1052b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 106019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson const std::vector<LoopBase<BlockT>*> &getSubLoops() const { return SubLoops; } 107019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator; 108329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return SubLoops.begin(); } 109329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return SubLoops.end(); } 11021c276d2fa99914d5ed958ac0aec7d78e3dd87cfDan Gohman bool empty() const { return SubLoops.empty(); } 111fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 112fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getBlocks - Get a list of the basic blocks which make up this loop. 113fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 114019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson const std::vector<BlockT*> &getBlocks() const { return Blocks; } 115019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson typedef typename std::vector<BlockT*>::const_iterator block_iterator; 1164e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner block_iterator block_begin() const { return Blocks.begin(); } 1174e77cc46ac688e7bee98747049f90e19e2902227Chris Lattner block_iterator block_end() const { return Blocks.end(); } 118fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 119280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky /// isLoopExit - True if terminator in the block can branch to another block 120280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky /// that is outside of the current loop. 121fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 122019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson bool isLoopExit(const BlockT *BB) const { 123d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<BlockT*> BlockTraits; 124d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename BlockTraits::ChildIteratorType SI = 125d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BlockTraits::child_begin(const_cast<BlockT*>(BB)), 126d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson SE = BlockTraits::child_end(const_cast<BlockT*>(BB)); SI != SE; ++SI) { 127019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (!contains(*SI)) 128019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return true; 129019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 130019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return false; 131019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 1326b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman 133fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getNumBackEdges - Calculate the number of back edges to the loop header 134fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 135019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson unsigned getNumBackEdges() const { 136019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson unsigned NumBackEdges = 0; 137019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *H = getHeader(); 138019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 139d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 140d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename InvBlockTraits::ChildIteratorType I = 141d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(const_cast<BlockT*>(H)), 142d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson E = InvBlockTraits::child_end(const_cast<BlockT*>(H)); I != E; ++I) 143019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (contains(*I)) 144019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ++NumBackEdges; 145019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 146019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return NumBackEdges; 147019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 1489474dd68e8a050193ca4003940ac399e2b17cb6aChris Lattner 14988d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner /// isLoopInvariant - Return true if the specified value is loop invariant 15088d3ef2c744db0289223a4477669f24d542e6d97Chris Lattner /// 151528b00adc44ae1f8dfd78cf95853014c6ef341a1Owen Anderson inline bool isLoopInvariant(Value *V) const { 152019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (Instruction *I = dyn_cast<Instruction>(V)) 153019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return !contains(I->getParent()); 154019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return true; // All non-instructions are loop invariant 155019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 156b9b2b309d3195d9e2ed1e72da8566a470783e8d7Evan Cheng 157e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner //===--------------------------------------------------------------------===// 158e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // APIs for simple analysis of the loop. 159e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // 160e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // Note that all of these methods can fail on general loops (ie, there may not 161e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // be a preheader, etc). For best success, the loop simplification and 162e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // induction variable canonicalization pass should be used to normalize loops 163e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // for easy analysis. These methods assume canonical loops. 164e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 1657466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// getExitingBlocks - Return all blocks inside the loop that have successors 1667466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// outside of the loop. These are the blocks _inside of the current loop_ 1677466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// which branch out. The returned list is always unique. 1687466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner /// 169019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { 170019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Sort the blocks vector so that we can use binary search to do quick 171019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // lookups. 172019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 173019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::sort(LoopBBs.begin(), LoopBBs.end()); 174019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 175d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<BlockT*> BlockTraits; 176f3ab3a937203d690744357844948faaf96fb73f9Dan Gohman for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 177d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename BlockTraits::ChildIteratorType I = 178d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 179d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson I != E; ++I) 180019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) { 181019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Not in current loop? It must be an exit block. 182019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ExitingBlocks.push_back(*BI); 183019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson break; 184019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 185019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 1867466ebf045fa5097ee0d7d2728eed7fd5945c8bcChris Lattner 187c83324682f3409c15dad992cd62928426c9ad83dDan Gohman /// getExitingBlock - If getExitingBlocks would return exactly one block, 188c83324682f3409c15dad992cd62928426c9ad83dDan Gohman /// return that block. Otherwise return null. 189c83324682f3409c15dad992cd62928426c9ad83dDan Gohman BlockT *getExitingBlock() const { 190c83324682f3409c15dad992cd62928426c9ad83dDan Gohman SmallVector<BlockT*, 8> ExitingBlocks; 191c83324682f3409c15dad992cd62928426c9ad83dDan Gohman getExitingBlocks(ExitingBlocks); 192c83324682f3409c15dad992cd62928426c9ad83dDan Gohman if (ExitingBlocks.size() == 1) 193c83324682f3409c15dad992cd62928426c9ad83dDan Gohman return ExitingBlocks[0]; 194c83324682f3409c15dad992cd62928426c9ad83dDan Gohman return 0; 195c83324682f3409c15dad992cd62928426c9ad83dDan Gohman } 196c83324682f3409c15dad992cd62928426c9ad83dDan Gohman 197f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// getExitBlocks - Return all of the successor blocks of this loop. These 198f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// are the blocks _outside of the current loop_ which are branched to. 199f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// 200019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { 201019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Sort the blocks vector so that we can use binary search to do quick 202019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // lookups. 203019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 204019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::sort(LoopBBs.begin(), LoopBBs.end()); 205019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 206d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<BlockT*> BlockTraits; 207f3ab3a937203d690744357844948faaf96fb73f9Dan Gohman for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 208d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename BlockTraits::ChildIteratorType I = 209d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 210d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson I != E; ++I) 211019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 212019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Not in current loop? It must be an exit block. 213019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ExitBlocks.push_back(*I); 214019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 215f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner 2161827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman /// getExitBlock - If getExitBlocks would return exactly one block, 2171827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman /// return that block. Otherwise return null. 2181827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman BlockT *getExitBlock() const { 2191827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman SmallVector<BlockT*, 8> ExitBlocks; 2201827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman getExitBlocks(ExitBlocks); 2211827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman if (ExitBlocks.size() == 1) 2221827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman return ExitBlocks[0]; 2231827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman return 0; 2241827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman } 2251827e8263c9cb5dc29eea4999d8729f7376af4e1Dan Gohman 2264b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 2274b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// These are the blocks _outside of the current loop_ which are branched to. 2284b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// This assumes that loop is in canonical form. 2294b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel /// 230019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { 231019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Sort the blocks vector so that we can use binary search to do quick 232019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // lookups. 233019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 234019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::sort(LoopBBs.begin(), LoopBBs.end()); 235019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 236019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::vector<BlockT*> switchExitBlocks; 237019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 238f3ab3a937203d690744357844948faaf96fb73f9Dan Gohman for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 239019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 240019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *current = *BI; 241019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson switchExitBlocks.clear(); 242019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 243d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<BlockT*> BlockTraits; 244d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 245d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename BlockTraits::ChildIteratorType I = 246d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 247d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson I != E; ++I) { 248019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 249019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // If block is inside the loop then it is not a exit block. 250019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson continue; 251d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson 252d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typename InvBlockTraits::ChildIteratorType PI = 253d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(*I); 254019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *firstPred = *PI; 255019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 256019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // If current basic block is this exit block's first predecessor 257019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // then only insert exit block in to the output ExitBlocks vector. 258019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // This ensures that same exit block is not inserted twice into 259019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // ExitBlocks vector. 260019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (current != firstPred) 261019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson continue; 262019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 263019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // If a terminator has more then two successors, for example SwitchInst, 264019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // then it is possible that there are multiple edges from current block 265019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // to one exit block. 266d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson if (std::distance(BlockTraits::child_begin(current), 267d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BlockTraits::child_end(current)) <= 2) { 268019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ExitBlocks.push_back(*I); 269019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson continue; 270019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 271019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 272019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // In case of multiple edges from current block to exit block, collect 273019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 274019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // duplicate edges. 275019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 276019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson == switchExitBlocks.end()) { 277019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson switchExitBlocks.push_back(*I); 278019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ExitBlocks.push_back(*I); 279019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 280019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 281019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 282019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 2834b8f36f10672bbdd747eabfb5708e4758c3d5337Devang Patel 284a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 285a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman /// block, return that block. Otherwise return null. 286a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman BlockT *getUniqueExitBlock() const { 287a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman SmallVector<BlockT*, 8> UniqueExitBlocks; 288a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman getUniqueExitBlocks(UniqueExitBlocks); 289a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman if (UniqueExitBlocks.size() == 1) 290a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman return UniqueExitBlocks[0]; 291a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman return 0; 292a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman } 293a278f3f55212e38c0647909f51ee7d2d6e41799aDan Gohman 2942b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopPreheader - If there is a preheader for this loop, return it. A 2952b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// loop has a preheader if there is only one edge to the header of the loop 2962b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// from outside of the loop. If this is the case, the block branching to the 297e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// header of the loop is the preheader node. 2982b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 299e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// This method returns null if there is no preheader for the loop. 3002b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 301019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *getLoopPreheader() const { 302019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Keep track of nodes outside the loop branching to the header... 303019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *Out = 0; 304019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 305019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Loop over the predecessors of the header node... 306019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *Header = getHeader(); 307d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<BlockT*> BlockTraits; 308d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 309d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename InvBlockTraits::ChildIteratorType PI = 310d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(Header), 311d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) 312019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (!contains(*PI)) { // If the block is not in the loop... 313019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (Out && Out != *PI) 314019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; // Multiple predecessors outside the loop 315019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Out = *PI; 316019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 317019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 318019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Make sure there is only one exit out of the preheader. 319019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(Out && "Header of loop has no predecessors from outside loop?"); 320d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 321019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ++SI; 322d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson if (SI != BlockTraits::child_end(Out)) 323019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; // Multiple exits from the block, must not be a preheader. 324019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 325131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // If there is exactly one preheader, return it. If there was zero, then 326131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // Out is still null. 327019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return Out; 328019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 3292b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 330b317143ba851ce2853fb262fb2185ef5f1be030dDan Gohman /// getLoopLatch - If there is a single latch block for this loop, return it. 331b317143ba851ce2853fb262fb2185ef5f1be030dDan Gohman /// A latch block is a block that contains a branch back to the header. 332b317143ba851ce2853fb262fb2185ef5f1be030dDan Gohman /// A loop header in normal form has two edges into it: one from a preheader 333b317143ba851ce2853fb262fb2185ef5f1be030dDan Gohman /// and one from a latch block. 334019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *getLoopLatch() const { 335019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *Header = getHeader(); 336d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 337d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typename InvBlockTraits::ChildIteratorType PI = 338d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(Header); 339d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typename InvBlockTraits::ChildIteratorType PE = 340d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_end(Header); 341019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (PI == PE) return 0; // no preds? 342019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 343019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *Latch = 0; 344019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (contains(*PI)) 345019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Latch = *PI; 346019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ++PI; 347019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (PI == PE) return 0; // only one pred? 348019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 349019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (contains(*PI)) { 350019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (Latch) return 0; // multiple backedges 351019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Latch = *PI; 352019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 353019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ++PI; 354019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (PI != PE) return 0; // more than two preds 355019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 356019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return Latch; 357019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 358331a1833e12b6229986f63f0a156062affbf3142Chris Lattner 359e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getCanonicalInductionVariable - Check to see if the loop has a canonical 360e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// induction variable: an integer recurrence that starts at 0 and increments 361e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// by one each time through the loop. If so, return the phi node that 362e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// corresponds to it. 363e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 3646c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// The IndVarSimplify pass transforms loops to have a canonical induction 3656c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// variable. 3666c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// 367528b00adc44ae1f8dfd78cf95853014c6ef341a1Owen Anderson inline PHINode *getCanonicalInductionVariable() const { 368019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *H = getHeader(); 369019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 370019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *Incoming = 0, *Backedge = 0; 371d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 372d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typename InvBlockTraits::ChildIteratorType PI = 373d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(H); 374d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson assert(PI != InvBlockTraits::child_end(H) && 375d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson "Loop must have at least one backedge!"); 376019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Backedge = *PI++; 377d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop 378019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Incoming = *PI++; 379d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? 380019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 381019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (contains(Incoming)) { 382019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (contains(Backedge)) 383019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; 384019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::swap(Incoming, Backedge); 385019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } else if (!contains(Backedge)) 386019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; 387019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 388019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Loop over all of the PHI nodes, looking for a canonical indvar. 389019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) { 390019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson PHINode *PN = cast<PHINode>(I); 391402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (ConstantInt *CI = 392402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 393402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (CI->isNullValue()) 394402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (Instruction *Inc = 395402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 396402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (Inc->getOpcode() == Instruction::Add && 397402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz Inc->getOperand(0) == PN) 398402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 399402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz if (CI->equalsInt(1)) 400402689d11a3879163a3e67ea297937c2c26cc502Wojciech Matyjewicz return PN; 401019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 402019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; 403019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 404e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 405e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 406e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// the canonical induction variable value for the "next" iteration of the 407e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// loop. This always succeeds if getCanonicalInductionVariable succeeds. 408e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 409528b00adc44ae1f8dfd78cf95853014c6ef341a1Owen Anderson inline Instruction *getCanonicalInductionVariableIncrement() const { 410019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (PHINode *PN = getCanonicalInductionVariable()) { 411019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson bool P1InLoop = contains(PN->getIncomingBlock(1)); 412019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return cast<Instruction>(PN->getIncomingValue(P1InLoop)); 413019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 414019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; 415019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 416e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 417e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// getTripCount - Return a loop-invariant LLVM value indicating the number of 418e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// times the loop will be executed. Note that this means that the backedge 419e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// of the loop executes N-1 times. If the trip-count cannot be determined, 420e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// this returns null. 421e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner /// 4226c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// The IndVarSimplify pass transforms loops to have a form that this 4236c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// function easily understands. 4246c3534c5aa6b1d34b277dfaca3af86ac41e53f0eDan Gohman /// 425528b00adc44ae1f8dfd78cf95853014c6ef341a1Owen Anderson inline Value *getTripCount() const { 426019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Canonical loops will end with a 'cmp ne I, V', where I is the incremented 427019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // canonical induction variable and V is the trip count of the loop. 428019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Instruction *Inc = getCanonicalInductionVariableIncrement(); 429019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (Inc == 0) return 0; 430019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson PHINode *IV = cast<PHINode>(Inc->getOperand(0)); 431019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 432019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *BackedgeBlock = 433019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); 434019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 435019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) 436019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (BI->isConditional()) { 437019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { 438ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov if (ICI->getOperand(0) == Inc) { 439019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (BI->getSuccessor(0) == getHeader()) { 440019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (ICI->getPredicate() == ICmpInst::ICMP_NE) 441019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return ICI->getOperand(1); 442019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { 443019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return ICI->getOperand(1); 444019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 445ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov } 446019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 447019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 448019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 449019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return 0; 450019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 451c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson 45245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// getSmallConstantTripCount - Returns the trip count of this loop as a 45345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// normal unsigned value, if possible. Returns 0 if the trip count is unknown 45445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// of not constant. Will also return 0 if the trip count is very large 45545b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// (>= 2^32) 45645b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman inline unsigned getSmallConstantTripCount() const { 45745b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman Value* TripCount = this->getTripCount(); 45845b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (TripCount) { 45945b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { 46045b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman // Guard against huge trip counts. 46145b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (TripCountC->getValue().getActiveBits() <= 32) { 46245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman return (unsigned)TripCountC->getZExtValue(); 46345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 46445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 46545b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 46645b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman return 0; 46745b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 46845b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman 46945b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// getSmallConstantTripMultiple - Returns the largest constant divisor of the 47045b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// trip count of this loop as a normal unsigned value, if possible. This 47145b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// means that the actual trip count is always a multiple of the returned 47245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// value (don't forget the trip count could very well be zero as well!). 47345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// 47445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// Returns 1 if the trip count is unknown or not guaranteed to be the 47545b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// multiple of a constant (which is also the case if the trip count is simply 47645b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// constant, use getSmallConstantTripCount for that case), Will also return 1 47745b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman /// if the trip count is very large (>= 2^32). 47845b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman inline unsigned getSmallConstantTripMultiple() const { 47945b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman Value* TripCount = this->getTripCount(); 48045b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman // This will hold the ConstantInt result, if any 48145b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman ConstantInt *Result = NULL; 48245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (TripCount) { 48345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman // See if the trip count is constant itself 48445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman Result = dyn_cast<ConstantInt>(TripCount); 48545b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman // if not, see if it is a multiplication 48645b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (!Result) 48745b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { 48845b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman switch (BO->getOpcode()) { 48945b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman case BinaryOperator::Mul: 49045b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman Result = dyn_cast<ConstantInt>(BO->getOperand(1)); 49145b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman break; 49245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman default: 49345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman break; 49445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 49545b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 49645b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 49745b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman // Guard against huge trip counts. 49845b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman if (Result && Result->getValue().getActiveBits() <= 32) { 49945b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman return (unsigned)Result->getZExtValue(); 50045b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } else { 50145b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman return 1; 50245b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 50345b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman } 50445b3197090afedf2d19eb0b73115207343cbb2aeDan Gohman 505c2cc15cf9d926b8de41dabba86005a55806127a0Owen Anderson /// isLCSSAForm - Return true if the Loop is in LCSSA form 506528b00adc44ae1f8dfd78cf95853014c6ef341a1Owen Anderson inline bool isLCSSAForm() const { 507019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Sort the blocks vector so that we can use binary search to do quick 508019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // lookups. 509019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SmallPtrSet<BlockT*, 16> LoopBBs(block_begin(), block_end()); 510019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 511019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 512019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *BB = *BI; 513131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E;++I) 514019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 515019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson ++UI) { 516019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson BlockT *UserBB = cast<Instruction>(*UI)->getParent(); 517019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (PHINode *P = dyn_cast<PHINode>(*UI)) { 518a36791da41cf4f635e50077b290676b873836bdaGabor Greif UserBB = P->getIncomingBlock(UI); 519019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 520019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 521131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // Check the current block, as a fast-path. Most values are used in 522131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // the same block they are defined in. 523019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (UserBB != BB && !LoopBBs.count(UserBB)) 524019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return false; 525019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 526019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 527019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 528019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return true; 529019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 530e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 531e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner //===--------------------------------------------------------------------===// 532e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // APIs for updating loop information after changing the CFG 533e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner // 534e725cb0d5a8e017b66768eaf186718b36ffea193Chris Lattner 535fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// addBasicBlockToLoop - This method is used by other analyses to update loop 536fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// information. NewBB is set to be a new member of the current loop. 5372b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// Because of this, it is added as a member of all parent loops, and is added 5382b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// to the specified LoopInfo object as being in the current basic block. It 5392b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// is not valid to replace the loop header with this method. 5402b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 541d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT> &LI); 5422b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 54346758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// replaceChildLoopWith - This is used when splitting loops up. It replaces 54446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// the OldChild entry in our children list with NewChild, and updates the 54546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// parent pointer of OldChild to be null and the NewChild to be this loop. 54646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// This updates the loop depth of the new child. 547019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void replaceChildLoopWith(LoopBase<BlockT> *OldChild, 548019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *NewChild) { 549019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(OldChild->ParentLoop == this && "This loop is already broken!"); 550019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!"); 551019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson typename std::vector<LoopBase<BlockT>*>::iterator I = 552019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson std::find(SubLoops.begin(), SubLoops.end(), OldChild); 553019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(I != SubLoops.end() && "OldChild not in loop!"); 554019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson *I = NewChild; 555019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson OldChild->ParentLoop = 0; 556019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson NewChild->ParentLoop = this; 557019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 55846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 55946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// addChildLoop - Add the specified loop to be a child of this loop. This 56046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// updates the loop depth of the new child. 56146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// 562019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void addChildLoop(LoopBase<BlockT> *NewChild) { 563019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!"); 564019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson NewChild->ParentLoop = this; 565019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SubLoops.push_back(NewChild); 566019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 56746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 56846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// removeChildLoop - This removes the specified child from being a subloop of 56946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// this loop. The loop is not deleted, as it will presumably be inserted 57046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// into another loop. 571019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *removeChildLoop(iterator I) { 572019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(I != SubLoops.end() && "Cannot remove end iterator!"); 573019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *Child = *I; 574019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(Child->ParentLoop == this && "Child is not a child of this loop!"); 575019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson SubLoops.erase(SubLoops.begin()+(I-begin())); 576019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson Child->ParentLoop = 0; 577019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson return Child; 578019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 57946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 58046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// addBlockEntry - This adds a basic block directly to the basic block list. 58146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// This should only be used by transformations that create new loops. Other 58246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// transformations should use addBasicBlockToLoop. 583019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void addBlockEntry(BlockT *BB) { 58446758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner Blocks.push_back(BB); 58546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner } 58646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 58751a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// moveToHeader - This method is used to move BB (which must be part of this 58851a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// loop) to be the loop header of the loop (the block that dominates all 58951a4ad475b095aed49caff176b98c0754e421af4Chris Lattner /// others). 590019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void moveToHeader(BlockT *BB) { 59151a4ad475b095aed49caff176b98c0754e421af4Chris Lattner if (Blocks[0] == BB) return; 59251a4ad475b095aed49caff176b98c0754e421af4Chris Lattner for (unsigned i = 0; ; ++i) { 59351a4ad475b095aed49caff176b98c0754e421af4Chris Lattner assert(i != Blocks.size() && "Loop does not contain BB!"); 59451a4ad475b095aed49caff176b98c0754e421af4Chris Lattner if (Blocks[i] == BB) { 59551a4ad475b095aed49caff176b98c0754e421af4Chris Lattner Blocks[i] = Blocks[0]; 59651a4ad475b095aed49caff176b98c0754e421af4Chris Lattner Blocks[0] = BB; 59751a4ad475b095aed49caff176b98c0754e421af4Chris Lattner return; 59851a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 59951a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 60051a4ad475b095aed49caff176b98c0754e421af4Chris Lattner } 60151a4ad475b095aed49caff176b98c0754e421af4Chris Lattner 60246758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// removeBlockFromLoop - This removes the specified basic block from the 603f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// current loop, updating the Blocks as appropriate. This does not update 604f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner /// the mapping in the LoopInfo class. 605019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void removeBlockFromLoop(BlockT *BB) { 606019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson RemoveFromVector(Blocks, BB); 607019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 60846758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 60958e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel /// verifyLoop - Verify loop structure 610019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void verifyLoop() const { 611019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#ifndef NDEBUG 612019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert (getHeader() && "Loop header is missing"); 613019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert (getLoopPreheader() && "Loop preheader is missing"); 614019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert (getLoopLatch() && "Loop latch is missing"); 615f3ab3a937203d690744357844948faaf96fb73f9Dan Gohman for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) 616019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson (*I)->verifyLoop(); 617019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson#endif 618019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 619019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 620019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void print(std::ostream &OS, unsigned Depth = 0) const { 621927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman OS << std::string(Depth*2, ' ') << "Loop at depth " << getLoopDepth() 622927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman << " containing: "; 623019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 624019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson for (unsigned i = 0; i < getBlocks().size(); ++i) { 625019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson if (i) OS << ","; 626927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman BlockT *BB = getBlocks()[i]; 627927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman WriteAsOperand(OS, BB, false); 628927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman if (BB == getHeader()) OS << "<header>"; 629927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman if (BB == getLoopLatch()) OS << "<latch>"; 630927793b6a165148af6d079ac03f97d13d296ff0dDan Gohman if (isLoopExit(BB)) OS << "<exit>"; 631019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 632019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson OS << "\n"; 63358e0ef1e90c3f6dbae213612b44e56f7d6d65ea7Devang Patel 634019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson for (iterator I = begin(), E = end(); I != E; ++I) 635019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson (*I)->print(OS, Depth+2); 636019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 637019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 6385c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *O, unsigned Depth = 0) const { 6395c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (O) print(*O, Depth); 6405c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 641019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 642019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson void dump() const { 643019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson print(cerr); 644019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 645019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 6460bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate: 64744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson friend class LoopInfoBase<BlockT>; 6481002c0203450620594a85454c6a095ca94b87cb2Dan Gohman explicit LoopBase(BlockT *BB) : ParentLoop(0) { 649072b163424491c85df6664a4e056aae5e07dc64dChris Lattner Blocks.push_back(BB); 6500bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 6510bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 6520bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 6530bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 6540bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 6552b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// LoopInfo - This class builds and contains all of the top level loop 6562b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// structures in the specified function. 6572b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 65844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 65944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersontemplate<class BlockT> 66044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersonclass LoopInfoBase { 6610bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // BBMap - Mapping of basic blocks to the inner most loop they occur in 662d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson std::map<BlockT*, LoopBase<BlockT>*> BBMap; 66344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson std::vector<LoopBase<BlockT>*> TopLevelLoops; 66444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson friend class LoopBase<BlockT>; 6659d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman 6669d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman void operator=(const LoopInfoBase &); // do not implement 6679d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LoopInfoBase(const LoopInfo &); // do not implement 6680bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 66944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopInfoBase() { } 67044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson ~LoopInfoBase() { releaseMemory(); } 67144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 67244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void releaseMemory() { 67344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (typename std::vector<LoopBase<BlockT>* >::iterator I = 67444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) 67544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson delete *I; // Delete all of the loops... 6760bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 677131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner BBMap.clear(); // Reset internal state of analysis 67844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops.clear(); 67944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 68044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 681329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - The interface to the top-level loops in the current 682329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// function. 683329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// 68444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator; 685329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return TopLevelLoops.begin(); } 686329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return TopLevelLoops.end(); } 687a8c763b3071ae1a58ee8baeb282331245527e004Dan Gohman bool empty() const { return TopLevelLoops.empty(); } 68844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 6892b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopFor - Return the inner most loop that BB lives in. If a basic 6902b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// block is in no loop (for example the entry node), null is returned. 6912b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 69244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *getLoopFor(const BlockT *BB) const { 69344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::map<BlockT *, LoopBase<BlockT>*>::const_iterator I= 694d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson BBMap.find(const_cast<BlockT*>(BB)); 6950bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return I != BBMap.end() ? I->second : 0; 6960bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 69744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 6982b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// operator[] - same as getLoopFor... 6992b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 70044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson const LoopBase<BlockT> *operator[](const BlockT *BB) const { 7010bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return getLoopFor(BB); 7020bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 70344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 704ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// getLoopDepth - Return the loop nesting level of the specified block. A 705ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// depth of 0 means the block is not inside any loop. 7062b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 70744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson unsigned getLoopDepth(const BlockT *BB) const { 708d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson const LoopBase<BlockT> *L = getLoopFor(BB); 7090bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return L ? L->getLoopDepth() : 0; 7100bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 7110bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 7120bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // isLoopHeader - True if the block is a loop header node 71344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson bool isLoopHeader(BlockT *BB) const { 714d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson const LoopBase<BlockT> *L = getLoopFor(BB); 71550f5490842d501e269a4c6085d0d132cae0d31f8Chris Lattner return L && L->getHeader() == BB; 7160bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 71744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 71844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// removeLoop - This removes the specified top-level loop from this loop info 71944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// object. The loop is not deleted, as it will presumably be inserted into 72044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// another loop. 72144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *removeLoop(iterator I) { 72244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(I != end() && "Cannot remove end iterator!"); 72344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *L = *I; 72444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(L->getParentLoop() == 0 && "Not a top-level loop!"); 72544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin())); 72644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson return L; 72744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 72844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 72944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// changeLoopFor - Change the top-level loop that contains BB to the 73044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// specified loop. This should be used by transformations that restructure 73144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// the loop hierarchy tree. 73244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void changeLoopFor(BlockT *BB, LoopBase<BlockT> *L) { 73344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *&OldLoop = BBMap[BB]; 73444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(OldLoop && "Block not in a loop yet!"); 73544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson OldLoop = L; 73644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 73744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 73844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// changeTopLevelLoop - Replace the specified loop in the top-level loops 73944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// list with the indicated loop. 74044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void changeTopLevelLoop(LoopBase<BlockT> *OldLoop, 74144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *NewLoop) { 74244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::vector<LoopBase<BlockT>*>::iterator I = 74344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop); 74444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(I != TopLevelLoops.end() && "Old loop not at top level!"); 74544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson *I = NewLoop; 74644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 && 74744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson "Loops already embedded into a subloop!"); 74844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 74944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 75044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// addTopLevelLoop - This adds the specified loop to the collection of 75144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// top-level loops. 75244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void addTopLevelLoop(LoopBase<BlockT> *New) { 75344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(New->getParentLoop() == 0 && "Loop already in subloop!"); 75444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops.push_back(New); 75544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 75644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 75744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// removeBlock - This method completely removes BB from all data structures, 75844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// including all of the Loop objects it is nested in and our mapping from 75944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// BasicBlocks to loops. 76044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void removeBlock(BlockT *BB) { 76144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::map<BlockT *, LoopBase<BlockT>*>::iterator I = BBMap.find(BB); 76244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (I != BBMap.end()) { 763d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (LoopBase<BlockT> *L = I->second; L; L = L->getParentLoop()) 76444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson L->removeBlockFromLoop(BB); 76544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 76644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BBMap.erase(I); 76744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 76844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 76944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 77044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Internals 77144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 7722f46bb8178e30e3b845859a44b57c048db06ef84Dale Johannesen static bool isNotAlreadyContainedIn(const LoopBase<BlockT> *SubLoop, 7732f46bb8178e30e3b845859a44b57c048db06ef84Dale Johannesen const LoopBase<BlockT> *ParentLoop) { 77444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (SubLoop == 0) return true; 77544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (SubLoop == ParentLoop) return false; 77644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); 77744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 77844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 779d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson void Calculate(DominatorTreeBase<BlockT> &DT) { 78044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BlockT *RootNode = DT.getRootNode()->getBlock(); 78144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 78244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (df_iterator<BlockT*> NI = df_begin(RootNode), 78344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson NE = df_end(RootNode); NI != NE; ++NI) 78444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (LoopBase<BlockT> *L = ConsiderForLoop(*NI, DT)) 78544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops.push_back(L); 78644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 78744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 788d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson LoopBase<BlockT> *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) { 78944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node? 79044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 79144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson std::vector<BlockT *> TodoStack; 79244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 79344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Scan the predecessors of BB, checking to see if BB dominates any of 79444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // them. This identifies backedges which target this node... 795d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 796d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson for (typename InvBlockTraits::ChildIteratorType I = 797d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB); 798d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson I != E; ++I) 79944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (DT.dominates(BB, *I)) // If BB dominates it's predecessor... 80044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TodoStack.push_back(*I); 80144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 80244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (TodoStack.empty()) return 0; // No backedges to this block... 80344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 80444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Create a new loop to represent this basic block... 80544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *L = new LoopBase<BlockT>(BB); 80644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BBMap[BB] = L; 80744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 808e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson BlockT *EntryBlock = BB->getParent()->begin(); 80944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 81044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson while (!TodoStack.empty()) { // Process all the nodes in the loop 81144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BlockT *X = TodoStack.back(); 81244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TodoStack.pop_back(); 81344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 81444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (!L->contains(X) && // As of yet unprocessed?? 81544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson DT.dominates(EntryBlock, X)) { // X is reachable from entry block? 81644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Check to see if this block already belongs to a loop. If this occurs 817131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // then we have a case where a loop that is supposed to be a child of 818131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // the current loop was processed before the current loop. When this 819131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // occurs, this child loop gets added to a part of the current loop, 820131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // making it a sibling to the current loop. We have to reparent this 821131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // loop. 82244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (LoopBase<BlockT> *SubLoop = 82344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson const_cast<LoopBase<BlockT>*>(getLoopFor(X))) 824131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){ 82544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Remove the subloop from it's current parent... 82644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L); 82744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *SLP = SubLoop->ParentLoop; // SubLoopParent 82844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::vector<LoopBase<BlockT>*>::iterator I = 82944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop); 830131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?"); 83144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson SLP->SubLoops.erase(I); // Remove from parent... 83244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 83344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Add the subloop to THIS loop... 83444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson SubLoop->ParentLoop = L; 83544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson L->SubLoops.push_back(SubLoop); 83644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 83744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 83844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Normal case, add the block to our loop... 83944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson L->Blocks.push_back(X); 840d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson 841d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 842d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson 84344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Add all of the predecessors of X to the end of the work stack... 844d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X), 845d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson InvBlockTraits::child_end(X)); 84644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 84744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 84844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 84944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // If there are any loops nested within this loop, create them now! 85044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), 85144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson E = L->Blocks.end(); I != E; ++I) 85244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (LoopBase<BlockT> *NewLoop = ConsiderForLoop(*I, DT)) { 85344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson L->SubLoops.push_back(NewLoop); 85444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson NewLoop->ParentLoop = L; 85544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 85644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 85744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Add the basic blocks that comprise this loop to the BBMap so that this 85844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // loop can be found for them. 85944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // 86044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), 86144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson E = L->Blocks.end(); I != E; ++I) { 86244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::map<BlockT*, LoopBase<BlockT>*>::iterator BBMI = 863c418bf3dd593b5b2fe2f978930f6d0d6b17e344eDan Gohman BBMap.find(*I); 864c418bf3dd593b5b2fe2f978930f6d0d6b17e344eDan Gohman if (BBMI == BBMap.end()) // Not in map yet... 86544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BBMap.insert(BBMI, std::make_pair(*I, L)); // Must be at this level 86644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 86744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 86844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Now that we have a list of all of the child loops of this loop, check to 869131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // see if any of them should actually be nested inside of each other. We 870131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // can accidentally pull loops our of their parents, so we must make sure to 87144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // organize the loop nests correctly now. 87244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson { 87344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson std::map<BlockT*, LoopBase<BlockT>*> ContainingLoops; 87444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (unsigned i = 0; i != L->SubLoops.size(); ++i) { 87544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *Child = L->SubLoops[i]; 87644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(Child->getParentLoop() == L && "Not proper child loop?"); 87744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 87844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (LoopBase<BlockT> *ContainingLoop = 87944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson ContainingLoops[Child->getHeader()]) { 88044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // If there is already a loop which contains this loop, move this loop 88144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // into the containing loop. 88244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson MoveSiblingLoopInto(Child, ContainingLoop); 88344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson --i; // The loop got removed from the SubLoops list. 88444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } else { 885131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // This is currently considered to be a top-level loop. Check to see 886131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // if any of the contained blocks are loop headers for subloops we 887131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner // have already processed. 88844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) { 88944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *&BlockLoop = ContainingLoops[Child->Blocks[b]]; 89044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (BlockLoop == 0) { // Child block not processed yet... 89144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BlockLoop = Child; 89244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } else if (BlockLoop != Child) { 89344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *SubLoop = BlockLoop; 89444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Reparent all of the blocks which used to belong to BlockLoops 89544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j) 89644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson ContainingLoops[SubLoop->Blocks[j]] = Child; 89744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 89844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // There is already a loop which contains this block, that means 89944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // that we should reparent the loop which the block is currently 90044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // considered to belong to to be a child of this loop. 90144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson MoveSiblingLoopInto(SubLoop, Child); 90244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson --i; // We just shrunk the SubLoops list. 90344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 90444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 90544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 90644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 90744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 90844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 90944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson return L; 91044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 91144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 912131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside 913131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner /// of the NewParent Loop, instead of being a sibling of it. 91444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void MoveSiblingLoopInto(LoopBase<BlockT> *NewChild, 91544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *NewParent) { 91644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LoopBase<BlockT> *OldParent = NewChild->getParentLoop(); 91744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(OldParent && OldParent == NewParent->getParentLoop() && 91844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson NewChild != NewParent && "Not sibling loops!"); 91944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 92044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Remove NewChild from being a child of OldParent 92144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson typename std::vector<LoopBase<BlockT>*>::iterator I = 922131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), 923131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner NewChild); 92444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??"); 92544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson OldParent->SubLoops.erase(I); // Remove from parent's subloops list 92644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson NewChild->ParentLoop = 0; 92744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 92844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson InsertLoopInto(NewChild, NewParent); 92944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 93044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 931131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner /// InsertLoopInto - This inserts loop L into the specified parent loop. If 932131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner /// the parent loop contains a loop which should contain L, the loop gets 933131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner /// inserted into L instead. 93444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void InsertLoopInto(LoopBase<BlockT> *L, LoopBase<BlockT> *Parent) { 93544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson BlockT *LHeader = L->getHeader(); 936131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner assert(Parent->contains(LHeader) && 937131bd2ecf721749666111ec2dd1d32a20ae049b2Chris Lattner "This loop should not be inserted here!"); 93844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 93944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Check to see if it belongs in a child loop... 94034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size()); 94134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng i != e; ++i) 94244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson if (Parent->SubLoops[i]->contains(LHeader)) { 94344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson InsertLoopInto(L, Parent->SubLoops[i]); 94444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson return; 94544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 94644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 94744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // If not, insert it here! 94844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson Parent->SubLoops.push_back(L); 94944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson L->ParentLoop = Parent; 95044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 95144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 95244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // Debugging 95344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 95444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void print(std::ostream &OS, const Module* ) const { 95544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 95644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson TopLevelLoops[i]->print(OS); 95744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson #if 0 95844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson for (std::map<BasicBlock*, Loop*>::const_iterator I = BBMap.begin(), 95944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson E = BBMap.end(); I != E; ++I) 96044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson OS << "BB '" << I->first->getName() << "' level = " 96144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson << I->second->getLoopDepth() << "\n"; 96244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson #endif 96344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 96444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson}; 96544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 96644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersonclass LoopInfo : public FunctionPass { 9679d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LoopInfoBase<BasicBlock> LI; 96844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson friend class LoopBase<BasicBlock>; 9699d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman 9709d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman void operator=(const LoopInfo &); // do not implement 9719d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LoopInfo(const LoopInfo &); // do not implement 97244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersonpublic: 97344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson static char ID; // Pass identification, replacement for typeid 97444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 9759d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LoopInfo() : FunctionPass(&ID) {} 97644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 9779d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LoopInfoBase<BasicBlock>& getBase() { return LI; } 978d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson 97944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// iterator/begin/end - The interface to the top-level loops in the current 98044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// function. 98144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// 9829d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman typedef LoopInfoBase<BasicBlock>::iterator iterator; 9839d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline iterator begin() const { return LI.begin(); } 9849d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline iterator end() const { return LI.end(); } 9859d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman bool empty() const { return LI.empty(); } 98644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 98744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// getLoopFor - Return the inner most loop that BB lives in. If a basic 98844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// block is in no loop (for example the entry node), null is returned. 98944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// 99044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline Loop *getLoopFor(const BasicBlock *BB) const { 9919d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopFor(BB); 99244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 99344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 99444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// operator[] - same as getLoopFor... 99544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// 99644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline const Loop *operator[](const BasicBlock *BB) const { 9979d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopFor(BB); 99844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 99944a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 1000ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// getLoopDepth - Return the loop nesting level of the specified block. A 1001ba42d2b937160c970c8c6ea57573113c9265325fDan Gohman /// depth of 0 means the block is not inside any loop. 100244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson /// 100344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline unsigned getLoopDepth(const BasicBlock *BB) const { 10049d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopDepth(BB); 100544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 100644a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 100744a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson // isLoopHeader - True if the block is a loop header node 100844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline bool isLoopHeader(BasicBlock *BB) const { 10099d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.isLoopHeader(BB); 101044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 10110bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 10122b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// runOnFunction - Calculate the natural loop information. 10132b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 10147e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 1015facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 10169d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman virtual void releaseMemory() { LI.releaseMemory(); } 10175c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling 101844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson virtual void print(std::ostream &O, const Module* M = 0) const { 10199d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.print(O, M); 10205c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling } 1021918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner 1022f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 1023f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner 10244e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// removeLoop - This removes the specified top-level loop from this loop info 10254e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// object. The loop is not deleted, as it will presumably be inserted into 10264e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner /// another loop. 10279d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); } 10284e55b7d2c62de7efa0147e0579980de8b1df9123Chris Lattner 102946758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// changeLoopFor - Change the top-level loop that contains BB to the 103046758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// specified loop. This should be used by transformations that restructure 103146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// the loop hierarchy tree. 103244a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline void changeLoopFor(BasicBlock *BB, Loop *L) { 10339d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.changeLoopFor(BB, L); 103444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 103546758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 103646758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// changeTopLevelLoop - Replace the specified loop in the top-level loops 103746758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner /// list with the indicated loop. 103844a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) { 10399d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.changeTopLevelLoop(OldLoop, NewLoop); 104044a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 104146758a894f5d9ca7adc8ec03dd6adeb36b7eadb3Chris Lattner 1042072b163424491c85df6664a4e056aae5e07dc64dChris Lattner /// addTopLevelLoop - This adds the specified loop to the collection of 1043072b163424491c85df6664a4e056aae5e07dc64dChris Lattner /// top-level loops. 104444a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson inline void addTopLevelLoop(Loop *New) { 10459d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.addTopLevelLoop(New); 1046072b163424491c85df6664a4e056aae5e07dc64dChris Lattner } 1047072b163424491c85df6664a4e056aae5e07dc64dChris Lattner 10489afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// removeBlock - This method completely removes BB from all data structures, 10499afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// including all of the Loop objects it is nested in and our mapping from 10509afb24bf0847b9f2ff0bf3f7f7405dcbe42fa38bChris Lattner /// BasicBlocks to loops. 105144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson void removeBlock(BasicBlock *BB) { 10529d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.removeBlock(BB); 105344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson } 10540bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 10550bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1056e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla 10571db0a400370466e187ae06c96a1586c2c21409ddChris Lattner// Allow clients to walk the list of nested loops... 10581db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<const Loop*> { 10591db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef const Loop NodeType; 10609d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman typedef LoopInfo::iterator ChildIteratorType; 10611db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 10621db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(const Loop *L) { return L; } 10639769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 1064329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 10651db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 10669769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 1067329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 10681db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 10691db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 10701db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 10711db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<Loop*> { 10721db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef Loop NodeType; 10739d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman typedef LoopInfo::iterator ChildIteratorType; 10741db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 10751db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(Loop *L) { return L; } 10769769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 1077329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 10781db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 10799769ab22265b313171d201b5928688524a01bd87Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 1080329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 10811db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 10821db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 10831db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 1084019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Andersontemplate<class BlockT> 108544a95e06cc0bb3a2d617fe94235aee92b1951910Owen Andersonvoid LoopBase<BlockT>::addBasicBlockToLoop(BlockT *NewBB, 1086d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson LoopInfoBase<BlockT> &LIB) { 1087d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson assert((Blocks.empty() || LIB[getHeader()] == this) && 1088019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson "Incorrect LI specified for this loop!"); 1089019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson assert(NewBB && "Cannot add a null basic block to the loop!"); 1090d735ee85dbab8e4f66f9ec157f19956e0d11ec7aOwen Anderson assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!"); 109144a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson 1092019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Add the loop mapping to the LoopInfo object... 109344a95e06cc0bb3a2d617fe94235aee92b1951910Owen Anderson LIB.BBMap[NewBB] = this; 1094019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 1095019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson // Add the basic block to this loop and all parent loops... 1096019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson LoopBase<BlockT> *L = this; 1097019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson while (L) { 1098019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson L->Blocks.push_back(NewBB); 1099019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson L = L->getParentLoop(); 1100019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson } 1101019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson} 1102019b92a70c11319f5ab96c9f5e66e4e111a972f8Owen Anderson 1103d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 1104d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 11050bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#endif 1106