15207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===// 25207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 35207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// The LLVM Compiler Infrastructure 45207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 55207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// This file is distributed under the University of Illinois Open Source 65207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// License. See LICENSE.TXT for details. 75207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 85207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick//===----------------------------------------------------------------------===// 95207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// This file defines iterators to visit the basic blocks within a loop. 105207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 115207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// These iterators currently visit blocks within subloops as well. 125207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// Unfortunately we have no efficient way of summarizing loop exits which would 135207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// allow skipping subloops during traversal. 145207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 155207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// If you want to visit all blocks in a loop and don't need an ordered traveral, 165207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// use Loop::block_begin() instead. 175207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// 185207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// This is intentionally designed to work with ill-formed loops in which the 195207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// backedge has been deleted. The only prerequisite is that all blocks 205207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// contained within the loop according to the most recent LoopInfo analysis are 215207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick// reachable from the loop header. 225207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick//===----------------------------------------------------------------------===// 235207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 24674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_LOOPITERATOR_H 25674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_LOOPITERATOR_H 265207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 275207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick#include "llvm/ADT/PostOrderIterator.h" 285207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick#include "llvm/Analysis/LoopInfo.h" 295207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 305207936a24ab9e0bfaa10e798625df65143e3716Andrew Tricknamespace llvm { 315207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 325207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickclass LoopBlocksTraversal; 335207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 345207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// Store the result of a depth first search within basic blocks contained by a 355207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// single loop. 365207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// 375207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// TODO: This could be generalized for any CFG region, or the entire CFG. 385207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickclass LoopBlocksDFS { 395207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickpublic: 405207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Postorder list iterators. 415207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick typedef std::vector<BasicBlock*>::const_iterator POIterator; 425207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator; 435207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 445207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick friend class LoopBlocksTraversal; 455207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 465207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickprivate: 475207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick Loop *L; 485207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 495207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Map each block to its postorder number. A block is only mapped after it is 505207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// preorder visited by DFS. It's postorder number is initially zero and set 515207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// to nonzero after it is finished by postorder traversal. 525207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DenseMap<BasicBlock*, unsigned> PostNumbers; 535207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick std::vector<BasicBlock*> PostBlocks; 545207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 555207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickpublic: 565207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick LoopBlocksDFS(Loop *Container) : 575207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { 585207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick PostBlocks.reserve(Container->getNumBlocks()); 595207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 605207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 615207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick Loop *getLoop() const { return L; } 625207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 632d31ae3d9dfb153f081a5521374b2b42befd50a1Andrew Trick /// Traverse the loop blocks and store the DFS result. 642d31ae3d9dfb153f081a5521374b2b42befd50a1Andrew Trick void perform(LoopInfo *LI); 652d31ae3d9dfb153f081a5521374b2b42befd50a1Andrew Trick 665207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Return true if postorder numbers are assigned to all loop blocks. 675207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } 685207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 695207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Iterate over the cached postorder blocks. 705207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick POIterator beginPostorder() const { 715207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(isComplete() && "bad loop DFS"); 725207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return PostBlocks.begin(); 735207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 745207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick POIterator endPostorder() const { return PostBlocks.end(); } 755207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 765207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Reverse iterate over the cached postorder blocks. 775207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick RPOIterator beginRPO() const { 785207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(isComplete() && "bad loop DFS"); 795207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return PostBlocks.rbegin(); 805207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 815207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick RPOIterator endRPO() const { return PostBlocks.rend(); } 825207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 835207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Return true if this block has been preorder visited. 845207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } 855207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 865207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Return true if this block has a postorder number. 875207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick bool hasPostorder(BasicBlock *BB) const { 885207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 895207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return I != PostNumbers.end() && I->second; 905207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 915207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 925207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Get a block's postorder number. 935207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick unsigned getPostorder(BasicBlock *BB) const { 945207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 955207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(I != PostNumbers.end() && "block not visited by DFS"); 965207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(I->second && "block not finished by DFS"); 975207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return I->second; 985207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 995207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1005207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Get a block's reverse postorder number. 1015207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick unsigned getRPO(BasicBlock *BB) const { 1025207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return 1 + PostBlocks.size() - getPostorder(BB); 1035207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1045207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1055207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick void clear() { 1065207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick PostNumbers.clear(); 1075207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick PostBlocks.clear(); 1085207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1095207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick}; 1105207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 11131f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen/// Specialize po_iterator_storage to record postorder numbers. 11231f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesentemplate<> class po_iterator_storage<LoopBlocksTraversal, true> { 11331f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen LoopBlocksTraversal &LBT; 11431f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesenpublic: 11531f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} 11631f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen // These functions are defined below. 11731f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen bool insertEdge(BasicBlock *From, BasicBlock *To); 11831f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen void finishPostorder(BasicBlock *BB); 11931f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen}; 12031f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen 1215207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// Traverse the blocks in a loop using a depth-first search. 1225207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickclass LoopBlocksTraversal { 1235207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickpublic: 1245207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Graph traversal iterator. 125d8a2f3ab91e90a1e1da2061410bb08b18650c9eeAndrew Trick typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 1265207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1275207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickprivate: 1285207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick LoopBlocksDFS &DFS; 1295207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick LoopInfo *LI; 1305207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1315207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickpublic: 1325207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 1335207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DFS(Storage), LI(LInfo) {} 1345207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1355207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Postorder traversal over the graph. This only needs to be done once. 1365207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// po_iterator "automatically" calls back to visitPreorder and 1375207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// finishPostorder to record the DFS result. 1385207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick POTIterator begin() { 1395207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); 140d8a2f3ab91e90a1e1da2061410bb08b18650c9eeAndrew Trick assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); 141d8a2f3ab91e90a1e1da2061410bb08b18650c9eeAndrew Trick return po_ext_begin(DFS.L->getHeader(), *this); 1425207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1435207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick POTIterator end() { 144d8a2f3ab91e90a1e1da2061410bb08b18650c9eeAndrew Trick // po_ext_end interface requires a basic block, but ignores its value. 145d8a2f3ab91e90a1e1da2061410bb08b18650c9eeAndrew Trick return po_ext_end(DFS.L->getHeader(), *this); 1465207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1475207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1485207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Called by po_iterator upon reaching a block via a CFG edge. If this block 1495207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// is contained in the loop and has not been visited, then mark it preorder 1505207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// visited and return true. 1515207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// 1525207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// TODO: If anyone is interested, we could record preorder numbers here. 1535207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick bool visitPreorder(BasicBlock *BB) { 1545207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick if (!DFS.L->contains(LI->getLoopFor(BB))) 1555207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return false; 1565207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1575207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 1585207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1595207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1605207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// Called by po_iterator each time it advances, indicating a block's 1615207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick /// postorder. 1625207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick void finishPostorder(BasicBlock *BB) { 1635207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 1645207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DFS.PostBlocks.push_back(BB); 1655207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 1665207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick } 1675207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick}; 1685207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 16931f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Oleseninline bool po_iterator_storage<LoopBlocksTraversal, true>:: 17031f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund OleseninsertEdge(BasicBlock *From, BasicBlock *To) { 17131f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen return LBT.visitPreorder(To); 17231f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen} 17331f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen 17431f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Oleseninline void po_iterator_storage<LoopBlocksTraversal, true>:: 17531f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund OlesenfinishPostorder(BasicBlock *BB) { 17631f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen LBT.finishPostorder(BB); 17731f18eeb2bff53ce48c9c980f0b0676401d593c8Jakob Stoklund Olesen} 1785207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1795207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick} // End namespace llvm 1805207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 1815207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick#endif 182