23#ifndef LLVM_ADT_GENERICCYCLEIMPL_H
24#define LLVM_ADT_GENERICCYCLEIMPL_H
31#define DEBUG_TYPE "generic-cycle-impl"
35template <
typename ContextT>
42 while (Depth < C->
Depth)
47template <
typename ContextT>
50 if (!ExitBlocksCache.empty()) {
51 TmpStorage = ExitBlocksCache;
57 size_t NumExitBlocks = 0;
65 auto ExitEndIt = TmpStorage.
begin() + NumExitBlocks;
66 if (std::find(TmpStorage.
begin(), ExitEndIt, Succ) == ExitEndIt)
67 TmpStorage[NumExitBlocks++] = Succ;
71 TmpStorage.
resize(NumExitBlocks);
73 ExitBlocksCache.append(TmpStorage.
begin(), TmpStorage.
end());
76template <
typename ContextT>
91template <
typename ContextT>
93 BlockT *Predecessor = getCyclePredecessor();
97 assert(isReducible() &&
"Cycle Predecessor must be in a reducible cycle!");
103 if (!Predecessor->isLegalToHoistInto())
109template <
typename ContextT>
117 BlockT *Header = getHeader();
120 if (Out && Out != Pred)
137 assert(!Entries.empty() &&
"Cycle must have one or more entries.");
140 for (
BlockT *Entry : entries()) {
141 assert(Entries.insert(Entry).second);
147 getExitBlocks(ExitBBs);
158 "Cycle block has no in-cycle successors!");
162 "Cycle block has no in-cycle predecessors!");
165 for (
BlockT *
B : llvm::inverse_children<BlockT *>(BB))
169 if (Entries.contains(BB)) {
170 assert(!OutsideCyclePreds.
empty() &&
"Entry is unreachable!");
171 }
else if (!OutsideCyclePreds.
empty()) {
175 BlockT *EntryBB = &BB->getParent()->front();
178 "Non-entry block reachable from outside!");
181 "Cycle contains function entry block!");
186 if (VisitedBBs.
size() != getNumBlocks()) {
187 dbgs() <<
"The following blocks are unreachable in the cycle:\n ";
190 if (!VisitedBBs.
count(BB)) {
192 BB->printAsOperand(
dbgs());
206template <
typename ContextT>
212 for (
BlockT *BB : Child->blocks()) {
214 "Cycle does not contain all the blocks of a subcycle!");
222 "Cycle is not a subcycle of its parent!");
229 using BlockT =
typename ContextT::BlockT;
231 using CycleT =
typename CycleInfoT::CycleT;
240 explicit DFSInfo(
unsigned Start) : Start(Start) {}
242 explicit operator bool()
const {
return Start; }
246 bool isAncestorOf(
const DFSInfo &
Other)
const {
260 void run(BlockT *EntryBlock);
265 void dfs(BlockT *EntryBlock);
268template <
typename ContextT>
272 if (
Cycle != BlockMapTopLevel.end())
273 return Cycle->second;
275 auto MapIt = BlockMap.find(
Block);
276 if (MapIt == BlockMap.end())
279 auto *
C = MapIt->second;
280 while (
C->ParentCycle)
282 BlockMapTopLevel.try_emplace(
Block,
C);
286template <
typename ContextT>
289 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
290 "NewParent and Child must be both top level cycle!\n");
291 auto &CurrentContainer =
292 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
294 return Child ==
Ptr.get();
296 assert(Pos != CurrentContainer.end());
297 NewParent->Children.push_back(std::move(*Pos));
298 *Pos = std::move(CurrentContainer.back());
299 CurrentContainer.pop_back();
300 Child->ParentCycle = NewParent;
302 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
304 for (
auto &It : BlockMapTopLevel)
305 if (It.second == Child)
306 It.second = NewParent;
307 NewParent->clearCache();
311template <
typename ContextT>
320 while (ParentCycle) {
331template <
typename ContextT>
339 for (BlockT *HeaderCandidate :
llvm::reverse(BlockPreorder)) {
340 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
343 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
346 if (CandidateInfo.isAncestorOf(PredDFSInfo))
349 if (Worklist.
empty()) {
355 <<
Info.Context.print(HeaderCandidate) <<
"\n");
356 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
357 NewCycle->appendEntry(HeaderCandidate);
358 NewCycle->appendBlock(HeaderCandidate);
359 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
364 auto ProcessPredecessors = [&](BlockT *
Block) {
367 bool IsEntry =
false;
369 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
370 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
372 }
else if (!PredDFSInfo) {
383 NewCycle->appendEntry(
Block);
391 if (
Block == HeaderCandidate)
397 if (
auto *BlockParent =
Info.getTopLevelParentCycle(
Block)) {
400 if (BlockParent != NewCycle.get()) {
402 <<
"discovered child cycle "
403 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
405 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
407 for (
auto *ChildEntry : BlockParent->entries())
408 ProcessPredecessors(ChildEntry);
411 <<
"known child cycle "
412 <<
Info.Context.print(BlockParent->getHeader()) <<
"\n");
415 Info.BlockMap.try_emplace(
Block, NewCycle.get());
417 NewCycle->Blocks.insert(
Block);
418 ProcessPredecessors(
Block);
419 Info.BlockMapTopLevel.try_emplace(
Block, NewCycle.get());
421 }
while (!Worklist.
empty());
423 Info.TopLevelCycles.push_back(std::move(NewCycle));
427 for (
auto *TLC :
Info.toplevel_cycles()) {
429 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
431 TLC->ParentCycle =
nullptr;
437template <
typename ContextT>
446template <
typename ContextT>
450 unsigned Counter = 0;
457 if (!BlockDFSInfo.count(
Block)) {
463 << TraverseStack.
size() <<
"\n");
468 bool Added = BlockDFSInfo.try_emplace(
Block, ++Counter).second;
471 BlockPreorder.push_back(
Block);
475 if (DFSTreeStack.
back() == TraverseStack.
size()) {
477 BlockDFSInfo.find(
Block)->second.End = Counter;
484 }
while (!TraverseStack.
empty());
488 errs() <<
"Preorder:\n";
489 for (
int i = 0, e = BlockPreorder.size(); i != e; ++i) {
490 errs() <<
" " << Info.Context.print(BlockPreorder[i]) <<
": " << i <<
"\n";
497 TopLevelCycles.clear();
499 BlockMapTopLevel.clear();
503template <
typename ContextT>
506 Context = ContextT(&
F);
510 Compute.
run(&
F.front());
513template <
typename ContextT>
518 CycleT *
Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
522 addBlockToCycle(NewBlock,
Cycle);
530template <
typename ContextT>
533 return BlockMap.lookup(
Block);
540template <
typename ContextT>
549 while (
A->getDepth() >
B->getDepth())
550 A =
A->getParentCycle();
551 while (
B->getDepth() >
A->getDepth())
552 B =
B->getParentCycle();
558 A =
A->getParentCycle();
559 B =
B->getParentCycle();
569template <
typename ContextT>
581template <
typename ContextT>
586 for (
CycleT *TopCycle : toplevel_cycles()) {
596 auto MapIt = BlockMap.find(BB);
597 assert(MapIt != BlockMap.end());
607 verifyCycleNest(
true);
611template <
typename ContextT>
613 for (
const auto *TLC : toplevel_cycles()) {
615 for (
unsigned I = 0;
I <
Cycle->Depth; ++
I)
static const Function * getParent(const Value *V)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
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.
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 verify() const
Verify that the entire cycle tree well-formed.
void addBlockToCycle(BlockT *Block, CycleT *Cycle)
Assumes that Cycle is the innermost cycle containing Block.
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.
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.
void verifyCycleNest(bool VerifyFull=false) const
Methods for debug and self-test.
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 clearCache() const
Clear the cache of the cycle.
BlockT * getHeader() const
void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all blocks of this cycle that have successor outside of this cycle.
void verifyCycle() const
Verify that this is actually a well-formed cycle in the CFG.
void verifyCycleNest() const
Verify the parent-child relations of this cycle.
Printable print(const ContextT &Ctx) const
iterator_range< const_block_iterator > blocks() 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
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto succ_size(const MachineBasicBlock *BB)
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)
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
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)
std::pair< iterator, bool > insert(NodeRef N)