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>
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;
111 using CycleT =
typename CycleInfoT::CycleT;
120 explicit DFSInfo(
unsigned Start) : Start(Start) {}
124 bool isAncestorOf(
const DFSInfo &
Other)
const {
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(Child->block_begin(), Child->block_end());
182 for (
auto &It : BlockMapTopLevel)
183 if (It.second == Child)
184 It.second = NewParent;
187template <
typename ContextT>
188void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *
Block, CycleT *
Cycle) {
196 while (ParentCycle) {
206template <
typename ContextT>
214 for (BlockT *HeaderCandidate :
llvm::reverse(BlockPreorder)) {
215 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
218 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
219 if (CandidateInfo.isAncestorOf(PredDFSInfo))
222 if (Worklist.
empty()) {
228 <<
Info.Context.print(HeaderCandidate) <<
"\n");
229 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
230 NewCycle->appendEntry(HeaderCandidate);
231 NewCycle->appendBlock(HeaderCandidate);
232 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
237 auto ProcessPredecessors = [&](BlockT *
Block) {
240 bool IsEntry =
false;
242 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
243 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
252 NewCycle->appendEntry(
Block);
260 if (
Block == HeaderCandidate)
266 if (
auto *BlockParent =
Info.getTopLevelParentCycle(
Block)) {
269 if (BlockParent != NewCycle.get()) {
271 <<
"discovered child cycle "
272 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
274 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
276 for (
auto *ChildEntry : BlockParent->entries())
277 ProcessPredecessors(ChildEntry);
280 <<
"known child cycle "
281 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
284 Info.BlockMap.try_emplace(
Block, NewCycle.get());
286 NewCycle->Blocks.insert(
Block);
287 ProcessPredecessors(
Block);
288 Info.BlockMapTopLevel.try_emplace(
Block, NewCycle.get());
290 }
while (!Worklist.
empty());
292 Info.TopLevelCycles.push_back(std::move(NewCycle));
296 for (
auto *TLC :
Info.toplevel_cycles()) {
298 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
300 TLC->ParentCycle =
nullptr;
306template <
typename ContextT>
315template <
typename ContextT>
319 unsigned Counter = 0;
326 if (!BlockDFSInfo.count(
Block)) {
332 << TraverseStack.
size() <<
"\n");
337 bool Added = BlockDFSInfo.try_emplace(
Block, ++Counter).second;
340 BlockPreorder.push_back(
Block);
344 if (DFSTreeStack.
back() == TraverseStack.
size()) {
346 BlockDFSInfo.find(
Block)->second.End = Counter;
353 }
while (!TraverseStack.
empty());
357 errs() <<
"Preorder:\n";
358 for (
int i = 0, e = BlockPreorder.size(); i != e; ++i) {
359 errs() <<
" " << Info.Context.print(BlockPreorder[i]) <<
": " << i <<
"\n";
366 TopLevelCycles.clear();
368 BlockMapTopLevel.clear();
372template <
typename ContextT>
379 Compute.
run(&
F.front());
384template <
typename ContextT>
389 CycleT *
Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
393 addBlockToCycle(NewBlock,
Cycle);
401template <
typename ContextT>
404 return BlockMap.lookup(
Block);
411template <
typename ContextT>
420 while (
A->getDepth() >
B->getDepth())
421 A =
A->getParentCycle();
422 while (
B->getDepth() >
A->getDepth())
423 B =
B->getParentCycle();
429 A =
A->getParentCycle();
430 B =
B->getParentCycle();
440template <
typename ContextT>
453template <
typename ContextT>
459 errs() << File <<
':' << Line
460 <<
": GenericCycleInfo::validateTree: " <<
Cond <<
'\n';
465 reportError(__FILE__, __LINE__, #cond); \
470 for (
const auto *TLC : toplevel_cycles()) {
472 if (
Cycle->ParentCycle)
476 auto MapIt = BlockMap.find(
Block);
477 check(MapIt != BlockMap.end());
485 check(Entries.insert(Entry).second);
490 unsigned ChildDepth = 0;
494 ChildDepth = Child->Depth;
496 check(ChildDepth == Child->Depth);
502 for (
const auto &Entry : BlockMap) {
517template <
typename ContextT>
519 for (
const auto *TLC : toplevel_cycles()) {
521 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.
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)