LLVM 17.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
32namespace llvm {
33
34template <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
46template <typename ContextT>
48 SmallVectorImpl<BlockT *> &TmpStorage) const {
49 TmpStorage.clear();
50
51 size_t NumExitBlocks = 0;
52 for (BlockT *Block : blocks()) {
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
69template <typename ContextT>
71 BlockT *Predecessor = getCyclePredecessor();
72 if (!Predecessor)
73 return nullptr;
74
75 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
76
77 if (succ_size(Predecessor) != 1)
78 return nullptr;
79
80 // Make sure we are allowed to hoist instructions into the predecessor.
81 if (!Predecessor->isLegalToHoistInto())
82 return nullptr;
83
84 return Predecessor;
85}
86
87template <typename ContextT>
89 if (!isReducible())
90 return nullptr;
91
92 BlockT *Out = nullptr;
93
94 // Loop over the predecessors of the header node...
95 BlockT *Header = getHeader();
96 for (const auto Pred : predecessors(Header)) {
97 if (!contains(Pred)) {
98 if (Out && Out != Pred)
99 return nullptr;
100 Out = Pred;
101 }
102 }
103
104 return Out;
105}
106
107/// \brief Helper class for computing cycle information.
108template <typename ContextT> class GenericCycleInfoCompute {
109 using BlockT = typename ContextT::BlockT;
111 using CycleT = typename CycleInfoT::CycleT;
112
113 CycleInfoT &Info;
114
115 struct DFSInfo {
116 unsigned Start = 0; // DFS start; positive if block is found
117 unsigned End = 0; // DFS end
118
119 DFSInfo() = default;
120 explicit DFSInfo(unsigned Start) : Start(Start) {}
121
122 /// Whether this node is an ancestor (or equal to) the node \p Other
123 /// in the DFS tree.
124 bool isAncestorOf(const DFSInfo &Other) const {
125 return Start <= Other.Start && Other.End <= End;
126 }
127 };
128
129 DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
130 SmallVector<BlockT *, 8> BlockPreorder;
131
133 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
134
135public:
137
138 void run(BlockT *EntryBlock);
139
140 static void updateDepth(CycleT *SubTree);
141
142private:
143 void dfs(BlockT *EntryBlock);
144};
145
146template <typename ContextT>
148 -> CycleT * {
149 auto Cycle = BlockMapTopLevel.find(Block);
150 if (Cycle != BlockMapTopLevel.end())
151 return Cycle->second;
152
153 auto MapIt = BlockMap.find(Block);
154 if (MapIt == BlockMap.end())
155 return nullptr;
156
157 auto *C = MapIt->second;
158 while (C->ParentCycle)
159 C = C->ParentCycle;
160 BlockMapTopLevel.try_emplace(Block, C);
161 return C;
162}
163
164template <typename ContextT>
166 CycleT *Child) {
167 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
168 "NewParent and Child must be both top level cycle!\n");
169 auto &CurrentContainer =
170 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
171 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
172 return Child == Ptr.get();
173 });
174 assert(Pos != CurrentContainer.end());
175 NewParent->Children.push_back(std::move(*Pos));
176 *Pos = std::move(CurrentContainer.back());
177 CurrentContainer.pop_back();
178 Child->ParentCycle = NewParent;
179
180 NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(),
181 Child->block_end());
182
183 for (auto &It : BlockMapTopLevel)
184 if (It.second == Child)
185 It.second = NewParent;
186}
187
188/// \brief Main function of the cycle info computations.
189template <typename ContextT>
191 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
192 << "\n");
193 dfs(EntryBlock);
194
196
197 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
198 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
199
200 for (BlockT *Pred : predecessors(HeaderCandidate)) {
201 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
202 if (CandidateInfo.isAncestorOf(PredDFSInfo))
203 Worklist.push_back(Pred);
204 }
205 if (Worklist.empty()) {
206 continue;
207 }
208
209 // Found a cycle with the candidate as its header.
210 LLVM_DEBUG(errs() << "Found cycle for header: "
211 << Info.Context.print(HeaderCandidate) << "\n");
212 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
213 NewCycle->appendEntry(HeaderCandidate);
214 NewCycle->appendBlock(HeaderCandidate);
215 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
216
217 // Helper function to process (non-back-edge) predecessors of a discovered
218 // block and either add them to the worklist or recognize that the given
219 // block is an additional cycle entry.
220 auto ProcessPredecessors = [&](BlockT *Block) {
221 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
222
223 bool IsEntry = false;
224 for (BlockT *Pred : predecessors(Block)) {
225 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
226 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
227 Worklist.push_back(Pred);
228 } else {
229 IsEntry = true;
230 }
231 }
232 if (IsEntry) {
233 assert(!NewCycle->isEntry(Block));
234 LLVM_DEBUG(errs() << "append as entry\n");
235 NewCycle->appendEntry(Block);
236 } else {
237 LLVM_DEBUG(errs() << "append as child\n");
238 }
239 };
240
241 do {
242 BlockT *Block = Worklist.pop_back_val();
243 if (Block == HeaderCandidate)
244 continue;
245
246 // If the block has already been discovered by some cycle
247 // (possibly by ourself), then the outermost cycle containing it
248 // should become our child.
249 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
250 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
251
252 if (BlockParent != NewCycle.get()) {
254 << "discovered child cycle "
255 << Info.Context.print(BlockParent->getHeader()) << "\n");
256 // Make BlockParent the child of NewCycle.
257 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
258
259 for (auto *ChildEntry : BlockParent->entries())
260 ProcessPredecessors(ChildEntry);
261 } else {
263 << "known child cycle "
264 << Info.Context.print(BlockParent->getHeader()) << "\n");
265 }
266 } else {
267 Info.BlockMap.try_emplace(Block, NewCycle.get());
268 assert(!is_contained(NewCycle->Blocks, Block));
269 NewCycle->Blocks.push_back(Block);
270 ProcessPredecessors(Block);
271 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
272 }
273 } while (!Worklist.empty());
274
275 Info.TopLevelCycles.push_back(std::move(NewCycle));
276 }
277
278 // Fix top-level cycle links and compute cycle depths.
279 for (auto *TLC : Info.toplevel_cycles()) {
280 LLVM_DEBUG(errs() << "top-level cycle: "
281 << Info.Context.print(TLC->getHeader()) << "\n");
282
283 TLC->ParentCycle = nullptr;
284 updateDepth(TLC);
285 }
286}
287
288/// \brief Recompute depth values of \p SubTree and all descendants.
289template <typename ContextT>
291 for (CycleT *Cycle : depth_first(SubTree))
292 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
293}
294
295/// \brief Compute a DFS of basic blocks starting at the function entry.
296///
297/// Fills BlockDFSInfo with start/end counters and BlockPreorder.
298template <typename ContextT>
299void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
300 SmallVector<unsigned, 8> DFSTreeStack;
301 SmallVector<BlockT *, 8> TraverseStack;
302 unsigned Counter = 0;
303 TraverseStack.emplace_back(EntryBlock);
304
305 do {
306 BlockT *Block = TraverseStack.back();
307 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
308 << "\n");
309 if (!BlockDFSInfo.count(Block)) {
310 // We're visiting the block for the first time. Open its DFSInfo, add
311 // successors to the traversal stack, and remember the traversal stack
312 // depth at which the block was opened, so that we can correctly record
313 // its end time.
314 LLVM_DEBUG(errs() << " first encountered at depth "
315 << TraverseStack.size() << "\n");
316
317 DFSTreeStack.emplace_back(TraverseStack.size());
318 llvm::append_range(TraverseStack, successors(Block));
319
320 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
321 (void)Added;
322 assert(Added);
323 BlockPreorder.push_back(Block);
324 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
325 } else {
326 assert(!DFSTreeStack.empty());
327 if (DFSTreeStack.back() == TraverseStack.size()) {
328 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
329 BlockDFSInfo.find(Block)->second.End = Counter;
330 DFSTreeStack.pop_back();
331 } else {
332 LLVM_DEBUG(errs() << " already done\n");
333 }
334 TraverseStack.pop_back();
335 }
336 } while (!TraverseStack.empty());
337 assert(DFSTreeStack.empty());
338
340 errs() << "Preorder:\n";
341 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
342 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
343 }
344 );
345}
346
347/// \brief Reset the object to its initial state.
348template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
349 TopLevelCycles.clear();
350 BlockMap.clear();
351 BlockMapTopLevel.clear();
352}
353
354/// \brief Compute the cycle info for a function.
355template <typename ContextT>
358 Context.setFunction(F);
359
360 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
361 << "\n");
362 Compute.run(ContextT::getEntryBlock(F));
363
364 assert(validateTree());
365}
366
367/// \brief Find the innermost cycle containing a given block.
368///
369/// \returns the innermost cycle containing \p Block or nullptr if
370/// it is not contained in any cycle.
371template <typename ContextT>
373 -> CycleT * {
374 auto MapIt = BlockMap.find(Block);
375 if (MapIt != BlockMap.end())
376 return MapIt->second;
377 return nullptr;
378}
379
380/// \brief get the depth for the cycle which containing a given block.
381///
382/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
383/// not contained in any cycle.
384template <typename ContextT>
386 CycleT *Cycle = getCycle(Block);
387 if (!Cycle)
388 return 0;
389 return Cycle->getDepth();
390}
391
392#ifndef NDEBUG
393/// \brief Validate the internal consistency of the cycle tree.
394///
395/// Note that this does \em not check that cycles are really cycles in the CFG,
396/// or that the right set of cycles in the CFG were found.
397template <typename ContextT>
399 DenseSet<BlockT *> Blocks;
400 DenseSet<BlockT *> Entries;
401
402 auto reportError = [](const char *File, int Line, const char *Cond) {
403 errs() << File << ':' << Line
404 << ": GenericCycleInfo::validateTree: " << Cond << '\n';
405 };
406#define check(cond) \
407 do { \
408 if (!(cond)) { \
409 reportError(__FILE__, __LINE__, #cond); \
410 return false; \
411 } \
412 } while (false)
413
414 for (const auto *TLC : toplevel_cycles()) {
415 for (const CycleT *Cycle : depth_first(TLC)) {
416 if (Cycle->ParentCycle)
417 check(is_contained(Cycle->ParentCycle->children(), Cycle));
418
419 for (BlockT *Block : Cycle->Blocks) {
420 auto MapIt = BlockMap.find(Block);
421 check(MapIt != BlockMap.end());
422 check(Cycle->contains(MapIt->second));
423 check(Blocks.insert(Block).second); // duplicates in block list?
424 }
425 Blocks.clear();
426
427 check(!Cycle->Entries.empty());
428 for (BlockT *Entry : Cycle->Entries) {
429 check(Entries.insert(Entry).second); // duplicate entry?
430 check(is_contained(Cycle->Blocks, Entry));
431 }
432 Entries.clear();
433
434 unsigned ChildDepth = 0;
435 for (const CycleT *Child : Cycle->children()) {
436 check(Child->Depth > Cycle->Depth);
437 if (!ChildDepth) {
438 ChildDepth = Child->Depth;
439 } else {
440 check(ChildDepth == Child->Depth);
441 }
442 }
443 }
444 }
445
446 for (const auto &Entry : BlockMap) {
447 BlockT *Block = Entry.first;
448 for (const CycleT *Cycle = Entry.second; Cycle;
449 Cycle = Cycle->ParentCycle) {
450 check(is_contained(Cycle->Blocks, Block));
451 }
452 }
453
454#undef check
455
456 return true;
457}
458#endif
459
460/// \brief Print the cycle info.
461template <typename ContextT>
463 for (const auto *TLC : toplevel_cycles()) {
464 for (const CycleT *Cycle : depth_first(TLC)) {
465 for (unsigned I = 0; I < Cycle->Depth; ++I)
466 Out << " ";
467
468 Out << Cycle->print(Context) << '\n';
469 }
470 }
471}
472
473} // namespace llvm
474
475#undef DEBUG_TYPE
476
477#endif // LLVM_ADT_GENERICCYCLEIMPL_H
aarch64 promote const
SmallVector< MachineOperand, 4 > Cond
static Error reportError(StringRef Message)
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define check(cond)
Find all cycles in a control-flow graph, including irreducible loops.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:467
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Helper class for computing cycle information.
void run(BlockT *EntryBlock)
Main function of the cycle info computations.
GenericCycleInfoCompute(CycleInfoT &Info)
static void updateDepth(CycleT *SubTree)
Recompute depth values of SubTree and all descendants.
Cycle information for a function.
typename ContextT::FunctionT FunctionT
void print(raw_ostream &Out) const
Print the cycle info.
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.
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)
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
A possibly irreducible generalization of a Loop.
Printable print(const ContextT &Ctx) const
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
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.
typename ContextT::BlockT BlockT
unsigned getDepth() const
iterator_range< const_child_iterator > children() const
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
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
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
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:1846
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
iterator_range< df_iterator< T > > depth_first(const T &G)
unsigned succ_size(const MachineBasicBlock *BB)