LLVM  15.0.0git
GenericCycleImpl.h
Go to the documentation of this file.
1 //===- GenericCycleImpl.h -------------------------------------*- 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 /// This template implementation resides in a separate file so that it
11 /// does not get injected into every .cpp file that includes the
12 /// generic header.
13 ///
14 /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
15 ///
16 /// This file should only be included by files that implement a
17 /// specialization of the relevant templates. Currently these are:
18 /// - CycleAnalysis.cpp
19 /// - MachineCycleAnalysis.cpp
20 ///
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_ADT_GENERICCYCLEIMPL_H
24 #define LLVM_ADT_GENERICCYCLEIMPL_H
25 
26 #include "llvm/ADT/DenseSet.h"
29 
30 #define DEBUG_TYPE "generic-cycle-impl"
31 
32 namespace llvm {
33 
34 template <typename ContextT>
36  if (!C)
37  return false;
38 
39  if (Depth > C->Depth)
40  return false;
41  while (Depth < C->Depth)
42  C = C->ParentCycle;
43  return this == C;
44 }
45 
46 template <typename ContextT>
48  SmallVectorImpl<BlockT *> &TmpStorage) const {
49  TmpStorage.clear();
50 
51  size_t NumExitBlocks = 0;
52  for (BlockT *Block : blocks()) {
53  llvm::append_range(TmpStorage, successors(Block));
54 
55  for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
56  ++Idx) {
57  BlockT *Succ = TmpStorage[Idx];
58  if (!contains(Succ)) {
59  auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
60  if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
61  TmpStorage[NumExitBlocks++] = Succ;
62  }
63  }
64 
65  TmpStorage.resize(NumExitBlocks);
66  }
67 }
68 
69 /// \brief Helper class for computing cycle information.
70 template <typename ContextT> class GenericCycleInfoCompute {
71  using BlockT = typename ContextT::BlockT;
73  using CycleT = typename CycleInfoT::CycleT;
74 
75  CycleInfoT &Info;
76 
77  struct DFSInfo {
78  unsigned Start = 0; // DFS start; positive if block is found
79  unsigned End = 0; // DFS end
80 
81  DFSInfo() = default;
82  explicit DFSInfo(unsigned Start) : Start(Start) {}
83 
84  /// Whether this node is an ancestor (or equal to) the node \p Other
85  /// in the DFS tree.
86  bool isAncestorOf(const DFSInfo &Other) const {
87  return Start <= Other.Start && Other.End <= End;
88  }
89  };
90 
91  DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
92  SmallVector<BlockT *, 8> BlockPreorder;
93 
95  GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
96 
97 public:
99 
100  void run(BlockT *EntryBlock);
101 
102  static void updateDepth(CycleT *SubTree);
103 
104 private:
105  void dfs(BlockT *EntryBlock);
106 };
107 
108 template <typename ContextT>
110  const BlockT *Block) const -> CycleT * {
111  auto MapIt = BlockMap.find(Block);
112  if (MapIt == BlockMap.end())
113  return nullptr;
114 
115  auto *C = MapIt->second;
116  while (C->ParentCycle)
117  C = C->ParentCycle;
118  return C;
119 }
120 
121 template <typename ContextT>
123  CycleT *Child) {
124  auto &CurrentContainer =
125  Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
126  auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
127  return Child == Ptr.get();
128  });
129  assert(Pos != CurrentContainer.end());
130  NewParent->Children.push_back(std::move(*Pos));
131  *Pos = std::move(CurrentContainer.back());
132  CurrentContainer.pop_back();
133  Child->ParentCycle = NewParent;
134 }
135 
136 /// \brief Main function of the cycle info computations.
137 template <typename ContextT>
138 void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) {
139  LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
140  << "\n");
141  dfs(EntryBlock);
142 
143  SmallVector<BlockT *, 8> Worklist;
144 
145  for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
146  const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
147 
148  for (BlockT *Pred : predecessors(HeaderCandidate)) {
149  const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
150  if (CandidateInfo.isAncestorOf(PredDFSInfo))
151  Worklist.push_back(Pred);
152  }
153  if (Worklist.empty()) {
154  continue;
155  }
156 
157  // Found a cycle with the candidate as its header.
158  LLVM_DEBUG(errs() << "Found cycle for header: "
159  << Info.Context.print(HeaderCandidate) << "\n");
160  std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
161  NewCycle->appendEntry(HeaderCandidate);
162  NewCycle->appendBlock(HeaderCandidate);
163  Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
164 
165  // Helper function to process (non-back-edge) predecessors of a discovered
166  // block and either add them to the worklist or recognize that the given
167  // block is an additional cycle entry.
168  auto ProcessPredecessors = [&](BlockT *Block) {
169  LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
170 
171  bool IsEntry = false;
172  for (BlockT *Pred : predecessors(Block)) {
173  const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
174  if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
175  Worklist.push_back(Pred);
176  } else {
177  IsEntry = true;
178  }
179  }
180  if (IsEntry) {
181  assert(!NewCycle->isEntry(Block));
182  LLVM_DEBUG(errs() << "append as entry\n");
183  NewCycle->appendEntry(Block);
184  } else {
185  LLVM_DEBUG(errs() << "append as child\n");
186  }
187  };
188 
189  do {
190  BlockT *Block = Worklist.pop_back_val();
191  if (Block == HeaderCandidate)
192  continue;
193 
194  // If the block has already been discovered by some cycle
195  // (possibly by ourself), then the outermost cycle containing it
196  // should become our child.
197  if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
198  LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
199 
200  if (BlockParent != NewCycle.get()) {
201  LLVM_DEBUG(errs()
202  << "discovered child cycle "
203  << Info.Context.print(BlockParent->getHeader()) << "\n");
204  // Make BlockParent the child of NewCycle.
205  Info.moveToNewParent(NewCycle.get(), BlockParent);
206  NewCycle->Blocks.insert(NewCycle->Blocks.end(),
207  BlockParent->block_begin(),
208  BlockParent->block_end());
209 
210  for (auto *ChildEntry : BlockParent->entries())
211  ProcessPredecessors(ChildEntry);
212  } else {
213  LLVM_DEBUG(errs()
214  << "known child cycle "
215  << Info.Context.print(BlockParent->getHeader()) << "\n");
216  }
217  } else {
218  Info.BlockMap.try_emplace(Block, NewCycle.get());
219  assert(!is_contained(NewCycle->Blocks, Block));
220  NewCycle->Blocks.push_back(Block);
221  ProcessPredecessors(Block);
222  }
223  } while (!Worklist.empty());
224 
225  Info.TopLevelCycles.push_back(std::move(NewCycle));
226  }
227 
228  // Fix top-level cycle links and compute cycle depths.
229  for (auto *TLC : Info.toplevel_cycles()) {
230  LLVM_DEBUG(errs() << "top-level cycle: "
231  << Info.Context.print(TLC->getHeader()) << "\n");
232 
233  TLC->ParentCycle = nullptr;
234  updateDepth(TLC);
235  }
236 }
237 
238 /// \brief Recompute depth values of \p SubTree and all descendants.
239 template <typename ContextT>
241  for (CycleT *Cycle : depth_first(SubTree))
242  Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
243 }
244 
245 /// \brief Compute a DFS of basic blocks starting at the function entry.
246 ///
247 /// Fills BlockDFSInfo with start/end counters and BlockPreorder.
248 template <typename ContextT>
249 void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
250  SmallVector<unsigned, 8> DFSTreeStack;
251  SmallVector<BlockT *, 8> TraverseStack;
252  unsigned Counter = 0;
253  TraverseStack.emplace_back(EntryBlock);
254 
255  do {
256  BlockT *Block = TraverseStack.back();
257  LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
258  << "\n");
259  if (!BlockDFSInfo.count(Block)) {
260  // We're visiting the block for the first time. Open its DFSInfo, add
261  // successors to the traversal stack, and remember the traversal stack
262  // depth at which the block was opened, so that we can correctly record
263  // its end time.
264  LLVM_DEBUG(errs() << " first encountered at depth "
265  << TraverseStack.size() << "\n");
266 
267  DFSTreeStack.emplace_back(TraverseStack.size());
268  llvm::append_range(TraverseStack, successors(Block));
269 
270  bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
271  (void)Added;
272  assert(Added);
273  BlockPreorder.push_back(Block);
274  LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
275  } else {
276  assert(!DFSTreeStack.empty());
277  if (DFSTreeStack.back() == TraverseStack.size()) {
278  LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
279  BlockDFSInfo.find(Block)->second.End = Counter;
280  DFSTreeStack.pop_back();
281  } else {
282  LLVM_DEBUG(errs() << " already done\n");
283  }
284  TraverseStack.pop_back();
285  }
286  } while (!TraverseStack.empty());
287  assert(DFSTreeStack.empty());
288 
289  LLVM_DEBUG(
290  errs() << "Preorder:\n";
291  for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
292  errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
293  }
294  );
295 }
296 
297 /// \brief Reset the object to its initial state.
298 template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
299  TopLevelCycles.clear();
300  BlockMap.clear();
301 }
302 
303 /// \brief Compute the cycle info for a function.
304 template <typename ContextT>
306  GenericCycleInfoCompute<ContextT> Compute(*this);
307  Context.setFunction(F);
308 
309  LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
310  << "\n");
311  Compute.run(ContextT::getEntryBlock(F));
312 
313  assert(validateTree());
314 }
315 
316 /// \brief Find the innermost cycle containing a given block.
317 ///
318 /// \returns the innermost cycle containing \p Block or nullptr if
319 /// it is not contained in any cycle.
320 template <typename ContextT>
322  -> CycleT * {
323  auto MapIt = BlockMap.find(Block);
324  if (MapIt != BlockMap.end())
325  return MapIt->second;
326  return nullptr;
327 }
328 
329 #ifndef NDEBUG
330 /// \brief Validate the internal consistency of the cycle tree.
331 ///
332 /// Note that this does \em not check that cycles are really cycles in the CFG,
333 /// or that the right set of cycles in the CFG were found.
334 template <typename ContextT>
336  DenseSet<BlockT *> Blocks;
337  DenseSet<BlockT *> Entries;
338 
339  auto reportError = [](const char *File, int Line, const char *Cond) {
340  errs() << File << ':' << Line
341  << ": GenericCycleInfo::validateTree: " << Cond << '\n';
342  };
343 #define check(cond) \
344  do { \
345  if (!(cond)) { \
346  reportError(__FILE__, __LINE__, #cond); \
347  return false; \
348  } \
349  } while (false)
350 
351  for (const auto *TLC : toplevel_cycles()) {
352  for (const CycleT *Cycle : depth_first(TLC)) {
353  if (Cycle->ParentCycle)
354  check(is_contained(Cycle->ParentCycle->children(), Cycle));
355 
356  for (BlockT *Block : Cycle->Blocks) {
357  auto MapIt = BlockMap.find(Block);
358  check(MapIt != BlockMap.end());
359  check(Cycle->contains(MapIt->second));
360  check(Blocks.insert(Block).second); // duplicates in block list?
361  }
362  Blocks.clear();
363 
364  check(!Cycle->Entries.empty());
365  for (BlockT *Entry : Cycle->Entries) {
366  check(Entries.insert(Entry).second); // duplicate entry?
367  check(is_contained(Cycle->Blocks, Entry));
368  }
369  Entries.clear();
370 
371  unsigned ChildDepth = 0;
372  for (const CycleT *Child : Cycle->children()) {
373  check(Child->Depth > Cycle->Depth);
374  if (!ChildDepth) {
375  ChildDepth = Child->Depth;
376  } else {
377  check(ChildDepth == Child->Depth);
378  }
379  }
380  }
381  }
382 
383  for (const auto &Entry : BlockMap) {
384  BlockT *Block = Entry.first;
385  for (const CycleT *Cycle = Entry.second; Cycle;
386  Cycle = Cycle->ParentCycle) {
387  check(is_contained(Cycle->Blocks, Block));
388  }
389  }
390 
391 #undef check
392 
393  return true;
394 }
395 #endif
396 
397 /// \brief Print the cycle info.
398 template <typename ContextT>
400  for (const auto *TLC : toplevel_cycles()) {
401  for (const CycleT *Cycle : depth_first(TLC)) {
402  for (unsigned I = 0; I < Cycle->Depth; ++I)
403  Out << " ";
404 
405  Out << Cycle->print(Context) << '\n';
406  }
407  }
408 }
409 
410 } // namespace llvm
411 
412 #undef DEBUG_TYPE
413 
414 #endif // LLVM_ADT_GENERICCYCLEIMPL_H
i
i
Definition: README.txt:29
llvm::GenericCycleInfo::getTopLevelParentCycle
CycleT * getTopLevelParentCycle(const BlockT *Block) const
Definition: GenericCycleImpl.h:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::GenericCycleInfo< SSAContext >::FunctionT
typename SSAContext ::FunctionT FunctionT
Definition: GenericCycleInfo.h:214
contains
return AArch64::GPR64RegClass contains(Reg)
llvm::SmallVector< BlockT *, 8 >
llvm::GenericCycleInfoCompute::GenericCycleInfoCompute
GenericCycleInfoCompute(CycleInfoT &Info)
Definition: GenericCycleImpl.h:98
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::GenericCycleInfo::validateTree
bool validateTree() const
Methods for debug and self-test.
Definition: GenericCycleImpl.h:335
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::GenericCycleInfo::moveToNewParent
void moveToNewParent(CycleT *NewParent, CycleT *Child)
Move Child to NewParent by manipulating Children vectors.
Definition: GenericCycleImpl.h:122
llvm::GenericCycleInfo::CycleT
GenericCycle< ContextT > CycleT
Definition: GenericCycleInfo.h:213
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
reportError
static Error reportError(StringRef Message)
Definition: BitcodeAnalyzer.cpp:19
DenseSet.h
check
#define check(cond)
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
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::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
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::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::GenericCycleInfoCompute::updateDepth
static void updateDepth(CycleT *SubTree)
Recompute depth values of SubTree and all descendants.
Definition: GenericCycleImpl.h:240
llvm::GenericCycleInfo::getCycle
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
Definition: GenericCycleImpl.h:321
GenericCycleInfo.h
Find all cycles in a control-flow graph, including irreducible loops.
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1627
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap< BlockT *, DFSInfo >
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:1672
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::GenericCycleInfo
Cycle information for a function.
Definition: GenericCycleInfo.h:44
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:178
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1813
llvm::GenericCycle::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all of the successor blocks of this cycle.
Definition: GenericCycleImpl.h:47
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1634
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::GenericCycleInfo::print
void print(raw_ostream &Out) const
Print the cycle info.
Definition: GenericCycleImpl.h:399
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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::children
iterator_range< const_child_iterator > children() const
Definition: GenericCycleInfo.h:150
llvm::GenericCycleInfo< SSAContext >::BlockT
typename SSAContext ::BlockT BlockT
Definition: GenericCycleInfo.h:212
llvm::GenericCycle::BlockT
typename ContextT::BlockT BlockT
Definition: GenericCycleInfo.h:50
llvm::SmallVectorImpl< BlockT * >
llvm::GenericCycleInfoCompute::run
void run(BlockT *EntryBlock)
Main function of the cycle info computations.
Definition: GenericCycleImpl.h:138
llvm::GenericCycle::contains
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
Definition: GenericCycleInfo.h:107
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1225
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927