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) {}
137 explicit operator bool()
const {
return Start; }
141 bool isAncestorOf(
const DFSInfo &
Other)
const {
155 void run(BlockT *EntryBlock);
160 void dfs(BlockT *EntryBlock);
163template <
typename ContextT>
167 if (
Cycle != BlockMapTopLevel.end())
168 return Cycle->second;
170 auto MapIt = BlockMap.find(
Block);
171 if (MapIt == BlockMap.end())
174 auto *
C = MapIt->second;
175 while (
C->ParentCycle)
177 BlockMapTopLevel.try_emplace(
Block,
C);
181template <
typename ContextT>
184 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
185 "NewParent and Child must be both top level cycle!\n");
186 auto &CurrentContainer =
187 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
189 return Child ==
Ptr.get();
191 assert(Pos != CurrentContainer.end());
192 NewParent->Children.push_back(std::move(*Pos));
193 *Pos = std::move(CurrentContainer.back());
194 CurrentContainer.pop_back();
195 Child->ParentCycle = NewParent;
197 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
199 for (
auto &It : BlockMapTopLevel)
200 if (It.second == Child)
201 It.second = NewParent;
204template <
typename ContextT>
205void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *
Block, CycleT *
Cycle) {
213 while (ParentCycle) {
223template <
typename ContextT>
231 for (BlockT *HeaderCandidate :
llvm::reverse(BlockPreorder)) {
232 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
235 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
238 if (CandidateInfo.isAncestorOf(PredDFSInfo))
241 if (Worklist.
empty()) {
247 <<
Info.Context.print(HeaderCandidate) <<
"\n");
248 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
249 NewCycle->appendEntry(HeaderCandidate);
250 NewCycle->appendBlock(HeaderCandidate);
251 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
256 auto ProcessPredecessors = [&](BlockT *
Block) {
259 bool IsEntry =
false;
261 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
262 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
264 }
else if (!PredDFSInfo) {
289 if (
auto *BlockParent =
Info.getTopLevelParentCycle(
Block)) {
292 if (BlockParent != NewCycle.get()) {
294 <<
"discovered child cycle "
295 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
297 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
299 for (
auto *ChildEntry : BlockParent->entries())
300 ProcessPredecessors(ChildEntry);
303 <<
"known child cycle "
304 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
307 Info.BlockMap.try_emplace(
Block, NewCycle.get());
309 NewCycle->Blocks.insert(
Block);
310 ProcessPredecessors(
Block);
311 Info.BlockMapTopLevel.try_emplace(
Block, NewCycle.get());
313 }
while (!Worklist.
empty());
315 Info.TopLevelCycles.push_back(std::move(NewCycle));
319 for (
auto *TLC :
Info.toplevel_cycles()) {
321 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
323 TLC->ParentCycle =
nullptr;
329template <
typename ContextT>
338template <
typename ContextT>
342 unsigned Counter = 0;
349 if (!BlockDFSInfo.count(
Block)) {
355 << TraverseStack.
size() <<
"\n");
360 bool Added = BlockDFSInfo.try_emplace(
Block, ++Counter).second;
363 BlockPreorder.push_back(
Block);
367 if (DFSTreeStack.
back() == TraverseStack.
size()) {
369 BlockDFSInfo.find(
Block)->second.End = Counter;
376 }
while (!TraverseStack.
empty());
380 errs() <<
"Preorder:\n";
381 for (
int i = 0, e = BlockPreorder.size(); i != e; ++i) {
382 errs() <<
" " << Info.Context.print(BlockPreorder[i]) <<
": " << i <<
"\n";
389 TopLevelCycles.clear();
391 BlockMapTopLevel.clear();
395template <
typename ContextT>
398 Context = ContextT(&
F);
402 Compute.
run(&
F.front());
407template <
typename ContextT>
412 CycleT *
Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
416 addBlockToCycle(NewBlock,
Cycle);
424template <
typename ContextT>
427 return BlockMap.lookup(
Block);
434template <
typename ContextT>
443 while (
A->getDepth() >
B->getDepth())
444 A =
A->getParentCycle();
445 while (
B->getDepth() >
A->getDepth())
446 B =
B->getParentCycle();
452 A =
A->getParentCycle();
453 B =
B->getParentCycle();
463template <
typename ContextT>
476template <
typename ContextT>
482 errs() << File <<
':' << Line
483 <<
": GenericCycleInfo::validateTree: " <<
Cond <<
'\n';
488 reportError(__FILE__, __LINE__, #cond); \
493 for (
const auto *TLC : toplevel_cycles()) {
495 if (
Cycle->ParentCycle)
499 auto MapIt = BlockMap.find(
Block);
500 check(MapIt != BlockMap.end());
508 check(Entries.insert(Entry).second);
513 unsigned ChildDepth = 0;
517 ChildDepth = Child->Depth;
519 check(ChildDepth == Child->Depth);
525 for (
const auto &Entry : BlockMap) {
540template <
typename ContextT>
542 for (
const auto *TLC : toplevel_cycles()) {
544 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)