LLVM  16.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 
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  //@{
144  typename std::vector<std::unique_ptr<GenericCycle>>::const_iterator;
146  : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
147  using Base =
149 
150  const_child_iterator() = default;
152 
154  GenericCycle *operator*() const { return Base::I->get(); }
155  };
156 
158  return const_child_iterator{Children.begin()};
159  }
161  return const_child_iterator{Children.end()};
162  }
163  size_t getNumChildren() const { return Children.size(); }
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 
175  return const_block_iterator{Blocks.begin()};
176  }
178  return const_block_iterator{Blocks.end()};
179  }
180  size_t getNumBlocks() const { return Blocks.size(); }
183  }
184  //@}
185 
186  /// Iteration over entry blocks.
187  //@{
188  using const_entry_iterator =
190 
191  size_t getNumEntries() const { return Entries.size(); }
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;
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.
237 
238  /// Map basic blocks to their top level containing cycle.
239  DenseMap<BlockT *, CycleT *> BlockMapTopLevel;
240 
241  /// Top-level 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;
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;
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  //@{
280  typename std::vector<std::unique_ptr<CycleT>>::const_iterator;
282  : iterator_adaptor_base<const_toplevel_iterator,
283  const_toplevel_iterator_base> {
286 
287  const_toplevel_iterator() = default;
289  : Base(I) {}
290 
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 
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;
315 
316  static NodeRef getEntryNode(NodeRef Graph) { return Graph; }
317 
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> *>
348 template <typename BlockT>
349 struct GraphTraits<GenericCycle<BlockT> *>
352 
353 } // namespace llvm
354 
355 #endif // LLVM_ADT_GENERICCYCLEINFO_H
llvm::GenericCycle::child_begin
const_child_iterator child_begin() const
Definition: GenericCycleInfo.h:157
llvm::GenericCycle::getHeader
BlockT * getHeader() const
Definition: GenericCycleInfo.h:101
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:228
llvm::GenericCycleInfo::toplevel_begin
const_toplevel_iterator toplevel_begin() const
Definition: GenericCycleInfo.h:295
llvm::GenericCycle::blocks
iterator_range< const_block_iterator > blocks() const
Definition: GenericCycleInfo.h:181
llvm::GenericCycle::getParentCycle
const GenericCycle * getParentCycle() const
Definition: GenericCycleInfo.h:121
llvm::GenericCycleInfo::dump
void dump() const
Definition: GenericCycleInfo.h:274
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:316
llvm::SmallVector< BlockT *, 1 >
llvm::GenericCycle::printEntries
Printable printEntries(const ContextT &Ctx) const
Definition: GenericCycleInfo.h:197
llvm::iterator_adaptor_base< const_child_iterator, const_child_iterator_base >::I
const_child_iterator_base I
Definition: iterator.h:241
llvm::GenericCycleInfo::getCycleDepth
unsigned getCycleDepth(const BlockT *Block) const
get the depth for the cycle which containing a given block.
Definition: GenericCycleImpl.h:385
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:192
llvm::GenericCycleInfo::validateTree
bool validateTree() const
Methods for debug and self-test.
Definition: GenericCycleImpl.h:398
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:288
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
llvm::GenericCycle::getCyclePreheader
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
Definition: GenericCycleImpl.h:70
GenericSSAContext.h
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
llvm::GenericCycleInfo::CycleT
GenericCycle< ContextT > CycleT
Definition: GenericCycleInfo.h:227
llvm::GenericCycleInfo::getTopLevelParentCycle
CycleT * getTopLevelParentCycle(BlockT *Block)
Definition: GenericCycleImpl.h:147
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:144
llvm::GenericCycle::child_end
const_child_iterator child_end() const
Definition: GenericCycleInfo.h:160
llvm::CycleGraphTraits::child_begin
static ChildIteratorType child_begin(NodeRef Ref)
Definition: GenericCycleInfo.h:318
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:189
llvm::GenericCycle::block_begin
const_block_iterator block_begin() const
Definition: GenericCycleInfo.h:174
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:154
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:53
llvm::GenericCycle::const_child_iterator::wrapped
const const_child_iterator_base & wrapped()
Definition: GenericCycleInfo.h:153
llvm::GenericCycle::block_end
const_block_iterator block_end() const
Definition: GenericCycleInfo.h:177
llvm::GenericCycle::getNumEntries
size_t getNumEntries() const
Definition: GenericCycleInfo.h:191
llvm::GenericCycleInfoCompute
Helper class for computing cycle information.
Definition: GenericCycleImpl.h:108
llvm::GenericCycleInfo::compute
void compute(FunctionT &F)
Compute the cycle info for a function.
Definition: GenericCycleImpl.h:356
llvm::GenericCycle::getDepth
unsigned getDepth() const
Definition: GenericCycleInfo.h:123
llvm::GenericCycleInfo::getSSAContext
const ContextT & getSSAContext() const
Definition: GenericCycleInfo.h:262
llvm::GenericCycleInfo::getCycle
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
Definition: GenericCycleImpl.h:372
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:151
llvm::DenseMap
Definition: DenseMap.h:714
iterator.h
llvm::GenericCycle::getNumBlocks
size_t getNumBlocks() const
Definition: GenericCycleInfo.h:180
llvm::GenericCycle::getEntries
const SmallVectorImpl< BlockT * > & getEntries() const
Definition: GenericCycleInfo.h:103
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:1868
llvm::GenericCycleInfo::toplevel_end
const_toplevel_iterator toplevel_end() const
Definition: GenericCycleInfo.h:298
ArrayRef.h
llvm::GenericCycleInfo::const_toplevel_iterator::wrapped
const const_toplevel_iterator_base & wrapped()
Definition: GenericCycleInfo.h:291
llvm::GenericCycleInfo::const_toplevel_iterator::operator*
CycleT * operator*() const
Definition: GenericCycleInfo.h:292
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
const_iterator
llvm::GenericCycleInfo::getFunction
FunctionT * getFunction() const
Definition: GenericCycleInfo.h:261
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:145
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:172
llvm::CycleGraphTraits::child_end
static ChildIteratorType child_end(NodeRef Ref)
Definition: GenericCycleInfo.h:321
llvm::GenericCycleInfo::GenericCycleInfo
GenericCycleInfo()=default
llvm::CycleGraphTraits::nodes_iterator
ChildIteratorT nodes_iterator
Definition: GenericCycleInfo.h:313
llvm::GenericCycleInfo::const_toplevel_iterator
Definition: GenericCycleInfo.h:281
llvm::GenericCycleInfo::toplevel_cycles
iterator_range< const_toplevel_iterator > toplevel_cycles() const
Definition: GenericCycleInfo.h:302
llvm::GenericCycleInfo::print
void print(raw_ostream &Out) const
Print the cycle info.
Definition: GenericCycleImpl.h:462
llvm::GenericCycle::isEntry
bool isEntry(BlockT *Block) const
Return whether Block is an entry block of the cycle.
Definition: GenericCycleInfo.h:108
llvm::GenericCycle::isReducible
bool isReducible() const
Whether the cycle is a natural loop.
Definition: GenericCycleInfo.h:99
llvm::GenericCycle::getCyclePredecessor
BlockT * getCyclePredecessor() const
If the cycle has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.
Definition: GenericCycleImpl.h:88
llvm::GenericCycle::print
Printable print(const ContextT &Ctx) const
Definition: GenericCycleInfo.h:209
llvm::GenericCycleInfo::clear
void clear()
Reset the object to its initial state.
Definition: GenericCycleImpl.h:348
llvm::GenericCycle::getNumChildren
size_t getNumChildren() const
Definition: GenericCycleInfo.h:163
llvm::GenericCycle::children
iterator_range< const_child_iterator > children() const
Definition: GenericCycleInfo.h:164
llvm::GenericCycleInfo< SSAContext >::BlockT
typename SSAContext ::BlockT BlockT
Definition: GenericCycleInfo.h:226
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:122
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:280
llvm::CycleGraphTraits
GraphTraits for iterating over a sub-tree of the CycleT tree.
Definition: GenericCycleInfo.h:310
llvm::GenericCycle::contains
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
Definition: GenericCycleInfo.h:111
Debug.h
llvm::GenericCycle::GenericCycle
GenericCycle()=default