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