1 //===- GenericCycleInfo.h - Info for Cycles in any IR ------*- 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 /// 9 /// \file 10 /// \brief Find all cycles in a control-flow graph, including irreducible loops. 11 /// 12 /// See docs/CycleTerminology.rst for a formal definition of cycles. 13 /// 14 /// Briefly: 15 /// - A cycle is a generalization of a loop which can represent 16 /// irreducible control flow. 17 /// - Cycles identified in a program are implementation defined, 18 /// depending on the DFS traversal chosen. 19 /// - Cycles are well-nested, and form a forest with a parent-child 20 /// relationship. 21 /// - In any choice of DFS, every natural loop L is represented by a 22 /// unique cycle C which is a superset of L. 23 /// - In the absence of irreducible control flow, the cycles are 24 /// exactly the natural loops in the program. 25 /// 26 //===----------------------------------------------------------------------===// 27 28 #ifndef LLVM_ADT_GENERICCYCLEINFO_H 29 #define LLVM_ADT_GENERICCYCLEINFO_H 30 31 #include "llvm/ADT/ArrayRef.h" 32 #include "llvm/ADT/DenseMap.h" 33 #include "llvm/ADT/GenericSSAContext.h" 34 #include "llvm/ADT/GraphTraits.h" 35 #include "llvm/ADT/SmallVector.h" 36 #include "llvm/ADT/iterator.h" 37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/Printable.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <vector> 41 42 namespace llvm { 43 44 template <typename ContextT> class GenericCycleInfo; 45 template <typename ContextT> class GenericCycleInfoCompute; 46 47 /// A possibly irreducible generalization of a \ref Loop. 48 template <typename ContextT> class GenericCycle { 49 public: 50 using BlockT = typename ContextT::BlockT; 51 using FunctionT = typename ContextT::FunctionT; 52 template <typename> friend class GenericCycleInfo; 53 template <typename> friend class GenericCycleInfoCompute; 54 55 private: 56 /// The parent cycle. Is null for the root "cycle". Top-level cycles point 57 /// at the root. 58 GenericCycle *ParentCycle = nullptr; 59 60 /// The entry block(s) of the cycle. The header is the only entry if 61 /// this is a loop. Is empty for the root "cycle", to avoid 62 /// unnecessary memory use. 63 SmallVector<BlockT *, 1> Entries; 64 65 /// Child cycles, if any. 66 std::vector<std::unique_ptr<GenericCycle>> Children; 67 68 /// Basic blocks that are contained in the cycle, including entry blocks, 69 /// and including blocks that are part of a child cycle. 70 std::vector<BlockT *> Blocks; 71 72 /// Depth of the cycle in the tree. The root "cycle" is at depth 0. 73 /// 74 /// \note Depths are not necessarily contiguous. However, child loops always 75 /// have strictly greater depth than their parents, and sibling loops 76 /// always have the same depth. 77 unsigned Depth = 0; 78 79 void clear() { 80 Entries.clear(); 81 Children.clear(); 82 Blocks.clear(); 83 Depth = 0; 84 ParentCycle = nullptr; 85 } 86 87 void appendEntry(BlockT *Block) { Entries.push_back(Block); } 88 void appendBlock(BlockT *Block) { Blocks.push_back(Block); } 89 90 GenericCycle(const GenericCycle &) = delete; 91 GenericCycle &operator=(const GenericCycle &) = delete; 92 GenericCycle(GenericCycle &&Rhs) = delete; 93 GenericCycle &operator=(GenericCycle &&Rhs) = delete; 94 95 public: 96 GenericCycle() = default; 97 98 /// \brief Whether the cycle is a natural loop. 99 bool isReducible() const { return Entries.size() == 1; } 100 101 BlockT *getHeader() const { return Entries[0]; } 102 103 const SmallVectorImpl<BlockT *> & getEntries() const { 104 return Entries; 105 } 106 107 /// \brief Return whether \p Block is an entry block of the cycle. 108 bool isEntry(BlockT *Block) const { return is_contained(Entries, Block); } 109 110 /// \brief Return whether \p Block is contained in the cycle. 111 bool contains(const BlockT *Block) const { 112 return is_contained(Blocks, Block); 113 } 114 115 /// \brief Returns true iff this cycle contains \p C. 116 /// 117 /// Note: Non-strict containment check, i.e. returns true if C is the 118 /// same cycle. 119 bool contains(const GenericCycle *C) const; 120 121 const GenericCycle *getParentCycle() const { return ParentCycle; } 122 GenericCycle *getParentCycle() { return ParentCycle; } 123 unsigned getDepth() const { return Depth; } 124 125 /// Return all of the successor blocks of this cycle. 126 /// 127 /// These are the blocks _outside of the current cycle_ which are 128 /// branched to. 129 void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const; 130 131 /// Return the preheader block for this cycle. Pre-header is well-defined for 132 /// reducible cycle in docs/LoopTerminology.rst as: the only one entering 133 /// block and its only edge is to the entry block. Return null for irreducible 134 /// cycles. 135 BlockT *getCyclePreheader() const; 136 137 /// If the cycle has exactly one entry with exactly one predecessor, return 138 /// it, otherwise return nullptr. 139 BlockT *getCyclePredecessor() const; 140 141 /// Iteration over child cycles. 142 //@{ 143 using const_child_iterator_base = 144 typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator; 145 struct const_child_iterator 146 : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> { 147 using Base = 148 iterator_adaptor_base<const_child_iterator, const_child_iterator_base>; 149 150 const_child_iterator() = default; 151 explicit const_child_iterator(const_child_iterator_base I) : Base(I) {} 152 153 const const_child_iterator_base &wrapped() { return Base::wrapped(); } 154 GenericCycle *operator*() const { return Base::I->get(); } 155 }; 156 157 const_child_iterator child_begin() const { 158 return const_child_iterator{Children.begin()}; 159 } 160 const_child_iterator child_end() const { 161 return const_child_iterator{Children.end()}; 162 } 163 size_t getNumChildren() const { return Children.size(); } 164 iterator_range<const_child_iterator> children() const { 165 return llvm::make_range(const_child_iterator{Children.begin()}, 166 const_child_iterator{Children.end()}); 167 } 168 //@} 169 170 /// Iteration over blocks in the cycle (including entry blocks). 171 //@{ 172 using const_block_iterator = typename std::vector<BlockT *>::const_iterator; 173 174 const_block_iterator block_begin() const { 175 return const_block_iterator{Blocks.begin()}; 176 } 177 const_block_iterator block_end() const { 178 return const_block_iterator{Blocks.end()}; 179 } 180 size_t getNumBlocks() const { return Blocks.size(); } 181 iterator_range<const_block_iterator> blocks() const { 182 return llvm::make_range(block_begin(), block_end()); 183 } 184 //@} 185 186 /// Iteration over entry blocks. 187 //@{ 188 using const_entry_iterator = 189 typename SmallVectorImpl<BlockT *>::const_iterator; 190 191 size_t getNumEntries() const { return Entries.size(); } 192 iterator_range<const_entry_iterator> entries() const { 193 return llvm::make_range(Entries.begin(), Entries.end()); 194 } 195 //@} 196 197 Printable printEntries(const ContextT &Ctx) const { 198 return Printable([this, &Ctx](raw_ostream &Out) { 199 bool First = true; 200 for (auto *Entry : Entries) { 201 if (!First) 202 Out << ' '; 203 First = false; 204 Out << Ctx.print(Entry); 205 } 206 }); 207 } 208 209 Printable print(const ContextT &Ctx) const { 210 return Printable([this, &Ctx](raw_ostream &Out) { 211 Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')'; 212 213 for (auto *Block : Blocks) { 214 if (isEntry(Block)) 215 continue; 216 217 Out << ' ' << Ctx.print(Block); 218 } 219 }); 220 } 221 }; 222 223 /// \brief Cycle information for a function. 224 template <typename ContextT> class GenericCycleInfo { 225 public: 226 using BlockT = typename ContextT::BlockT; 227 using CycleT = GenericCycle<ContextT>; 228 using FunctionT = typename ContextT::FunctionT; 229 template <typename> friend class GenericCycle; 230 template <typename> friend class GenericCycleInfoCompute; 231 232 private: 233 ContextT Context; 234 235 /// Map basic blocks to their inner-most containing cycle. 236 DenseMap<BlockT *, CycleT *> BlockMap; 237 238 /// Map basic blocks to their top level containing cycle. 239 DenseMap<BlockT *, CycleT *> BlockMapTopLevel; 240 241 /// Outermost cycles discovered by any DFS. 242 /// 243 /// Note: The implementation treats the nullptr as the parent of 244 /// every top-level cycle. See \ref contains for an example. 245 std::vector<std::unique_ptr<CycleT>> TopLevelCycles; 246 247 /// Move \p Child to \p NewParent by manipulating Children vectors. 248 /// 249 /// Note: This is an incomplete operation that does not update the depth of 250 /// the subtree. 251 void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child); 252 253 public: 254 GenericCycleInfo() = default; 255 GenericCycleInfo(GenericCycleInfo &&) = default; 256 GenericCycleInfo &operator=(GenericCycleInfo &&) = default; 257 258 void clear(); 259 void compute(FunctionT &F); 260 261 FunctionT *getFunction() const { return Context.getFunction(); } 262 const ContextT &getSSAContext() const { return Context; } 263 264 CycleT *getCycle(const BlockT *Block) const; 265 unsigned getCycleDepth(const BlockT *Block) const; 266 CycleT *getTopLevelParentCycle(BlockT *Block); 267 268 /// Methods for debug and self-test. 269 //@{ 270 #ifndef NDEBUG 271 bool validateTree() const; 272 #endif 273 void print(raw_ostream &Out) const; 274 void dump() const { print(dbgs()); } 275 //@} 276 277 /// Iteration over top-level cycles. 278 //@{ 279 using const_toplevel_iterator_base = 280 typename std::vector<std::unique_ptr<CycleT>>::const_iterator; 281 struct const_toplevel_iterator 282 : iterator_adaptor_base<const_toplevel_iterator, 283 const_toplevel_iterator_base> { 284 using Base = iterator_adaptor_base<const_toplevel_iterator, 285 const_toplevel_iterator_base>; 286 287 const_toplevel_iterator() = default; 288 explicit const_toplevel_iterator(const_toplevel_iterator_base I) 289 : Base(I) {} 290 291 const const_toplevel_iterator_base &wrapped() { return Base::wrapped(); } 292 CycleT *operator*() const { return Base::I->get(); } 293 }; 294 295 const_toplevel_iterator toplevel_begin() const { 296 return const_toplevel_iterator{TopLevelCycles.begin()}; 297 } 298 const_toplevel_iterator toplevel_end() const { 299 return const_toplevel_iterator{TopLevelCycles.end()}; 300 } 301 302 iterator_range<const_toplevel_iterator> toplevel_cycles() const { 303 return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()}, 304 const_toplevel_iterator{TopLevelCycles.end()}); 305 } 306 //@} 307 }; 308 309 /// \brief GraphTraits for iterating over a sub-tree of the CycleT tree. 310 template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits { 311 using NodeRef = CycleRefT; 312 313 using nodes_iterator = ChildIteratorT; 314 using ChildIteratorType = nodes_iterator; 315 316 static NodeRef getEntryNode(NodeRef Graph) { return Graph; } 317 318 static ChildIteratorType child_begin(NodeRef Ref) { 319 return Ref->child_begin(); 320 } 321 static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); } 322 323 // Not implemented: 324 // static nodes_iterator nodes_begin(GraphType *G) 325 // static nodes_iterator nodes_end (GraphType *G) 326 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 327 328 // typedef EdgeRef - Type of Edge token in the graph, which should 329 // be cheap to copy. 330 // typedef ChildEdgeIteratorType - Type used to iterate over children edges in 331 // graph, dereference to a EdgeRef. 332 333 // static ChildEdgeIteratorType child_edge_begin(NodeRef) 334 // static ChildEdgeIteratorType child_edge_end(NodeRef) 335 // Return iterators that point to the beginning and ending of the 336 // edge list for the given callgraph node. 337 // 338 // static NodeRef edge_dest(EdgeRef) 339 // Return the destination node of an edge. 340 // static unsigned size (GraphType *G) 341 // Return total number of nodes in the graph 342 }; 343 344 template <typename BlockT> 345 struct GraphTraits<const GenericCycle<BlockT> *> 346 : CycleGraphTraits<const GenericCycle<BlockT> *, 347 typename GenericCycle<BlockT>::const_child_iterator> {}; 348 template <typename BlockT> 349 struct GraphTraits<GenericCycle<BlockT> *> 350 : CycleGraphTraits<GenericCycle<BlockT> *, 351 typename GenericCycle<BlockT>::const_child_iterator> {}; 352 353 } // namespace llvm 354 355 #endif // LLVM_ADT_GENERICCYCLEINFO_H 356