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 /// - llvm/lib/IR/CycleInfo.cpp 19 /// - llvm/lib/CodeGen/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(Child->block_begin(), Child->block_end()); 181 182 for (auto &It : BlockMapTopLevel) 183 if (It.second == Child) 184 It.second = NewParent; 185 } 186 187 /// \brief Main function of the cycle info computations. 188 template <typename ContextT> 189 void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) { 190 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock) 191 << "\n"); 192 dfs(EntryBlock); 193 194 SmallVector<BlockT *, 8> Worklist; 195 196 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) { 197 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate); 198 199 for (BlockT *Pred : predecessors(HeaderCandidate)) { 200 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred); 201 if (CandidateInfo.isAncestorOf(PredDFSInfo)) 202 Worklist.push_back(Pred); 203 } 204 if (Worklist.empty()) { 205 continue; 206 } 207 208 // Found a cycle with the candidate as its header. 209 LLVM_DEBUG(errs() << "Found cycle for header: " 210 << Info.Context.print(HeaderCandidate) << "\n"); 211 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>(); 212 NewCycle->appendEntry(HeaderCandidate); 213 NewCycle->appendBlock(HeaderCandidate); 214 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get()); 215 216 // Helper function to process (non-back-edge) predecessors of a discovered 217 // block and either add them to the worklist or recognize that the given 218 // block is an additional cycle entry. 219 auto ProcessPredecessors = [&](BlockT *Block) { 220 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": "); 221 222 bool IsEntry = false; 223 for (BlockT *Pred : predecessors(Block)) { 224 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred); 225 if (CandidateInfo.isAncestorOf(PredDFSInfo)) { 226 Worklist.push_back(Pred); 227 } else { 228 IsEntry = true; 229 } 230 } 231 if (IsEntry) { 232 assert(!NewCycle->isEntry(Block)); 233 LLVM_DEBUG(errs() << "append as entry\n"); 234 NewCycle->appendEntry(Block); 235 } else { 236 LLVM_DEBUG(errs() << "append as child\n"); 237 } 238 }; 239 240 do { 241 BlockT *Block = Worklist.pop_back_val(); 242 if (Block == HeaderCandidate) 243 continue; 244 245 // If the block has already been discovered by some cycle 246 // (possibly by ourself), then the outermost cycle containing it 247 // should become our child. 248 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) { 249 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": "); 250 251 if (BlockParent != NewCycle.get()) { 252 LLVM_DEBUG(errs() 253 << "discovered child cycle " 254 << Info.Context.print(BlockParent->getHeader()) << "\n"); 255 // Make BlockParent the child of NewCycle. 256 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent); 257 258 for (auto *ChildEntry : BlockParent->entries()) 259 ProcessPredecessors(ChildEntry); 260 } else { 261 LLVM_DEBUG(errs() 262 << "known child cycle " 263 << Info.Context.print(BlockParent->getHeader()) << "\n"); 264 } 265 } else { 266 Info.BlockMap.try_emplace(Block, NewCycle.get()); 267 assert(!is_contained(NewCycle->Blocks, Block)); 268 NewCycle->Blocks.insert(Block); 269 ProcessPredecessors(Block); 270 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get()); 271 } 272 } while (!Worklist.empty()); 273 274 Info.TopLevelCycles.push_back(std::move(NewCycle)); 275 } 276 277 // Fix top-level cycle links and compute cycle depths. 278 for (auto *TLC : Info.toplevel_cycles()) { 279 LLVM_DEBUG(errs() << "top-level cycle: " 280 << Info.Context.print(TLC->getHeader()) << "\n"); 281 282 TLC->ParentCycle = nullptr; 283 updateDepth(TLC); 284 } 285 } 286 287 /// \brief Recompute depth values of \p SubTree and all descendants. 288 template <typename ContextT> 289 void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) { 290 for (CycleT *Cycle : depth_first(SubTree)) 291 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1; 292 } 293 294 /// \brief Compute a DFS of basic blocks starting at the function entry. 295 /// 296 /// Fills BlockDFSInfo with start/end counters and BlockPreorder. 297 template <typename ContextT> 298 void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) { 299 SmallVector<unsigned, 8> DFSTreeStack; 300 SmallVector<BlockT *, 8> TraverseStack; 301 unsigned Counter = 0; 302 TraverseStack.emplace_back(EntryBlock); 303 304 do { 305 BlockT *Block = TraverseStack.back(); 306 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block) 307 << "\n"); 308 if (!BlockDFSInfo.count(Block)) { 309 // We're visiting the block for the first time. Open its DFSInfo, add 310 // successors to the traversal stack, and remember the traversal stack 311 // depth at which the block was opened, so that we can correctly record 312 // its end time. 313 LLVM_DEBUG(errs() << " first encountered at depth " 314 << TraverseStack.size() << "\n"); 315 316 DFSTreeStack.emplace_back(TraverseStack.size()); 317 llvm::append_range(TraverseStack, successors(Block)); 318 319 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second; 320 (void)Added; 321 assert(Added); 322 BlockPreorder.push_back(Block); 323 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n"); 324 } else { 325 assert(!DFSTreeStack.empty()); 326 if (DFSTreeStack.back() == TraverseStack.size()) { 327 LLVM_DEBUG(errs() << " ended at " << Counter << "\n"); 328 BlockDFSInfo.find(Block)->second.End = Counter; 329 DFSTreeStack.pop_back(); 330 } else { 331 LLVM_DEBUG(errs() << " already done\n"); 332 } 333 TraverseStack.pop_back(); 334 } 335 } while (!TraverseStack.empty()); 336 assert(DFSTreeStack.empty()); 337 338 LLVM_DEBUG( 339 errs() << "Preorder:\n"; 340 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) { 341 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n"; 342 } 343 ); 344 } 345 346 /// \brief Reset the object to its initial state. 347 template <typename ContextT> void GenericCycleInfo<ContextT>::clear() { 348 TopLevelCycles.clear(); 349 BlockMap.clear(); 350 BlockMapTopLevel.clear(); 351 } 352 353 /// \brief Compute the cycle info for a function. 354 template <typename ContextT> 355 void GenericCycleInfo<ContextT>::compute(FunctionT &F) { 356 GenericCycleInfoCompute<ContextT> Compute(*this); 357 Context.setFunction(F); 358 359 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName() 360 << "\n"); 361 Compute.run(ContextT::getEntryBlock(F)); 362 363 assert(validateTree()); 364 } 365 366 /// \brief Find the innermost cycle containing a given block. 367 /// 368 /// \returns the innermost cycle containing \p Block or nullptr if 369 /// it is not contained in any cycle. 370 template <typename ContextT> 371 auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const 372 -> CycleT * { 373 auto MapIt = BlockMap.find(Block); 374 if (MapIt != BlockMap.end()) 375 return MapIt->second; 376 return nullptr; 377 } 378 379 /// \brief get the depth for the cycle which containing a given block. 380 /// 381 /// \returns the depth for the innermost cycle containing \p Block or 0 if it is 382 /// not contained in any cycle. 383 template <typename ContextT> 384 unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const { 385 CycleT *Cycle = getCycle(Block); 386 if (!Cycle) 387 return 0; 388 return Cycle->getDepth(); 389 } 390 391 #ifndef NDEBUG 392 /// \brief Validate the internal consistency of the cycle tree. 393 /// 394 /// Note that this does \em not check that cycles are really cycles in the CFG, 395 /// or that the right set of cycles in the CFG were found. 396 template <typename ContextT> 397 bool GenericCycleInfo<ContextT>::validateTree() const { 398 DenseSet<BlockT *> Blocks; 399 DenseSet<BlockT *> Entries; 400 401 auto reportError = [](const char *File, int Line, const char *Cond) { 402 errs() << File << ':' << Line 403 << ": GenericCycleInfo::validateTree: " << Cond << '\n'; 404 }; 405 #define check(cond) \ 406 do { \ 407 if (!(cond)) { \ 408 reportError(__FILE__, __LINE__, #cond); \ 409 return false; \ 410 } \ 411 } while (false) 412 413 for (const auto *TLC : toplevel_cycles()) { 414 for (const CycleT *Cycle : depth_first(TLC)) { 415 if (Cycle->ParentCycle) 416 check(is_contained(Cycle->ParentCycle->children(), Cycle)); 417 418 for (BlockT *Block : Cycle->Blocks) { 419 auto MapIt = BlockMap.find(Block); 420 check(MapIt != BlockMap.end()); 421 check(Cycle->contains(MapIt->second)); 422 check(Blocks.insert(Block).second); // duplicates in block list? 423 } 424 Blocks.clear(); 425 426 check(!Cycle->Entries.empty()); 427 for (BlockT *Entry : Cycle->Entries) { 428 check(Entries.insert(Entry).second); // duplicate entry? 429 check(is_contained(Cycle->Blocks, Entry)); 430 } 431 Entries.clear(); 432 433 unsigned ChildDepth = 0; 434 for (const CycleT *Child : Cycle->children()) { 435 check(Child->Depth > Cycle->Depth); 436 if (!ChildDepth) { 437 ChildDepth = Child->Depth; 438 } else { 439 check(ChildDepth == Child->Depth); 440 } 441 } 442 } 443 } 444 445 for (const auto &Entry : BlockMap) { 446 BlockT *Block = Entry.first; 447 for (const CycleT *Cycle = Entry.second; Cycle; 448 Cycle = Cycle->ParentCycle) { 449 check(is_contained(Cycle->Blocks, Block)); 450 } 451 } 452 453 #undef check 454 455 return true; 456 } 457 #endif 458 459 /// \brief Print the cycle info. 460 template <typename ContextT> 461 void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const { 462 for (const auto *TLC : toplevel_cycles()) { 463 for (const CycleT *Cycle : depth_first(TLC)) { 464 for (unsigned I = 0; I < Cycle->Depth; ++I) 465 Out << " "; 466 467 Out << Cycle->print(Context) << '\n'; 468 } 469 } 470 } 471 472 } // namespace llvm 473 474 #undef DEBUG_TYPE 475 476 #endif // LLVM_ADT_GENERICCYCLEIMPL_H 477