1 //===- GenericCycleImpl.h -------------------------------------*- C++ -*---===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This template implementation resides in a separate file so that it 11 /// does not get injected into every .cpp file that includes the 12 /// generic header. 13 /// 14 /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO. 15 /// 16 /// This file should only be included by files that implement a 17 /// specialization of the relevant templates. Currently these are: 18 /// - CycleAnalysis.cpp 19 /// - MachineCycleAnalysis.cpp 20 /// 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_ADT_GENERICCYCLEIMPL_H 24 #define LLVM_ADT_GENERICCYCLEIMPL_H 25 26 #include "llvm/ADT/DenseSet.h" 27 #include "llvm/ADT/DepthFirstIterator.h" 28 #include "llvm/ADT/GenericCycleInfo.h" 29 30 #define DEBUG_TYPE "generic-cycle-impl" 31 32 namespace llvm { 33 34 template <typename ContextT> 35 bool GenericCycle<ContextT>::contains(const GenericCycle *C) const { 36 if (!C) 37 return false; 38 39 if (Depth > C->Depth) 40 return false; 41 while (Depth < C->Depth) 42 C = C->ParentCycle; 43 return this == C; 44 } 45 46 template <typename ContextT> 47 void GenericCycle<ContextT>::getExitBlocks( 48 SmallVectorImpl<BlockT *> &TmpStorage) const { 49 TmpStorage.clear(); 50 51 size_t NumExitBlocks = 0; 52 for (BlockT *Block : blocks()) { 53 llvm::append_range(TmpStorage, successors(Block)); 54 55 for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End; 56 ++Idx) { 57 BlockT *Succ = TmpStorage[Idx]; 58 if (!contains(Succ)) { 59 auto ExitEndIt = TmpStorage.begin() + NumExitBlocks; 60 if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt) 61 TmpStorage[NumExitBlocks++] = Succ; 62 } 63 } 64 65 TmpStorage.resize(NumExitBlocks); 66 } 67 } 68 69 template <typename ContextT> 70 auto GenericCycle<ContextT>::getCyclePreheader() const -> BlockT * { 71 BlockT *Predecessor = getCyclePredecessor(); 72 if (!Predecessor) 73 return nullptr; 74 75 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!"); 76 77 if (succ_size(Predecessor) != 1) 78 return nullptr; 79 80 // Make sure we are allowed to hoist instructions into the predecessor. 81 if (!Predecessor->isLegalToHoistInto()) 82 return nullptr; 83 84 return Predecessor; 85 } 86 87 template <typename ContextT> 88 auto GenericCycle<ContextT>::getCyclePredecessor() const -> BlockT * { 89 if (!isReducible()) 90 return nullptr; 91 92 BlockT *Out = nullptr; 93 94 // Loop over the predecessors of the header node... 95 BlockT *Header = getHeader(); 96 for (const auto Pred : predecessors(Header)) { 97 if (!contains(Pred)) { 98 if (Out && Out != Pred) 99 return nullptr; 100 Out = Pred; 101 } 102 } 103 104 return Out; 105 } 106 107 /// \brief Helper class for computing cycle information. 108 template <typename ContextT> class GenericCycleInfoCompute { 109 using BlockT = typename ContextT::BlockT; 110 using CycleInfoT = GenericCycleInfo<ContextT>; 111 using CycleT = typename CycleInfoT::CycleT; 112 113 CycleInfoT &Info; 114 115 struct DFSInfo { 116 unsigned Start = 0; // DFS start; positive if block is found 117 unsigned End = 0; // DFS end 118 119 DFSInfo() = default; 120 explicit DFSInfo(unsigned Start) : Start(Start) {} 121 122 /// Whether this node is an ancestor (or equal to) the node \p Other 123 /// in the DFS tree. 124 bool isAncestorOf(const DFSInfo &Other) const { 125 return Start <= Other.Start && Other.End <= End; 126 } 127 }; 128 129 DenseMap<BlockT *, DFSInfo> BlockDFSInfo; 130 SmallVector<BlockT *, 8> BlockPreorder; 131 132 GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete; 133 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete; 134 135 public: 136 GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {} 137 138 void run(BlockT *EntryBlock); 139 140 static void updateDepth(CycleT *SubTree); 141 142 private: 143 void dfs(BlockT *EntryBlock); 144 }; 145 146 template <typename ContextT> 147 auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(BlockT *Block) 148 -> CycleT * { 149 auto Cycle = BlockMapTopLevel.find(Block); 150 if (Cycle != BlockMapTopLevel.end()) 151 return Cycle->second; 152 153 auto MapIt = BlockMap.find(Block); 154 if (MapIt == BlockMap.end()) 155 return nullptr; 156 157 auto *C = MapIt->second; 158 while (C->ParentCycle) 159 C = C->ParentCycle; 160 BlockMapTopLevel.try_emplace(Block, C); 161 return C; 162 } 163 164 template <typename ContextT> 165 void GenericCycleInfo<ContextT>::moveTopLevelCycleToNewParent(CycleT *NewParent, 166 CycleT *Child) { 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; 171 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool { 172 return Child == Ptr.get(); 173 }); 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; 179 180 NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(), 181 Child->block_end()); 182 183 for (auto &It : BlockMapTopLevel) 184 if (It.second == Child) 185 It.second = NewParent; 186 } 187 188 /// \brief Main function of the cycle info computations. 189 template <typename ContextT> 190 void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) { 191 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock) 192 << "\n"); 193 dfs(EntryBlock); 194 195 SmallVector<BlockT *, 8> Worklist; 196 197 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) { 198 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate); 199 200 for (BlockT *Pred : predecessors(HeaderCandidate)) { 201 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred); 202 if (CandidateInfo.isAncestorOf(PredDFSInfo)) 203 Worklist.push_back(Pred); 204 } 205 if (Worklist.empty()) { 206 continue; 207 } 208 209 // Found a cycle with the candidate as its header. 210 LLVM_DEBUG(errs() << "Found cycle for header: " 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()); 216 217 // Helper function to process (non-back-edge) predecessors of a discovered 218 // block and either add them to the worklist or recognize that the given 219 // block is an additional cycle entry. 220 auto ProcessPredecessors = [&](BlockT *Block) { 221 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": "); 222 223 bool IsEntry = false; 224 for (BlockT *Pred : predecessors(Block)) { 225 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred); 226 if (CandidateInfo.isAncestorOf(PredDFSInfo)) { 227 Worklist.push_back(Pred); 228 } else { 229 IsEntry = true; 230 } 231 } 232 if (IsEntry) { 233 assert(!NewCycle->isEntry(Block)); 234 LLVM_DEBUG(errs() << "append as entry\n"); 235 NewCycle->appendEntry(Block); 236 } else { 237 LLVM_DEBUG(errs() << "append as child\n"); 238 } 239 }; 240 241 do { 242 BlockT *Block = Worklist.pop_back_val(); 243 if (Block == HeaderCandidate) 244 continue; 245 246 // If the block has already been discovered by some cycle 247 // (possibly by ourself), then the outermost cycle containing it 248 // should become our child. 249 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) { 250 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": "); 251 252 if (BlockParent != NewCycle.get()) { 253 LLVM_DEBUG(errs() 254 << "discovered child cycle " 255 << Info.Context.print(BlockParent->getHeader()) << "\n"); 256 // Make BlockParent the child of NewCycle. 257 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent); 258 259 for (auto *ChildEntry : BlockParent->entries()) 260 ProcessPredecessors(ChildEntry); 261 } else { 262 LLVM_DEBUG(errs() 263 << "known child cycle " 264 << Info.Context.print(BlockParent->getHeader()) << "\n"); 265 } 266 } else { 267 Info.BlockMap.try_emplace(Block, NewCycle.get()); 268 assert(!is_contained(NewCycle->Blocks, Block)); 269 NewCycle->Blocks.push_back(Block); 270 ProcessPredecessors(Block); 271 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get()); 272 } 273 } while (!Worklist.empty()); 274 275 Info.TopLevelCycles.push_back(std::move(NewCycle)); 276 } 277 278 // Fix top-level cycle links and compute cycle depths. 279 for (auto *TLC : Info.toplevel_cycles()) { 280 LLVM_DEBUG(errs() << "top-level cycle: " 281 << Info.Context.print(TLC->getHeader()) << "\n"); 282 283 TLC->ParentCycle = nullptr; 284 updateDepth(TLC); 285 } 286 } 287 288 /// \brief Recompute depth values of \p SubTree and all descendants. 289 template <typename ContextT> 290 void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) { 291 for (CycleT *Cycle : depth_first(SubTree)) 292 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1; 293 } 294 295 /// \brief Compute a DFS of basic blocks starting at the function entry. 296 /// 297 /// Fills BlockDFSInfo with start/end counters and BlockPreorder. 298 template <typename ContextT> 299 void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) { 300 SmallVector<unsigned, 8> DFSTreeStack; 301 SmallVector<BlockT *, 8> TraverseStack; 302 unsigned Counter = 0; 303 TraverseStack.emplace_back(EntryBlock); 304 305 do { 306 BlockT *Block = TraverseStack.back(); 307 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block) 308 << "\n"); 309 if (!BlockDFSInfo.count(Block)) { 310 // We're visiting the block for the first time. Open its DFSInfo, add 311 // successors to the traversal stack, and remember the traversal stack 312 // depth at which the block was opened, so that we can correctly record 313 // its end time. 314 LLVM_DEBUG(errs() << " first encountered at depth " 315 << TraverseStack.size() << "\n"); 316 317 DFSTreeStack.emplace_back(TraverseStack.size()); 318 llvm::append_range(TraverseStack, successors(Block)); 319 320 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second; 321 (void)Added; 322 assert(Added); 323 BlockPreorder.push_back(Block); 324 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n"); 325 } else { 326 assert(!DFSTreeStack.empty()); 327 if (DFSTreeStack.back() == TraverseStack.size()) { 328 LLVM_DEBUG(errs() << " ended at " << Counter << "\n"); 329 BlockDFSInfo.find(Block)->second.End = Counter; 330 DFSTreeStack.pop_back(); 331 } else { 332 LLVM_DEBUG(errs() << " already done\n"); 333 } 334 TraverseStack.pop_back(); 335 } 336 } while (!TraverseStack.empty()); 337 assert(DFSTreeStack.empty()); 338 339 LLVM_DEBUG( 340 errs() << "Preorder:\n"; 341 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) { 342 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n"; 343 } 344 ); 345 } 346 347 /// \brief Reset the object to its initial state. 348 template <typename ContextT> void GenericCycleInfo<ContextT>::clear() { 349 TopLevelCycles.clear(); 350 BlockMap.clear(); 351 BlockMapTopLevel.clear(); 352 } 353 354 /// \brief Compute the cycle info for a function. 355 template <typename ContextT> 356 void GenericCycleInfo<ContextT>::compute(FunctionT &F) { 357 GenericCycleInfoCompute<ContextT> Compute(*this); 358 Context.setFunction(F); 359 360 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName() 361 << "\n"); 362 Compute.run(ContextT::getEntryBlock(F)); 363 364 assert(validateTree()); 365 } 366 367 /// \brief Find the innermost cycle containing a given block. 368 /// 369 /// \returns the innermost cycle containing \p Block or nullptr if 370 /// it is not contained in any cycle. 371 template <typename ContextT> 372 auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const 373 -> CycleT * { 374 auto MapIt = BlockMap.find(Block); 375 if (MapIt != BlockMap.end()) 376 return MapIt->second; 377 return nullptr; 378 } 379 380 /// \brief get the depth for the cycle which containing a given block. 381 /// 382 /// \returns the depth for the innermost cycle containing \p Block or 0 if it is 383 /// not contained in any cycle. 384 template <typename ContextT> 385 unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const { 386 CycleT *Cycle = getCycle(Block); 387 if (!Cycle) 388 return 0; 389 return Cycle->getDepth(); 390 } 391 392 #ifndef NDEBUG 393 /// \brief Validate the internal consistency of the cycle tree. 394 /// 395 /// Note that this does \em not check that cycles are really cycles in the CFG, 396 /// or that the right set of cycles in the CFG were found. 397 template <typename ContextT> 398 bool GenericCycleInfo<ContextT>::validateTree() const { 399 DenseSet<BlockT *> Blocks; 400 DenseSet<BlockT *> Entries; 401 402 auto reportError = [](const char *File, int Line, const char *Cond) { 403 errs() << File << ':' << Line 404 << ": GenericCycleInfo::validateTree: " << Cond << '\n'; 405 }; 406 #define check(cond) \ 407 do { \ 408 if (!(cond)) { \ 409 reportError(__FILE__, __LINE__, #cond); \ 410 return false; \ 411 } \ 412 } while (false) 413 414 for (const auto *TLC : toplevel_cycles()) { 415 for (const CycleT *Cycle : depth_first(TLC)) { 416 if (Cycle->ParentCycle) 417 check(is_contained(Cycle->ParentCycle->children(), Cycle)); 418 419 for (BlockT *Block : Cycle->Blocks) { 420 auto MapIt = BlockMap.find(Block); 421 check(MapIt != BlockMap.end()); 422 check(Cycle->contains(MapIt->second)); 423 check(Blocks.insert(Block).second); // duplicates in block list? 424 } 425 Blocks.clear(); 426 427 check(!Cycle->Entries.empty()); 428 for (BlockT *Entry : Cycle->Entries) { 429 check(Entries.insert(Entry).second); // duplicate entry? 430 check(is_contained(Cycle->Blocks, Entry)); 431 } 432 Entries.clear(); 433 434 unsigned ChildDepth = 0; 435 for (const CycleT *Child : Cycle->children()) { 436 check(Child->Depth > Cycle->Depth); 437 if (!ChildDepth) { 438 ChildDepth = Child->Depth; 439 } else { 440 check(ChildDepth == Child->Depth); 441 } 442 } 443 } 444 } 445 446 for (const auto &Entry : BlockMap) { 447 BlockT *Block = Entry.first; 448 for (const CycleT *Cycle = Entry.second; Cycle; 449 Cycle = Cycle->ParentCycle) { 450 check(is_contained(Cycle->Blocks, Block)); 451 } 452 } 453 454 #undef check 455 456 return true; 457 } 458 #endif 459 460 /// \brief Print the cycle info. 461 template <typename ContextT> 462 void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const { 463 for (const auto *TLC : toplevel_cycles()) { 464 for (const CycleT *Cycle : depth_first(TLC)) { 465 for (unsigned I = 0; I < Cycle->Depth; ++I) 466 Out << " "; 467 468 Out << Cycle->print(Context) << '\n'; 469 } 470 } 471 } 472 473 } // namespace llvm 474 475 #undef DEBUG_TYPE 476 477 #endif // LLVM_ADT_GENERICCYCLEIMPL_H 478