LLVM 19.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/DenseSet.h"
34#include "llvm/ADT/SetVector.h"
35#include "llvm/Support/Debug.h"
37
38namespace llvm {
39
40template <typename ContextT> class GenericCycleInfo;
41template <typename ContextT> class GenericCycleInfoCompute;
42
43/// A possibly irreducible generalization of a \ref Loop.
44template <typename ContextT> class GenericCycle {
45public:
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
51private:
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.
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.
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
93public:
94 GenericCycle() = default;
95
96 /// \brief Whether the cycle is a natural loop.
97 bool isReducible() const { return Entries.size() == 1; }
98
99 BlockT *getHeader() const { return Entries[0]; }
100
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 *getCyclePreheader() const;
134
135 /// If the cycle has exactly one entry with exactly one predecessor, return
136 /// it, otherwise return nullptr.
138
139 /// Iteration over child cycles.
140 //@{
142 typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
144 : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
145 using Base =
147
150
152 GenericCycle *operator*() const { return Base::I->get(); }
153 };
154
156 return const_child_iterator{Children.begin()};
157 }
159 return const_child_iterator{Children.end()};
160 }
161 size_t getNumChildren() const { return Children.size(); }
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 //@{
171
173 return const_block_iterator{Blocks.begin()};
174 }
176 return const_block_iterator{Blocks.end()};
177 }
178 size_t getNumBlocks() const { return Blocks.size(); }
181 }
182 //@}
183
184 /// Iteration over entry blocks.
185 //@{
188
189 size_t getNumEntries() const { return Entries.size(); }
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.
222template <typename ContextT> class GenericCycleInfo {
223public:
224 using BlockT = typename ContextT::BlockT;
226 using FunctionT = typename ContextT::FunctionT;
227 template <typename> friend class GenericCycle;
228 template <typename> friend class GenericCycleInfoCompute;
229
230private:
231 ContextT Context;
232
233 /// Map basic blocks to their inner-most containing cycle.
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
257public:
258 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;
271 unsigned getCycleDepth(const BlockT *Block) const;
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()); }
282 //@}
283
284 /// Iteration over top-level cycles.
285 //@{
287 typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
289 : iterator_adaptor_base<const_toplevel_iterator,
290 const_toplevel_iterator_base> {
293
296 : Base(I) {}
297
299 CycleT *operator*() const { return Base::I->get(); }
300 };
301
303 return const_toplevel_iterator{TopLevelCycles.begin()};
304 }
306 return const_toplevel_iterator{TopLevelCycles.end()};
307 }
308
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.
317template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {
318 using NodeRef = CycleRefT;
319
320 using nodes_iterator = ChildIteratorT;
322
323 static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
324
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
351template <typename BlockT>
355template <typename BlockT>
356struct GraphTraits<GenericCycle<BlockT> *>
359
360} // namespace llvm
361
362#endif // LLVM_ADT_GENERICCYCLEINFO_H
aarch64 promote const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:145
This file defines the DenseSet and SmallDenseSet classes.
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
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 implements a set that has insertion order iteration characteristics.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
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
const FunctionT * getFunction() const
void print(raw_ostream &Out) const
Print the cycle info.
CycleT * getSmallestCommonCycle(CycleT *A, CycleT *B) const
Find the innermost cycle containing both given cycles.
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.
void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)
const ContextT & getSSAContext() const
GenericCycleInfo(GenericCycleInfo &&)=default
Printable print(const CycleT *Cycle)
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 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.
typename BlockSetVectorT::const_iterator const_block_iterator
Iteration over blocks in the cycle (including entry blocks).
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:586
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
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()