LoopInfo.h revision fbdf4bf1799bf9ea566fc0fc0507752590a6d559
148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// 26fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 56fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// This file was developed by the LLVM research group and is distributed under 66fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 76fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 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 12fe3ae1ed660925f06159ec89460d92148e049ffdChris 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 16fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// contained entirely within the function, the basic blocks the make up the 17fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// loop, the nesting depth of the loop, and the successor blocks of the loop. 18fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// 19fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// It can calculate on the fly a variety of different bits of information, such 20fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// as whether there is a preheader for the loop, the number of back edges to the 21fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner// header, and whether or not a particular block branches out of the loop. 220bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner// 230bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 240bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 250bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#ifndef LLVM_ANALYSIS_LOOP_INFO_H 260bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#define LLVM_ANALYSIS_LOOP_INFO_H 270bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 28facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner#include "llvm/Pass.h" 291db0a400370466e187ae06c96a1586c2c21409ddChris Lattner#include "Support/GraphTraits.h" 300bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#include <set> 310bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 348fc2f2072de83665ae20e06929e28317f449bcdfChris Lattnerclass DominatorSet; 358fc2f2072de83665ae20e06929e28317f449bcdfChris Lattnerclass LoopInfo; 360bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 370bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 382b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// Loop class - Instances of this class are used to represent loops that are 392b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// detected in the flow graph 402b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 410bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerclass Loop { 420bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner Loop *ParentLoop; 43697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<Loop*> SubLoops; // Loops contained entirely within this one 447dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner std::vector<BasicBlock*> Blocks; // First entry is the header node 457dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner std::vector<BasicBlock*> ExitBlocks; // Reachable blocks outside the loop 460bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner unsigned LoopDepth; // Nesting depth of this loop 470bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 480bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner Loop(const Loop &); // DO NOT IMPLEMENT 490bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner const Loop &operator=(const Loop &); // DO NOT IMPLEMENT 500bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 510bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 527dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner unsigned getLoopDepth() const { return LoopDepth; } 537dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner BasicBlock *getHeader() const { return Blocks.front(); } 547dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner Loop *getParentLoop() const { return ParentLoop; } 550bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 562b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// contains - Return true of the specified basic block is in this loop 57fbdf4bf1799bf9ea566fc0fc0507752590a6d559Misha Brukman /// 58a51b767df42019eb155281f3a64a16593c14f7e9Chris Lattner bool contains(const BasicBlock *BB) const; 590bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 60329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - Return the loops contained entirely within this loop. 612b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 62329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner typedef std::vector<Loop*>::const_iterator iterator; 63329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return SubLoops.begin(); } 64329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return SubLoops.end(); } 65fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 66fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getBlocks - Get a list of the basic blocks which make up this loop. 67fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 68fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner const std::vector<BasicBlock*> &getBlocks() const { return Blocks; } 69fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 70fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getExitBlocks - Return all of the successor blocks of this loop. These 71fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// are the blocks _outside of the current loop_ which are branched to. 72fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 73fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner const std::vector<BasicBlock*> &getExitBlocks() const { return ExitBlocks; } 740bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 752b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// isLoopExit - True if terminator in the block can branch to another block 76fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// that is outside of the current loop. The reached block should be in the 77fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// ExitBlocks list. 78fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 796b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman bool isLoopExit(const BasicBlock *BB) const; 806b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman 81fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// getNumBackEdges - Calculate the number of back edges to the loop header 82fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 836b290a54409f6bb6a0cc1c0446cd2b170a4b7addMisha Brukman unsigned getNumBackEdges() const; 849474dd68e8a050193ca4003940ac399e2b17cb6aChris Lattner 856bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner /// hasExitBlock - Return true if the current loop has the specified block as 866bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner /// an exit block... 876bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner bool hasExitBlock(BasicBlock *BB) const { 886bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 896bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner if (ExitBlocks[i] == BB) 906bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner return true; 916bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner return false; 926bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner } 936bc428133645e0a4308c1420c1693685e5f0a6f8Chris Lattner 942b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopPreheader - If there is a preheader for this loop, return it. A 952b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// loop has a preheader if there is only one edge to the header of the loop 962b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// from outside of the loop. If this is the case, the block branching to the 972b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// header of the loop is the preheader node. The "preheaders" pass can be 982b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// "Required" to ensure that there is always a preheader node for every loop. 992b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1002b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// This method returns null if there is no preheader for the loop (either 1012b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// because the loop is dead or because multiple blocks branch to the header 1022b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// node of this loop). 1032b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1042b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner BasicBlock *getLoopPreheader() const; 1052b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 106fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// addBasicBlockToLoop - This method is used by other analyses to update loop 107fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// information. NewBB is set to be a new member of the current loop. 1082b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// Because of this, it is added as a member of all parent loops, and is added 1092b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// to the specified LoopInfo object as being in the current basic block. It 1102b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// is not valid to replace the loop header with this method. 1112b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1122b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI); 1132b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 114f2e2925f95a271505f3ba103bac71b3b6d066c57Chris Lattner /// changeExitBlock - This method is used to update loop information. All 115f2e2925f95a271505f3ba103bac71b3b6d066c57Chris Lattner /// instances of the specified Old basic block are removed from the exit list 116fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// and replaced with New. 117fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner /// 118fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner void changeExitBlock(BasicBlock *Old, BasicBlock *New); 119fe3ae1ed660925f06159ec89460d92148e049ffdChris Lattner 1207dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void print(std::ostream &O, unsigned Depth = 0) const; 121f972cbd98c87a2b288943425c1bc92022a8de5c5Chris Lattner void dump() const; 1220bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate: 1230bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner friend class LoopInfo; 124de39b71455143f80602a27481c4de82a5cf25db0Chris Lattner inline Loop(BasicBlock *BB) : ParentLoop(0) { 125de39b71455143f80602a27481c4de82a5cf25db0Chris Lattner Blocks.push_back(BB); LoopDepth = 0; 126de39b71455143f80602a27481c4de82a5cf25db0Chris Lattner } 127918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner ~Loop() { 128918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 129918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner delete SubLoops[i]; 130918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner } 1310bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1320bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner void setLoopDepth(unsigned Level) { 1330bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner LoopDepth = Level; 134918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 1350bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner SubLoops[i]->setLoopDepth(Level+1); 1360bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 1370bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 1380bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1390bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1400bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1410bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner//===----------------------------------------------------------------------===// 1422b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// LoopInfo - This class builds and contains all of the top level loop 1432b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// structures in the specified function. 1442b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner/// 145f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattnerclass LoopInfo : public FunctionPass { 1460bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // BBMap - Mapping of basic blocks to the inner most loop they occur in 147a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner std::map<BasicBlock*, Loop*> BBMap; 148697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<Loop*> TopLevelLoops; 1492b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner friend class Loop; 1500bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerpublic: 151918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner ~LoopInfo() { releaseMemory(); } 1520bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 153329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// iterator/begin/end - The interface to the top-level loops in the current 154329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// function. 155329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner /// 156329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner typedef std::vector<Loop*>::const_iterator iterator; 157329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator begin() const { return TopLevelLoops.begin(); } 158329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner iterator end() const { return TopLevelLoops.end(); } 1590bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1602b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopFor - Return the inner most loop that BB lives in. If a basic 1612b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// block is in no loop (for example the entry node), null is returned. 1622b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1637e70829632f82de15db187845666aaca6e04b792Chris Lattner const Loop *getLoopFor(const BasicBlock *BB) const { 1647e70829632f82de15db187845666aaca6e04b792Chris Lattner std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB); 1650bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return I != BBMap.end() ? I->second : 0; 1660bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 1672b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner 1682b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// operator[] - same as getLoopFor... 1692b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1707e70829632f82de15db187845666aaca6e04b792Chris Lattner inline const Loop *operator[](const BasicBlock *BB) const { 1710bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return getLoopFor(BB); 1720bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 1730bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1742b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getLoopDepth - Return the loop nesting level of the specified block... 1752b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1767e70829632f82de15db187845666aaca6e04b792Chris Lattner unsigned getLoopDepth(const BasicBlock *BB) const { 1770bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner const Loop *L = getLoopFor(BB); 1780bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return L ? L->getLoopDepth() : 0; 1790bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 1800bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1810bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner // isLoopHeader - True if the block is a loop header node 182a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner bool isLoopHeader(BasicBlock *BB) const { 1830bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner return getLoopFor(BB)->getHeader() == BB; 1840bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner } 1850bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 1862b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// runOnFunction - Calculate the natural loop information. 1872b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 1887e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 189facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 190918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner virtual void releaseMemory(); 19197f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner void print(std::ostream &O) const; 192918c4ecb0c1c85adad760fb9d7faae088171d324Chris Lattner 1932b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// getAnalysisUsage - Requires dominator sets 1942b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner /// 195f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 196f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner 197e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla static void stub(); // Noop 1980bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattnerprivate: 199facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner void Calculate(const DominatorSet &DS); 200a298d27808ecb8ffb574d6e50f56601db2ec5fdaChris Lattner Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS); 2017dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent); 2027dd46b09c0f1b6b93f03a80953046d38697fba82Chris Lattner void InsertLoopInto(Loop *L, Loop *Parent); 2030bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner}; 2040bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner 205e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla 2062b7bb7a986545b5ec877416278dc126a35ab6970Chris Lattner// Make sure that any clients of this file link in LoopInfo.cpp 207e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shuklastatic IncludeFile 208e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand ShuklaLOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub); 209e0b6b78e095f7dea9589e8df5ec4521e346ad005Anand Shukla 2101db0a400370466e187ae06c96a1586c2c21409ddChris Lattner// Allow clients to walk the list of nested loops... 2111db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<const Loop*> { 2121db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef const Loop NodeType; 2131db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef std::vector<Loop*>::const_iterator ChildIteratorType; 2141db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 2151db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(const Loop *L) { return L; } 2161db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 217329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 2181db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 2191db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static inline ChildIteratorType child_end(NodeType *N) { 220329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 2211db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 2221db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 2231db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 2241db0a400370466e187ae06c96a1586c2c21409ddChris Lattnertemplate <> struct GraphTraits<Loop*> { 2251db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef Loop NodeType; 2261db0a400370466e187ae06c96a1586c2c21409ddChris Lattner typedef std::vector<Loop*>::const_iterator ChildIteratorType; 2271db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 2281db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static NodeType *getEntryNode(Loop *L) { return L; } 2291db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 230329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->begin(); 2311db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 2321db0a400370466e187ae06c96a1586c2c21409ddChris Lattner static inline ChildIteratorType child_end(NodeType *N) { 233329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner return N->end(); 2341db0a400370466e187ae06c96a1586c2c21409ddChris Lattner } 2351db0a400370466e187ae06c96a1586c2c21409ddChris Lattner}; 2361db0a400370466e187ae06c96a1586c2c21409ddChris Lattner 237d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 238d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2390bbe58f073b4b4a6f68b3e2ee6074fc314e8d19fChris Lattner#endif 240