23#ifndef LLVM_ADT_GENERICCYCLEIMPL_H
24#define LLVM_ADT_GENERICCYCLEIMPL_H
30#define DEBUG_TYPE "generic-cycle-impl"
34template <
typename ContextT>
41 while (Depth < C->
Depth)
46template <
typename ContextT>
51 size_t NumExitBlocks = 0;
55 for (
size_t Idx = NumExitBlocks, End = TmpStorage.
size();
Idx < End;
59 auto ExitEndIt = TmpStorage.
begin() + NumExitBlocks;
60 if (std::find(TmpStorage.
begin(), ExitEndIt, Succ) == ExitEndIt)
61 TmpStorage[NumExitBlocks++] = Succ;
65 TmpStorage.
resize(NumExitBlocks);
69template <
typename ContextT>
71 BlockT *Predecessor = getCyclePredecessor();
75 assert(isReducible() &&
"Cycle Predecessor must be in a reducible cycle!");
81 if (!Predecessor->isLegalToHoistInto())
87template <
typename ContextT>
95 BlockT *Header = getHeader();
98 if (Out && Out != Pred)
109 using BlockT =
typename ContextT::BlockT;
120 explicit DFSInfo(
unsigned Start) : Start(Start) {}
124 bool isAncestorOf(
const DFSInfo &
Other)
const {
125 return Start <=
Other.Start &&
Other.End <= End;
138 void run(BlockT *EntryBlock);
143 void dfs(BlockT *EntryBlock);
146template <
typename ContextT>
150 if (
Cycle != BlockMapTopLevel.end())
151 return Cycle->second;
153 auto MapIt = BlockMap.find(
Block);
154 if (MapIt == BlockMap.end())
157 auto *
C = MapIt->second;
158 while (
C->ParentCycle)
160 BlockMapTopLevel.try_emplace(
Block,
C);
164template <
typename ContextT>
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;
172 return Child ==
Ptr.get();
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;
180 NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(),
183 for (
auto &It : BlockMapTopLevel)
184 if (It.second == Child)
185 It.second = NewParent;
189template <
typename ContextT>
197 for (BlockT *HeaderCandidate :
llvm::reverse(BlockPreorder)) {
198 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
201 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
202 if (CandidateInfo.isAncestorOf(PredDFSInfo))
205 if (Worklist.
empty()) {
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());
220 auto ProcessPredecessors = [&](BlockT *
Block) {
223 bool IsEntry =
false;
225 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
226 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
235 NewCycle->appendEntry(
Block);
243 if (
Block == HeaderCandidate)
249 if (
auto *BlockParent =
Info.getTopLevelParentCycle(
Block)) {
252 if (BlockParent != NewCycle.get()) {
254 <<
"discovered child cycle "
255 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
257 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
259 for (
auto *ChildEntry : BlockParent->entries())
260 ProcessPredecessors(ChildEntry);
263 <<
"known child cycle "
264 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
269 NewCycle->Blocks.push_back(
Block);
270 ProcessPredecessors(
Block);
271 Info.BlockMapTopLevel.try_emplace(
Block, NewCycle.get());
275 Info.TopLevelCycles.push_back(std::move(NewCycle));
279 for (
auto *TLC :
Info.toplevel_cycles()) {
281 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
283 TLC->ParentCycle =
nullptr;
289template <
typename ContextT>
298template <
typename ContextT>
302 unsigned Counter = 0;
309 if (!BlockDFSInfo.count(
Block)) {
315 << TraverseStack.
size() <<
"\n");
320 bool Added = BlockDFSInfo.try_emplace(
Block, ++Counter).second;
323 BlockPreorder.push_back(
Block);
327 if (DFSTreeStack.
back() == TraverseStack.
size()) {
329 BlockDFSInfo.find(
Block)->second.End = Counter;
336 }
while (!TraverseStack.
empty());
340 errs() <<
"Preorder:\n";
341 for (
int i = 0, e = BlockPreorder.size(); i != e; ++i) {
342 errs() <<
" " << Info.Context.print(BlockPreorder[i]) <<
": " << i <<
"\n";
349 TopLevelCycles.clear();
351 BlockMapTopLevel.clear();
355template <
typename ContextT>
362 Compute.
run(ContextT::getEntryBlock(
F));
371template <
typename ContextT>
374 auto MapIt = BlockMap.find(
Block);
375 if (MapIt != BlockMap.end())
376 return MapIt->second;
384template <
typename ContextT>
397template <
typename ContextT>
403 errs() << File <<
':' << Line
404 <<
": GenericCycleInfo::validateTree: " <<
Cond <<
'\n';
409 reportError(__FILE__, __LINE__, #cond); \
414 for (
const auto *TLC : toplevel_cycles()) {
416 if (
Cycle->ParentCycle)
420 auto MapIt = BlockMap.find(
Block);
421 check(MapIt != BlockMap.end());
429 check(Entries.insert(Entry).second);
434 unsigned ChildDepth = 0;
438 ChildDepth = Child->Depth;
440 check(ChildDepth == Child->Depth);
446 for (
const auto &Entry : BlockMap) {
461template <
typename ContextT>
463 for (
const auto *TLC : toplevel_cycles()) {
465 for (
unsigned I = 0;
I <
Cycle->Depth; ++
I)
SmallVector< MachineOperand, 4 > Cond
static Error reportError(StringRef Message)
Analysis containing CSE Info
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
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Find all cycles in a control-flow graph, including irreducible loops.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Implements a dense probed hash-table based set.
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
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::pair< iterator, bool > insert(const ValueT &V)
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
auto reverse(ContainerTy &&C)
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.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
unsigned succ_size(const MachineBasicBlock *BB)