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;
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>
84template <
typename ContextT>
86 BlockT *Predecessor = getCyclePredecessor();
90 assert(isReducible() &&
"Cycle Predecessor must be in a reducible cycle!");
96 if (!Predecessor->isLegalToHoistInto())
102template <
typename ContextT>
110 BlockT *Header = getHeader();
113 if (Out && Out != Pred)
124 using BlockT =
typename ContextT::BlockT;
126 using CycleT =
typename CycleInfoT::CycleT;
135 explicit DFSInfo(
unsigned Start) : Start(Start) {}
139 bool isAncestorOf(
const DFSInfo &
Other)
const {
153 void run(BlockT *EntryBlock);
158 void dfs(BlockT *EntryBlock);
161template <
typename ContextT>
165 if (
Cycle != BlockMapTopLevel.end())
166 return Cycle->second;
168 auto MapIt = BlockMap.find(
Block);
169 if (MapIt == BlockMap.end())
172 auto *
C = MapIt->second;
173 while (
C->ParentCycle)
175 BlockMapTopLevel.try_emplace(
Block,
C);
179template <
typename ContextT>
182 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
183 "NewParent and Child must be both top level cycle!\n");
184 auto &CurrentContainer =
185 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
187 return Child ==
Ptr.get();
189 assert(Pos != CurrentContainer.end());
190 NewParent->Children.push_back(std::move(*Pos));
191 *Pos = std::move(CurrentContainer.back());
192 CurrentContainer.pop_back();
193 Child->ParentCycle = NewParent;
195 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
197 for (
auto &It : BlockMapTopLevel)
198 if (It.second == Child)
199 It.second = NewParent;
202template <
typename ContextT>
203void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *
Block, CycleT *
Cycle) {
211 while (ParentCycle) {
221template <
typename ContextT>
229 for (BlockT *HeaderCandidate :
llvm::reverse(BlockPreorder)) {
230 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
233 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
234 if (CandidateInfo.isAncestorOf(PredDFSInfo))
237 if (Worklist.
empty()) {
243 <<
Info.Context.print(HeaderCandidate) <<
"\n");
244 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
245 NewCycle->appendEntry(HeaderCandidate);
246 NewCycle->appendBlock(HeaderCandidate);
247 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
252 auto ProcessPredecessors = [&](BlockT *
Block) {
255 bool IsEntry =
false;
257 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
258 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
281 if (
auto *BlockParent =
Info.getTopLevelParentCycle(
Block)) {
284 if (BlockParent != NewCycle.get()) {
286 <<
"discovered child cycle "
287 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
289 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
291 for (
auto *ChildEntry : BlockParent->entries())
292 ProcessPredecessors(ChildEntry);
295 <<
"known child cycle "
296 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
299 Info.BlockMap.try_emplace(
Block, NewCycle.get());
301 NewCycle->Blocks.insert(
Block);
302 ProcessPredecessors(
Block);
303 Info.BlockMapTopLevel.try_emplace(
Block, NewCycle.get());
305 }
while (!Worklist.
empty());
307 Info.TopLevelCycles.push_back(std::move(NewCycle));
311 for (
auto *TLC :
Info.toplevel_cycles()) {
313 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
315 TLC->ParentCycle =
nullptr;
321template <
typename ContextT>
330template <
typename ContextT>
334 unsigned Counter = 0;
341 if (!BlockDFSInfo.count(
Block)) {
347 << TraverseStack.
size() <<
"\n");
352 bool Added = BlockDFSInfo.try_emplace(
Block, ++Counter).second;
355 BlockPreorder.push_back(
Block);
359 if (DFSTreeStack.
back() == TraverseStack.
size()) {
361 BlockDFSInfo.find(
Block)->second.End = Counter;
368 }
while (!TraverseStack.
empty());
372 errs() <<
"Preorder:\n";
373 for (
int i = 0, e = BlockPreorder.size(); i != e; ++i) {
374 errs() <<
" " << Info.Context.print(BlockPreorder[i]) <<
": " << i <<
"\n";
381 TopLevelCycles.clear();
383 BlockMapTopLevel.clear();
387template <
typename ContextT>
394 Compute.
run(&
F.front());
399template <
typename ContextT>
404 CycleT *
Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
408 addBlockToCycle(NewBlock,
Cycle);
416template <
typename ContextT>
419 return BlockMap.lookup(
Block);
426template <
typename ContextT>
435 while (
A->getDepth() >
B->getDepth())
436 A =
A->getParentCycle();
437 while (
B->getDepth() >
A->getDepth())
438 B =
B->getParentCycle();
444 A =
A->getParentCycle();
445 B =
B->getParentCycle();
455template <
typename ContextT>
468template <
typename ContextT>
474 errs() << File <<
':' << Line
475 <<
": GenericCycleInfo::validateTree: " <<
Cond <<
'\n';
480 reportError(__FILE__, __LINE__, #cond); \
485 for (
const auto *TLC : toplevel_cycles()) {
487 if (
Cycle->ParentCycle)
491 auto MapIt = BlockMap.find(
Block);
492 check(MapIt != BlockMap.end());
500 check(Entries.insert(Entry).second);
505 unsigned ChildDepth = 0;
509 ChildDepth = Child->Depth;
511 check(ChildDepth == Child->Depth);
517 for (
const auto &Entry : BlockMap) {
532template <
typename ContextT>
534 for (
const auto *TLC : toplevel_cycles()) {
536 for (
unsigned I = 0;
I <
Cycle->Depth; ++
I)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static Error reportError(StringRef Message)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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.
DenseMap< Block *, BlockRelaxAux > Blocks
Find all cycles in a control-flow graph, including irreducible loops.
const SmallVectorImpl< MachineOperand > & Cond
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.
CycleT * getSmallestCommonCycle(CycleT *A, CycleT *B) const
Find the innermost cycle containing both given cycles.
void clear()
Reset the object to its initial state.
bool validateTree() const
Methods for debug and self-test.
void compute(FunctionT &F)
Compute the cycle info for a function.
void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)
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.
void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all blocks of this cycle that have successor outside of this cycle.
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
const GenericCycle * getParentCycle() const
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.
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 range R to container C.
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)