LLVM  15.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"
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"
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.
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  /// \brief Return whether \p Block is an entry block of the cycle.
104  bool isEntry(BlockT *Block) const { return is_contained(Entries, Block); }
105 
106  /// \brief Return whether \p Block is contained in the cycle.
107  bool contains(const BlockT *Block) const {
108  return is_contained(Blocks, Block);
109  }
110 
111  /// \brief Returns true iff this cycle contains \p C.
112  ///
113  /// Note: Non-strict containment check, i.e. returns true if C is the
114  /// same cycle.
115  bool contains(const GenericCycle *C) const;
116 
117  const GenericCycle *getParentCycle() const { return ParentCycle; }
118  GenericCycle *getParentCycle() { return ParentCycle; }
119  unsigned getDepth() const { return Depth; }
120 
121  /// Return all of the successor blocks of this cycle.
122  ///
123  /// These are the blocks _outside of the current cycle_ which are
124  /// branched to.
125  void getExitBlocks(SmallVectorImpl<BlockT *> &TmpStorage) const;
126 
127  /// Iteration over child cycles.
128  //@{
130  typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
132  : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
133  using Base =
135 
136  const_child_iterator() = default;
138 
140  GenericCycle *operator*() const { return Base::I->get(); }
141  };
142 
144  return const_child_iterator{Children.begin()};
145  }
147  return const_child_iterator{Children.end()};
148  }
149  size_t getNumChildren() const { return Children.size(); }
151  return llvm::make_range(const_child_iterator{Children.begin()},
152  const_child_iterator{Children.end()});
153  }
154  //@}
155 
156  /// Iteration over blocks in the cycle (including entry blocks).
157  //@{
158  using const_block_iterator = typename std::vector<BlockT *>::const_iterator;
159 
161  return const_block_iterator{Blocks.begin()};
162  }
164  return const_block_iterator{Blocks.end()};
165  }
166  size_t getNumBlocks() const { return Blocks.size(); }
169  }
170  //@}
171 
172  /// Iteration over entry blocks.
173  //@{
174  using const_entry_iterator =
176 
177  size_t getNumEntries() const { return Entries.size(); }
179  return llvm::make_range(Entries.begin(), Entries.end());
180  }
181  //@}
182 
183  Printable printEntries(const ContextT &Ctx) const {
184  return Printable([this, &Ctx](raw_ostream &Out) {
185  bool First = true;
186  for (auto *Entry : Entries) {
187  if (!First)
188  Out << ' ';
189  First = false;
190  Out << Ctx.print(Entry);
191  }
192  });
193  }
194 
195  Printable print(const ContextT &Ctx) const {
196  return Printable([this, &Ctx](raw_ostream &Out) {
197  Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';
198 
199  for (auto *Block : Blocks) {
200  if (isEntry(Block))
201  continue;
202 
203  Out << ' ' << Ctx.print(Block);
204  }
205  });
206  }
207 };
208 
209 /// \brief Cycle information for a function.
210 template <typename ContextT> class GenericCycleInfo {
211 public:
212  using BlockT = typename ContextT::BlockT;
214  using FunctionT = typename ContextT::FunctionT;
215  template <typename> friend class GenericCycle;
216  template <typename> friend class GenericCycleInfoCompute;
217 
218 private:
219  ContextT Context;
220 
221  /// Map basic blocks to their inner-most containing loop.
223 
224  /// Outermost cycles discovered by any DFS.
225  ///
226  /// Note: The implementation treats the nullptr as the parent of
227  /// every top-level cycle. See \ref contains for an example.
228  std::vector<std::unique_ptr<CycleT>> TopLevelCycles;
229 
230 public:
231  GenericCycleInfo() = default;
232  GenericCycleInfo(GenericCycleInfo &&) = default;
234 
235  void clear();
236  void compute(FunctionT &F);
237 
238  FunctionT *getFunction() const { return Context.getFunction(); }
239  const ContextT &getSSAContext() const { return Context; }
240 
241  CycleT *getCycle(const BlockT *Block) const;
242  CycleT *getTopLevelParentCycle(const BlockT *Block) const;
243 
244  /// Move \p Child to \p NewParent by manipulating Children vectors.
245  ///
246  /// Note: This is an incomplete operation that does not update the
247  /// list of blocks in the new parent or the depth of the subtree.
248  void moveToNewParent(CycleT *NewParent, CycleT *Child);
249 
250  /// Methods for debug and self-test.
251  //@{
252  bool validateTree() const;
253  void print(raw_ostream &Out) const;
254  void dump() const { print(dbgs()); }
255  //@}
256 
257  /// Iteration over top-level cycles.
258  //@{
260  typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
262  : iterator_adaptor_base<const_toplevel_iterator,
263  const_toplevel_iterator_base> {
266 
267  const_toplevel_iterator() = default;
269  : Base(I) {}
270 
272  CycleT *operator*() const { return Base::I->get(); }
273  };
274 
275  const_toplevel_iterator toplevel_begin() const {
276  return const_toplevel_iterator{TopLevelCycles.begin()};
277  }
278  const_toplevel_iterator toplevel_end() const {
279  return const_toplevel_iterator{TopLevelCycles.end()};
280  }
281 
283  return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},
284  const_toplevel_iterator{TopLevelCycles.end()});
285  }
286  //@}
287 };
288 
289 /// \brief GraphTraits for iterating over a sub-tree of the CycleT tree.
290 template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {
291  using NodeRef = CycleRefT;
292 
293  using nodes_iterator = ChildIteratorT;
295 
296  static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
297 
299  return Ref->child_begin();
300  }
301  static ChildIteratorType child_end(NodeRef Ref) { return Ref->child_end(); }
302 
303  // Not implemented:
304  // static nodes_iterator nodes_begin(GraphType *G)
305  // static nodes_iterator nodes_end (GraphType *G)
306  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
307 
308  // typedef EdgeRef - Type of Edge token in the graph, which should
309  // be cheap to copy.
310  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
311  // graph, dereference to a EdgeRef.
312 
313  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
314  // static ChildEdgeIteratorType child_edge_end(NodeRef)
315  // Return iterators that point to the beginning and ending of the
316  // edge list for the given callgraph node.
317  //
318  // static NodeRef edge_dest(EdgeRef)
319  // Return the destination node of an edge.
320  // static unsigned size (GraphType *G)
321  // Return total number of nodes in the graph
322 };
323 
324 template <typename BlockT>
325 struct GraphTraits<const GenericCycle<BlockT> *>
328 template <typename BlockT>
329 struct GraphTraits<GenericCycle<BlockT> *>
332 
333 } // namespace llvm
334 
335 #endif // LLVM_ADT_GENERICCYCLEINFO_H
llvm::GenericCycleInfo::getTopLevelParentCycle
CycleT * getTopLevelParentCycle(const BlockT *Block) const
Definition: GenericCycleImpl.h:109
const_iterator
llvm::GenericCycle::child_begin
const_child_iterator child_begin() const
Definition: GenericCycleInfo.h:143
llvm::GenericCycle::getHeader
BlockT * getHeader() const
Definition: GenericCycleInfo.h:101
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::GenericCycleInfo< SSAContext >::FunctionT
typename SSAContext ::FunctionT FunctionT
Definition: GenericCycleInfo.h:214
llvm::GenericCycleInfo::toplevel_begin
const_toplevel_iterator toplevel_begin() const
Definition: GenericCycleInfo.h:275
llvm::GenericCycle::blocks
iterator_range< const_block_iterator > blocks() const
Definition: GenericCycleInfo.h:167
llvm::GenericCycle::getParentCycle
const GenericCycle * getParentCycle() const
Definition: GenericCycleInfo.h:117
llvm::GenericCycleInfo::dump
void dump() const
Definition: GenericCycleInfo.h:254
llvm::GenericCycleInfo::const_toplevel_iterator::const_toplevel_iterator
const_toplevel_iterator()=default
Printable.h
llvm::CycleGraphTraits::getEntryNode
static NodeRef getEntryNode(NodeRef Graph)
Definition: GenericCycleInfo.h:296
llvm::SmallVector< BlockT *, 1 >
llvm::GenericCycle::printEntries
Printable printEntries(const ContextT &Ctx) const
Definition: GenericCycleInfo.h:183
llvm::iterator_adaptor_base< const_child_iterator, const_child_iterator_base >::I
const_child_iterator_base I
Definition: iterator.h:241
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
DenseMap.h
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
llvm::GenericCycle::entries
iterator_range< const_entry_iterator > entries() const
Definition: GenericCycleInfo.h:178
llvm::GenericCycleInfo::validateTree
bool validateTree() const
Methods for debug and self-test.
Definition: GenericCycleImpl.h:334
llvm::GenericCycle::const_child_iterator::const_child_iterator
const_child_iterator()=default
llvm::GenericCycleInfo::const_toplevel_iterator::const_toplevel_iterator
const_toplevel_iterator(const_toplevel_iterator_base I)
Definition: GenericCycleInfo.h:268
llvm::iterator_adaptor_base< const_child_iterator, const_child_iterator_base >::wrapped
const const_child_iterator_base & wrapped() const
Definition: iterator.h:250
F
#define F(x, y, z)
Definition: MD5.cpp:55
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
GenericSSAContext.h
llvm::GenericCycleInfo::moveToNewParent
void moveToNewParent(CycleT *NewParent, CycleT *Child)
Move Child to NewParent by manipulating Children vectors.
Definition: GenericCycleImpl.h:122
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
llvm::GenericCycleInfo::CycleT
GenericCycle< ContextT > CycleT
Definition: GenericCycleInfo.h:213
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GenericCycle::const_child_iterator_base
typename std::vector< std::unique_ptr< GenericCycle > >::const_iterator const_child_iterator_base
Iteration over child cycles.
Definition: GenericCycleInfo.h:130
llvm::GenericCycle::child_end
const_child_iterator child_end() const
Definition: GenericCycleInfo.h:146
llvm::CycleGraphTraits::child_begin
static ChildIteratorType child_begin(NodeRef Ref)
Definition: GenericCycleInfo.h:298
llvm::GenericCycleInfo::operator=
GenericCycleInfo & operator=(GenericCycleInfo &&)=default
llvm::GenericCycle::const_entry_iterator
typename SmallVectorImpl< BlockT * >::const_iterator const_entry_iterator
Iteration over entry blocks.
Definition: GenericCycleInfo.h:175
llvm::GenericCycle::block_begin
const_block_iterator block_begin() const
Definition: GenericCycleInfo.h:160
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
const_toplevel_iterator_base
llvm::GenericCycle::const_child_iterator::operator*
GenericCycle * operator*() const
Definition: GenericCycleInfo.h:140
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::GenericCycle::const_child_iterator::wrapped
const const_child_iterator_base & wrapped()
Definition: GenericCycleInfo.h:139
llvm::GenericCycle::block_end
const_block_iterator block_end() const
Definition: GenericCycleInfo.h:163
llvm::GenericCycle::getNumEntries
size_t getNumEntries() const
Definition: GenericCycleInfo.h:177
llvm::GenericCycleInfoCompute
Helper class for computing cycle information.
Definition: GenericCycleImpl.h:70
llvm::GenericCycleInfo::compute
void compute(FunctionT &F)
Compute the cycle info for a function.
Definition: GenericCycleImpl.h:305
llvm::GenericCycle::getDepth
unsigned getDepth() const
Definition: GenericCycleInfo.h:119
llvm::GenericCycleInfo::getSSAContext
const ContextT & getSSAContext() const
Definition: GenericCycleInfo.h:239
llvm::GenericCycleInfo::getCycle
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
Definition: GenericCycleImpl.h:321
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::GenericCycle::const_child_iterator::const_child_iterator
const_child_iterator(const_child_iterator_base I)
Definition: GenericCycleInfo.h:137
llvm::DenseMap
Definition: DenseMap.h:716
iterator.h
llvm::GenericCycle::getNumBlocks
size_t getNumBlocks() const
Definition: GenericCycleInfo.h:166
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1670
llvm::GenericCycleInfo::toplevel_end
const_toplevel_iterator toplevel_end() const
Definition: GenericCycleInfo.h:278
ArrayRef.h
llvm::GenericCycleInfo::const_toplevel_iterator::wrapped
const const_toplevel_iterator_base & wrapped()
Definition: GenericCycleInfo.h:271
llvm::GenericCycleInfo::const_toplevel_iterator::operator*
CycleT * operator*() const
Definition: GenericCycleInfo.h:272
llvm::GenericCycle::FunctionT
typename ContextT::FunctionT FunctionT
Definition: GenericCycleInfo.h:51
llvm::GenericCycleInfo
Cycle information for a function.
Definition: GenericCycleInfo.h:44
const_child_iterator_base
llvm::GenericCycleInfo::getFunction
FunctionT * getFunction() const
Definition: GenericCycleInfo.h:238
llvm::GenericCycle::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all of the successor blocks of this cycle.
Definition: GenericCycleImpl.h:47
llvm::GenericCycle::const_child_iterator
Definition: GenericCycleInfo.h:131
llvm::GenericCycle::const_block_iterator
typename std::vector< BlockT * >::const_iterator const_block_iterator
Iteration over blocks in the cycle (including entry blocks).
Definition: GenericCycleInfo.h:158
llvm::CycleGraphTraits::child_end
static ChildIteratorType child_end(NodeRef Ref)
Definition: GenericCycleInfo.h:301
llvm::GenericCycleInfo::GenericCycleInfo
GenericCycleInfo()=default
llvm::CycleGraphTraits::nodes_iterator
ChildIteratorT nodes_iterator
Definition: GenericCycleInfo.h:293
llvm::GenericCycleInfo::const_toplevel_iterator
Definition: GenericCycleInfo.h:261
llvm::GenericCycleInfo::toplevel_cycles
iterator_range< const_toplevel_iterator > toplevel_cycles() const
Definition: GenericCycleInfo.h:282
llvm::GenericCycleInfo::print
void print(raw_ostream &Out) const
Print the cycle info.
Definition: GenericCycleImpl.h:397
llvm::GenericCycle::isEntry
bool isEntry(BlockT *Block) const
Return whether Block is an entry block of the cycle.
Definition: GenericCycleInfo.h:104
llvm::GenericCycle::isReducible
bool isReducible() const
Whether the cycle is a natural loop.
Definition: GenericCycleInfo.h:99
llvm::GenericCycle::print
Printable print(const ContextT &Ctx) const
Definition: GenericCycleInfo.h:195
llvm::GenericCycleInfo::clear
void clear()
Reset the object to its initial state.
Definition: GenericCycleImpl.h:298
llvm::GenericCycle::getNumChildren
size_t getNumChildren() const
Definition: GenericCycleInfo.h:149
llvm::GenericCycle::children
iterator_range< const_child_iterator > children() const
Definition: GenericCycleInfo.h:150
llvm::GenericCycleInfo< SSAContext >::BlockT
typename SSAContext ::BlockT BlockT
Definition: GenericCycleInfo.h:212
SmallVector.h
llvm::Printable
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
llvm::GenericCycle::BlockT
typename ContextT::BlockT BlockT
Definition: GenericCycleInfo.h:50
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::SmallVectorImpl< BlockT * >
llvm::GenericCycle::getParentCycle
GenericCycle * getParentCycle()
Definition: GenericCycleInfo.h:118
llvm::GraphTraits
Definition: GraphTraits.h:37
raw_ostream.h
llvm::GenericCycleInfo::const_toplevel_iterator_base
typename std::vector< std::unique_ptr< CycleT > >::const_iterator const_toplevel_iterator_base
Iteration over top-level cycles.
Definition: GenericCycleInfo.h:260
llvm::CycleGraphTraits
GraphTraits for iterating over a sub-tree of the CycleT tree.
Definition: GenericCycleInfo.h:290
llvm::GenericCycle::contains
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
Definition: GenericCycleInfo.h:107
Debug.h
llvm::GenericCycle::GenericCycle
GenericCycle()=default