LLVM 17.0.0git
GenericCycleInfo.h
Go to the documentation of this file.
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"
36#include "llvm/ADT/iterator.h"
37#include "llvm/Support/Debug.h"
40#include <vector>
41
42namespace llvm {
43
44template <typename ContextT> class GenericCycleInfo;
45template <typename ContextT> class GenericCycleInfoCompute;
46
47/// A possibly irreducible generalization of a \ref Loop.
48template <typename ContextT> class GenericCycle {
49public:
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
55private:
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.
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
95public:
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
104 return Entries;
105 }
106
107 /// \brief Return whether \p Block is an entry block of the cycle.
108 bool isEntry(const BlockT *Block) const {
109 return is_contained(Entries, Block);
110 }
111
112 /// \brief Return whether \p Block is contained in the cycle.
113 bool contains(const BlockT *Block) const {
114 return is_contained(Blocks, Block);
115 }
116
117 /// \brief Returns true iff this cycle contains \p C.
118 ///
119 /// Note: Non-strict containment check, i.e. returns true if C is the
120 /// same cycle.
121 bool contains(const GenericCycle *C) const;
122
123 const GenericCycle *getParentCycle() const { return ParentCycle; }
124 GenericCycle *getParentCycle() { return ParentCycle; }
125 unsigned getDepth() const { return Depth; }
126
127 /// Return all of the successor blocks of this cycle.
128 ///
129 /// These are the blocks _outside of the current cycle_ which are
130 /// branched to.
131 void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
132
133 /// Return the preheader block for this cycle. Pre-header is well-defined for
134 /// reducible cycle in docs/LoopTerminology.rst as: the only one entering
135 /// block and its only edge is to the entry block. Return null for irreducible
136 /// cycles.
137 BlockT *getCyclePreheader() const;
138
139 /// If the cycle has exactly one entry with exactly one predecessor, return
140 /// it, otherwise return nullptr.
142
143 /// Iteration over child cycles.
144 //@{
146 typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
148 : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
149 using Base =
151
154
156 GenericCycle *operator*() const { return Base::I->get(); }
157 };
158
160 return const_child_iterator{Children.begin()};
161 }
163 return const_child_iterator{Children.end()};
164 }
165 size_t getNumChildren() const { return Children.size(); }
167 return llvm::make_range(const_child_iterator{Children.begin()},
168 const_child_iterator{Children.end()});
169 }
170 //@}
171
172 /// Iteration over blocks in the cycle (including entry blocks).
173 //@{
174 using const_block_iterator = typename std::vector<BlockT *>::const_iterator;
175
177 return const_block_iterator{Blocks.begin()};
178 }
180 return const_block_iterator{Blocks.end()};
181 }
182 size_t getNumBlocks() const { return Blocks.size(); }
185 }
186 //@}
187
188 /// Iteration over entry blocks.
189 //@{
192
193 size_t getNumEntries() const { return Entries.size(); }
195 return llvm::make_range(Entries.begin(), Entries.end());
196 }
197 //@}
198
199 Printable printEntries(const ContextT &Ctx) const {
200 return Printable([this, &Ctx](raw_ostream &Out) {
201 bool First = true;
202 for (auto *Entry : Entries) {
203 if (!First)
204 Out << ' ';
205 First = false;
206 Out << Ctx.print(Entry);
207 }
208 });
209 }
210
211 Printable print(const ContextT &Ctx) const {
212 return Printable([this, &Ctx](raw_ostream &Out) {
213 Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';
214
215 for (auto *Block : Blocks) {
216 if (isEntry(Block))
217 continue;
218
219 Out << ' ' << Ctx.print(Block);
220 }
221 });
222 }
223};
224
225/// \brief Cycle information for a function.
226template <typename ContextT> class GenericCycleInfo {
227public:
228 using BlockT = typename ContextT::BlockT;
230 using FunctionT = typename ContextT::FunctionT;
231 template <typename> friend class GenericCycle;
232 template <typename> friend class GenericCycleInfoCompute;
233
234private:
235 ContextT Context;
236
237 /// Map basic blocks to their inner-most containing cycle.
239
240 /// Map basic blocks to their top level containing cycle.
241 DenseMap<BlockT *, CycleT *> BlockMapTopLevel;
242
243 /// Top-level cycles discovered by any DFS.
244 ///
245 /// Note: The implementation treats the nullptr as the parent of
246 /// every top-level cycle. See \ref contains for an example.
247 std::vector<std::unique_ptr<CycleT>> TopLevelCycles;
248
249 /// Move \p Child to \p NewParent by manipulating Children vectors.
250 ///
251 /// Note: This is an incomplete operation that does not update the depth of
252 /// the subtree.
253 void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child);
254
255public:
256 GenericCycleInfo() = default;
259
260 void clear();
261 void compute(FunctionT &F);
262
263 FunctionT *getFunction() const { return Context.getFunction(); }
264 const ContextT &getSSAContext() const { return Context; }
265
266 CycleT *getCycle(const BlockT *Block) const;
267 unsigned getCycleDepth(const BlockT *Block) const;
269
270 /// Methods for debug and self-test.
271 //@{
272#ifndef NDEBUG
273 bool validateTree() const;
274#endif
275 void print(raw_ostream &Out) const;
276 void dump() const { print(dbgs()); }
277 //@}
278
279 /// Iteration over top-level cycles.
280 //@{
282 typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
284 : iterator_adaptor_base<const_toplevel_iterator,
285 const_toplevel_iterator_base> {
288
291 : Base(I) {}
292
294 CycleT *operator*() const { return Base::I->get(); }
295 };
296
298 return const_toplevel_iterator{TopLevelCycles.begin()};
299 }
301 return const_toplevel_iterator{TopLevelCycles.end()};
302 }
303
305 return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},
306 const_toplevel_iterator{TopLevelCycles.end()});
307 }
308 //@}
309};
310
311/// \brief GraphTraits for iterating over a sub-tree of the CycleT tree.
312template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {
313 using NodeRef = CycleRefT;
314
315 using nodes_iterator = ChildIteratorT;
317
318 static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
319
321 return Ref->child_begin();
322 }
323 static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); }
324
325 // Not implemented:
326 // static nodes_iterator nodes_begin(GraphType *G)
327 // static nodes_iterator nodes_end (GraphType *G)
328 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
329
330 // typedef EdgeRef - Type of Edge token in the graph, which should
331 // be cheap to copy.
332 // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
333 // graph, dereference to a EdgeRef.
334
335 // static ChildEdgeIteratorType child_edge_begin(NodeRef)
336 // static ChildEdgeIteratorType child_edge_end(NodeRef)
337 // Return iterators that point to the beginning and ending of the
338 // edge list for the given callgraph node.
339 //
340 // static NodeRef edge_dest(EdgeRef)
341 // Return the destination node of an edge.
342 // static unsigned size (GraphType *G)
343 // Return total number of nodes in the graph
344};
345
346template <typename BlockT>
350template <typename BlockT>
351struct GraphTraits<GenericCycle<BlockT> *>
354
355} // namespace llvm
356
357#endif // LLVM_ADT_GENERICCYCLEINFO_H
aarch64 promote const
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
This file defines the DenseMap class.
This file defines the little GenericSSAContext<X> template class that can be used to implement IR ana...
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition: MD5.cpp:55
LLVMContext & Context
This file defines the SmallVector class.
Helper class for computing cycle information.
Cycle information for a function.
typename ContextT::FunctionT FunctionT
typename std::vector< std::unique_ptr< CycleT > >::const_iterator const_toplevel_iterator_base
Iteration over top-level cycles.
iterator_range< const_toplevel_iterator > toplevel_cycles() const
const_toplevel_iterator toplevel_end() const
void print(raw_ostream &Out) const
Print the cycle info.
FunctionT * getFunction() const
GenericCycleInfo & operator=(GenericCycleInfo &&)=default
void clear()
Reset the object to its initial state.
bool validateTree() const
Methods for debug and self-test.
GenericCycle< ContextT > CycleT
void compute(FunctionT &F)
Compute the cycle info for a function.
const ContextT & getSSAContext() const
GenericCycleInfo(GenericCycleInfo &&)=default
unsigned getCycleDepth(const BlockT *Block) const
get the depth for the cycle which containing a given block.
typename ContextT::BlockT BlockT
CycleT * getTopLevelParentCycle(BlockT *Block)
const_toplevel_iterator toplevel_begin() const
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
A possibly irreducible generalization of a Loop.
BlockT * getHeader() const
bool isReducible() const
Whether the cycle is a natural loop.
typename ContextT::FunctionT FunctionT
typename std::vector< BlockT * >::const_iterator const_block_iterator
Iteration over blocks in the cycle (including entry blocks).
typename SmallVectorImpl< BlockT * >::const_iterator const_entry_iterator
Iteration over entry blocks.
const_child_iterator child_begin() const
iterator_range< const_entry_iterator > entries() const
GenericCycle()=default
Printable print(const ContextT &Ctx) const
iterator_range< const_block_iterator > blocks() const
const SmallVectorImpl< BlockT * > & getEntries() const
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
bool isEntry(const BlockT *Block) const
Return whether Block is an entry block of the cycle.
const_block_iterator block_begin() const
void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all of the successor blocks of this cycle.
BlockT * getCyclePredecessor() const
If the cycle has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
Printable printEntries(const ContextT &Ctx) const
size_t getNumEntries() const
const_child_iterator child_end() const
typename std::vector< std::unique_ptr< GenericCycle > >::const_iterator const_child_iterator_base
Iteration over child cycles.
size_t getNumChildren() const
typename ContextT::BlockT BlockT
const GenericCycle * getParentCycle() const
GenericCycle * getParentCycle()
unsigned getDepth() const
const_block_iterator block_end() const
size_t getNumBlocks() const
iterator_range< const_child_iterator > children() const
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:582
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:237
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Ref
The access may reference the value stored in memory.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1939
GraphTraits for iterating over a sub-tree of the CycleT tree.
static ChildIteratorType child_begin(NodeRef Ref)
nodes_iterator ChildIteratorType
ChildIteratorT nodes_iterator
static NodeRef getEntryNode(NodeRef Graph)
static ChildIteratorType child_end(NodeRef Ref)
const const_toplevel_iterator_base & wrapped()
const_toplevel_iterator(const_toplevel_iterator_base I)
const_child_iterator(const_child_iterator_base I)
const const_child_iterator_base & wrapped()