23 #ifndef LLVM_ADT_GENERICCYCLEIMPL_H
24 #define LLVM_ADT_GENERICCYCLEIMPL_H
30 #define DEBUG_TYPE "generic-cycle-impl"
34 template <
typename ContextT>
41 while (Depth < C->
Depth)
46 template <
typename ContextT>
51 size_t NumExitBlocks = 0;
52 for (
BlockT *Block : blocks()) {
55 for (
size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
57 BlockT *Succ = TmpStorage[Idx];
59 auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
60 if (
std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
61 TmpStorage[NumExitBlocks++] = Succ;
65 TmpStorage.
resize(NumExitBlocks);
69 template <
typename ContextT>
71 BlockT *Predecessor = getCyclePredecessor();
75 assert(isReducible() &&
"Cycle Predecessor must be in a reducible cycle!");
81 if (!Predecessor->isLegalToHoistInto())
87 template <
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);
146 template <
typename ContextT>
149 auto Cycle = BlockMapTopLevel.find(Block);
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);
164 template <
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;
189 template <
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))
203 Worklist.push_back(Pred);
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)) {
227 Worklist.push_back(Pred);
233 assert(!NewCycle->isEntry(Block));
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");
267 Info.BlockMap.try_emplace(Block, NewCycle.get());
269 NewCycle->Blocks.push_back(Block);
270 ProcessPredecessors(Block);
271 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
273 }
while (!Worklist.empty());
279 for (
auto *TLC :
Info.toplevel_cycles()) {
281 <<
Info.Context.print(TLC->getHeader()) <<
"\n");
283 TLC->ParentCycle =
nullptr;
289 template <
typename ContextT>
298 template <
typename ContextT>
302 unsigned Counter = 0;
306 BlockT *Block = TraverseStack.back();
309 if (!BlockDFSInfo.count(Block)) {
315 << TraverseStack.size() <<
"\n");
320 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
323 BlockPreorder.push_back(Block);
326 assert(!DFSTreeStack.empty());
327 if (DFSTreeStack.back() == TraverseStack.size()) {
329 BlockDFSInfo.find(Block)->second.End = Counter;
330 DFSTreeStack.pop_back();
334 TraverseStack.pop_back();
336 }
while (!TraverseStack.empty());
337 assert(DFSTreeStack.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();
355 template <
typename ContextT>
362 Compute.
run(ContextT::getEntryBlock(
F));
371 template <
typename ContextT>
374 auto MapIt = BlockMap.find(Block);
375 if (MapIt != BlockMap.end())
376 return MapIt->second;
384 template <
typename ContextT>
397 template <
typename ContextT>
403 errs() << File <<
':' << Line
404 <<
": GenericCycleInfo::validateTree: " <<
Cond <<
'\n';
406 #define check(cond) \
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) {
447 BlockT *Block = Entry.first;
461 template <
typename ContextT>
463 for (
const auto *TLC : toplevel_cycles()) {
465 for (
unsigned I = 0;
I <
Cycle->Depth; ++
I)
477 #endif // LLVM_ADT_GENERICCYCLEIMPL_H