1//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// This file defines iterators to visit the basic blocks within a loop. 9// 10// These iterators currently visit blocks within subloops as well. 11// Unfortunately we have no efficient way of summarizing loop exits which would 12// allow skipping subloops during traversal. 13// 14// If you want to visit all blocks in a loop and don't need an ordered traveral, 15// use Loop::block_begin() instead. 16// 17// This is intentionally designed to work with ill-formed loops in which the 18// backedge has been deleted. The only prerequisite is that all blocks 19// contained within the loop according to the most recent LoopInfo analysis are 20// reachable from the loop header. 21//===----------------------------------------------------------------------===// 22 23#ifndef LLVM_ANALYSIS_LOOPITERATOR_H 24#define LLVM_ANALYSIS_LOOPITERATOR_H 25 26#include "llvm/ADT/PostOrderIterator.h" 27#include "llvm/Analysis/LoopInfo.h" 28 29namespace llvm { 30 31class LoopBlocksTraversal; 32 33// A traits type that is intended to be used in graph algorithms. The graph 34// traits starts at the loop header, and traverses the BasicBlocks that are in 35// the loop body, but not the loop header. Since the loop header is skipped, 36// the back edges are excluded. 37// 38// TODO: Explore the possibility to implement LoopBlocksTraversal in terms of 39// LoopBodyTraits, so that insertEdge doesn't have to be specialized. 40struct LoopBodyTraits { 41 using NodeRef = std::pair<const Loop *, BasicBlock *>; 42 43 // This wraps a const Loop * into the iterator, so we know which edges to 44 // filter out. 45 class WrappedSuccIterator 46 : public iterator_adaptor_base< 47 WrappedSuccIterator, succ_iterator, 48 typename std::iterator_traits<succ_iterator>::iterator_category, 49 NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> { 50 using BaseT = iterator_adaptor_base< 51 WrappedSuccIterator, succ_iterator, 52 typename std::iterator_traits<succ_iterator>::iterator_category, 53 NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>; 54 55 const Loop *L; 56 57 public: 58 WrappedSuccIterator(succ_iterator Begin, const Loop *L) 59 : BaseT(Begin), L(L) {} 60 61 NodeRef operator*() const { return {L, *I}; } 62 }; 63 64 struct LoopBodyFilter { 65 bool operator()(NodeRef N) const { 66 const Loop *L = N.first; 67 return N.second != L->getHeader() && L->contains(N.second); 68 } 69 }; 70 71 using ChildIteratorType = 72 filter_iterator<WrappedSuccIterator, LoopBodyFilter>; 73 74 static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; } 75 76 static ChildIteratorType child_begin(NodeRef Node) { 77 return make_filter_range(make_range<WrappedSuccIterator>( 78 {succ_begin(Node.second), Node.first}, 79 {succ_end(Node.second), Node.first}), 80 LoopBodyFilter{}) 81 .begin(); 82 } 83 84 static ChildIteratorType child_end(NodeRef Node) { 85 return make_filter_range(make_range<WrappedSuccIterator>( 86 {succ_begin(Node.second), Node.first}, 87 {succ_end(Node.second), Node.first}), 88 LoopBodyFilter{}) 89 .end(); 90 } 91}; 92 93/// Store the result of a depth first search within basic blocks contained by a 94/// single loop. 95/// 96/// TODO: This could be generalized for any CFG region, or the entire CFG. 97class LoopBlocksDFS { 98public: 99 /// Postorder list iterators. 100 typedef std::vector<BasicBlock*>::const_iterator POIterator; 101 typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator; 102 103 friend class LoopBlocksTraversal; 104 105private: 106 Loop *L; 107 108 /// Map each block to its postorder number. A block is only mapped after it is 109 /// preorder visited by DFS. It's postorder number is initially zero and set 110 /// to nonzero after it is finished by postorder traversal. 111 DenseMap<BasicBlock*, unsigned> PostNumbers; 112 std::vector<BasicBlock*> PostBlocks; 113 114public: 115 LoopBlocksDFS(Loop *Container) : 116 L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { 117 PostBlocks.reserve(Container->getNumBlocks()); 118 } 119 120 Loop *getLoop() const { return L; } 121 122 /// Traverse the loop blocks and store the DFS result. 123 void perform(LoopInfo *LI); 124 125 /// Return true if postorder numbers are assigned to all loop blocks. 126 bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } 127 128 /// Iterate over the cached postorder blocks. 129 POIterator beginPostorder() const { 130 assert(isComplete() && "bad loop DFS"); 131 return PostBlocks.begin(); 132 } 133 POIterator endPostorder() const { return PostBlocks.end(); } 134 135 /// Reverse iterate over the cached postorder blocks. 136 RPOIterator beginRPO() const { 137 assert(isComplete() && "bad loop DFS"); 138 return PostBlocks.rbegin(); 139 } 140 RPOIterator endRPO() const { return PostBlocks.rend(); } 141 142 /// Return true if this block has been preorder visited. 143 bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } 144 145 /// Return true if this block has a postorder number. 146 bool hasPostorder(BasicBlock *BB) const { 147 DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 148 return I != PostNumbers.end() && I->second; 149 } 150 151 /// Get a block's postorder number. 152 unsigned getPostorder(BasicBlock *BB) const { 153 DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 154 assert(I != PostNumbers.end() && "block not visited by DFS"); 155 assert(I->second && "block not finished by DFS"); 156 return I->second; 157 } 158 159 /// Get a block's reverse postorder number. 160 unsigned getRPO(BasicBlock *BB) const { 161 return 1 + PostBlocks.size() - getPostorder(BB); 162 } 163 164 void clear() { 165 PostNumbers.clear(); 166 PostBlocks.clear(); 167 } 168}; 169 170/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end() 171/// interface for the DFS reverse post-order traversal of blocks in a loop body. 172class LoopBlocksRPO { 173private: 174 LoopBlocksDFS DFS; 175 176public: 177 LoopBlocksRPO(Loop *Container) : DFS(Container) {} 178 179 /// Traverse the loop blocks and store the DFS result. 180 void perform(LoopInfo *LI) { 181 DFS.perform(LI); 182 } 183 184 /// Reverse iterate over the cached postorder blocks. 185 LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); } 186 LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); } 187}; 188 189/// Specialize po_iterator_storage to record postorder numbers. 190template<> class po_iterator_storage<LoopBlocksTraversal, true> { 191 LoopBlocksTraversal &LBT; 192public: 193 po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} 194 // These functions are defined below. 195 bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To); 196 void finishPostorder(BasicBlock *BB); 197}; 198 199/// Traverse the blocks in a loop using a depth-first search. 200class LoopBlocksTraversal { 201public: 202 /// Graph traversal iterator. 203 typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 204 205private: 206 LoopBlocksDFS &DFS; 207 LoopInfo *LI; 208 209public: 210 LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 211 DFS(Storage), LI(LInfo) {} 212 213 /// Postorder traversal over the graph. This only needs to be done once. 214 /// po_iterator "automatically" calls back to visitPreorder and 215 /// finishPostorder to record the DFS result. 216 POTIterator begin() { 217 assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); 218 assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); 219 return po_ext_begin(DFS.L->getHeader(), *this); 220 } 221 POTIterator end() { 222 // po_ext_end interface requires a basic block, but ignores its value. 223 return po_ext_end(DFS.L->getHeader(), *this); 224 } 225 226 /// Called by po_iterator upon reaching a block via a CFG edge. If this block 227 /// is contained in the loop and has not been visited, then mark it preorder 228 /// visited and return true. 229 /// 230 /// TODO: If anyone is interested, we could record preorder numbers here. 231 bool visitPreorder(BasicBlock *BB) { 232 if (!DFS.L->contains(LI->getLoopFor(BB))) 233 return false; 234 235 return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 236 } 237 238 /// Called by po_iterator each time it advances, indicating a block's 239 /// postorder. 240 void finishPostorder(BasicBlock *BB) { 241 assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 242 DFS.PostBlocks.push_back(BB); 243 DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 244 } 245}; 246 247inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( 248 Optional<BasicBlock *> From, BasicBlock *To) { 249 return LBT.visitPreorder(To); 250} 251 252inline void po_iterator_storage<LoopBlocksTraversal, true>:: 253finishPostorder(BasicBlock *BB) { 254 LBT.finishPostorder(BB); 255} 256 257} // End namespace llvm 258 259#endif 260