1 //===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Calculate a program structure tree built out of single entry single exit 11 // regions. 12 // The basic ideas are taken from "The Program Structure Tree - Richard Johnson, 13 // David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The 14 // Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana 15 // Koehler - 2009". 16 // The algorithm to calculate these data structures however is completely 17 // different, as it takes advantage of existing information already available 18 // in (Post)dominace tree and dominance frontier passes. This leads to a simpler 19 // and in practice hopefully better performing algorithm. The runtime of the 20 // algorithms described in the papers above are both linear in graph size, 21 // O(V+E), whereas this algorithm is not, as the dominance frontier information 22 // itself is not, but in practice runtime seems to be in the order of magnitude 23 // of dominance tree calculation. 24 // 25 // WARNING: LLVM is generally very concerned about compile time such that 26 // the use of additional analysis passes in the default 27 // optimization sequence is avoided as much as possible. 28 // Specifically, if you do not need the RegionInfo, but dominance 29 // information could be sufficient please base your work only on 30 // the dominator tree. Most passes maintain it, such that using 31 // it has often near zero cost. In contrast RegionInfo is by 32 // default not available, is not maintained by existing 33 // transformations and there is no intention to do so. 34 // 35 //===----------------------------------------------------------------------===// 36 37 #ifndef LLVM_ANALYSIS_REGIONINFO_H 38 #define LLVM_ANALYSIS_REGIONINFO_H 39 40 #include "llvm/ADT/DenseMap.h" 41 #include "llvm/ADT/DepthFirstIterator.h" 42 #include "llvm/ADT/GraphTraits.h" 43 #include "llvm/ADT/PointerIntPair.h" 44 #include "llvm/ADT/iterator_range.h" 45 #include "llvm/IR/BasicBlock.h" 46 #include "llvm/IR/Dominators.h" 47 #include "llvm/IR/PassManager.h" 48 #include "llvm/Pass.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include <algorithm> 51 #include <cassert> 52 #include <map> 53 #include <memory> 54 #include <set> 55 #include <string> 56 #include <type_traits> 57 #include <vector> 58 59 namespace llvm { 60 61 class DominanceFrontier; 62 class DominatorTree; 63 class Loop; 64 class LoopInfo; 65 struct PostDominatorTree; 66 class Region; 67 template <class RegionTr> class RegionBase; 68 class RegionInfo; 69 template <class RegionTr> class RegionInfoBase; 70 class RegionNode; 71 72 // Class to be specialized for different users of RegionInfo 73 // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to 74 // pass around an unreasonable number of template parameters. 75 template <class FuncT_> 76 struct RegionTraits { 77 // FuncT 78 // BlockT 79 // RegionT 80 // RegionNodeT 81 // RegionInfoT 82 using BrokenT = typename FuncT_::UnknownRegionTypeError; 83 }; 84 85 template <> 86 struct RegionTraits<Function> { 87 using FuncT = Function; 88 using BlockT = BasicBlock; 89 using RegionT = Region; 90 using RegionNodeT = RegionNode; 91 using RegionInfoT = RegionInfo; 92 using DomTreeT = DominatorTree; 93 using DomTreeNodeT = DomTreeNode; 94 using DomFrontierT = DominanceFrontier; 95 using PostDomTreeT = PostDominatorTree; 96 using InstT = Instruction; 97 using LoopT = Loop; 98 using LoopInfoT = LoopInfo; 99 100 static unsigned getNumSuccessors(BasicBlock *BB) { 101 return BB->getTerminator()->getNumSuccessors(); 102 } 103 }; 104 105 /// @brief Marker class to iterate over the elements of a Region in flat mode. 106 /// 107 /// The class is used to either iterate in Flat mode or by not using it to not 108 /// iterate in Flat mode. During a Flat mode iteration all Regions are entered 109 /// and the iteration returns every BasicBlock. If the Flat mode is not 110 /// selected for SubRegions just one RegionNode containing the subregion is 111 /// returned. 112 template <class GraphType> 113 class FlatIt {}; 114 115 /// @brief A RegionNode represents a subregion or a BasicBlock that is part of a 116 /// Region. 117 template <class Tr> 118 class RegionNodeBase { 119 friend class RegionBase<Tr>; 120 121 public: 122 using BlockT = typename Tr::BlockT; 123 using RegionT = typename Tr::RegionT; 124 125 private: 126 /// This is the entry basic block that starts this region node. If this is a 127 /// BasicBlock RegionNode, then entry is just the basic block, that this 128 /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. 129 /// 130 /// In the BBtoRegionNode map of the parent of this node, BB will always map 131 /// to this node no matter which kind of node this one is. 132 /// 133 /// The node can hold either a Region or a BasicBlock. 134 /// Use one bit to save, if this RegionNode is a subregion or BasicBlock 135 /// RegionNode. 136 PointerIntPair<BlockT *, 1, bool> entry; 137 138 /// @brief The parent Region of this RegionNode. 139 /// @see getParent() 140 RegionT *parent; 141 142 protected: 143 /// @brief Create a RegionNode. 144 /// 145 /// @param Parent The parent of this RegionNode. 146 /// @param Entry The entry BasicBlock of the RegionNode. If this 147 /// RegionNode represents a BasicBlock, this is the 148 /// BasicBlock itself. If it represents a subregion, this 149 /// is the entry BasicBlock of the subregion. 150 /// @param isSubRegion If this RegionNode represents a SubRegion. 151 inline RegionNodeBase(RegionT *Parent, BlockT *Entry, 152 bool isSubRegion = false) 153 : entry(Entry, isSubRegion), parent(Parent) {} 154 155 public: 156 RegionNodeBase(const RegionNodeBase &) = delete; 157 RegionNodeBase &operator=(const RegionNodeBase &) = delete; 158 159 /// @brief Get the parent Region of this RegionNode. 160 /// 161 /// The parent Region is the Region this RegionNode belongs to. If for 162 /// example a BasicBlock is element of two Regions, there exist two 163 /// RegionNodes for this BasicBlock. Each with the getParent() function 164 /// pointing to the Region this RegionNode belongs to. 165 /// 166 /// @return Get the parent Region of this RegionNode. 167 inline RegionT *getParent() const { return parent; } 168 169 /// @brief Get the entry BasicBlock of this RegionNode. 170 /// 171 /// If this RegionNode represents a BasicBlock this is just the BasicBlock 172 /// itself, otherwise we return the entry BasicBlock of the Subregion 173 /// 174 /// @return The entry BasicBlock of this RegionNode. 175 inline BlockT *getEntry() const { return entry.getPointer(); } 176 177 /// @brief Get the content of this RegionNode. 178 /// 179 /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() 180 /// check the type of the content with the isSubRegion() function call. 181 /// 182 /// @return The content of this RegionNode. 183 template <class T> inline T *getNodeAs() const; 184 185 /// @brief Is this RegionNode a subregion? 186 /// 187 /// @return True if it contains a subregion. False if it contains a 188 /// BasicBlock. 189 inline bool isSubRegion() const { return entry.getInt(); } 190 }; 191 192 //===----------------------------------------------------------------------===// 193 /// @brief A single entry single exit Region. 194 /// 195 /// A Region is a connected subgraph of a control flow graph that has exactly 196 /// two connections to the remaining graph. It can be used to analyze or 197 /// optimize parts of the control flow graph. 198 /// 199 /// A <em> simple Region </em> is connected to the remaining graph by just two 200 /// edges. One edge entering the Region and another one leaving the Region. 201 /// 202 /// An <em> extended Region </em> (or just Region) is a subgraph that can be 203 /// transform into a simple Region. The transformation is done by adding 204 /// BasicBlocks that merge several entry or exit edges so that after the merge 205 /// just one entry and one exit edge exists. 206 /// 207 /// The \e Entry of a Region is the first BasicBlock that is passed after 208 /// entering the Region. It is an element of the Region. The entry BasicBlock 209 /// dominates all BasicBlocks in the Region. 210 /// 211 /// The \e Exit of a Region is the first BasicBlock that is passed after 212 /// leaving the Region. It is not an element of the Region. The exit BasicBlock, 213 /// postdominates all BasicBlocks in the Region. 214 /// 215 /// A <em> canonical Region </em> cannot be constructed by combining smaller 216 /// Regions. 217 /// 218 /// Region A is the \e parent of Region B, if B is completely contained in A. 219 /// 220 /// Two canonical Regions either do not intersect at all or one is 221 /// the parent of the other. 222 /// 223 /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of 224 /// Regions in the control flow graph and E is the \e parent relation of these 225 /// Regions. 226 /// 227 /// Example: 228 /// 229 /// \verbatim 230 /// A simple control flow graph, that contains two regions. 231 /// 232 /// 1 233 /// / | 234 /// 2 | 235 /// / \ 3 236 /// 4 5 | 237 /// | | | 238 /// 6 7 8 239 /// \ | / 240 /// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} 241 /// 9 Region B: 2 -> 9 {2,4,5,6,7} 242 /// \endverbatim 243 /// 244 /// You can obtain more examples by either calling 245 /// 246 /// <tt> "opt -regions -analyze anyprogram.ll" </tt> 247 /// or 248 /// <tt> "opt -view-regions-only anyprogram.ll" </tt> 249 /// 250 /// on any LLVM file you are interested in. 251 /// 252 /// The first call returns a textual representation of the program structure 253 /// tree, the second one creates a graphical representation using graphviz. 254 template <class Tr> 255 class RegionBase : public RegionNodeBase<Tr> { 256 friend class RegionInfoBase<Tr>; 257 258 using FuncT = typename Tr::FuncT; 259 using BlockT = typename Tr::BlockT; 260 using RegionInfoT = typename Tr::RegionInfoT; 261 using RegionT = typename Tr::RegionT; 262 using RegionNodeT = typename Tr::RegionNodeT; 263 using DomTreeT = typename Tr::DomTreeT; 264 using LoopT = typename Tr::LoopT; 265 using LoopInfoT = typename Tr::LoopInfoT; 266 using InstT = typename Tr::InstT; 267 268 using BlockTraits = GraphTraits<BlockT *>; 269 using InvBlockTraits = GraphTraits<Inverse<BlockT *>>; 270 using SuccIterTy = typename BlockTraits::ChildIteratorType; 271 using PredIterTy = typename InvBlockTraits::ChildIteratorType; 272 273 // Information necessary to manage this Region. 274 RegionInfoT *RI; 275 DomTreeT *DT; 276 277 // The exit BasicBlock of this region. 278 // (The entry BasicBlock is part of RegionNode) 279 BlockT *exit; 280 281 using RegionSet = std::vector<std::unique_ptr<RegionT>>; 282 283 // The subregions of this region. 284 RegionSet children; 285 286 using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>; 287 288 // Save the BasicBlock RegionNodes that are element of this Region. 289 mutable BBNodeMapT BBNodeMap; 290 291 /// Check if a BB is in this Region. This check also works 292 /// if the region is incorrectly built. (EXPENSIVE!) 293 void verifyBBInRegion(BlockT *BB) const; 294 295 /// Walk over all the BBs of the region starting from BB and 296 /// verify that all reachable basic blocks are elements of the region. 297 /// (EXPENSIVE!) 298 void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const; 299 300 /// Verify if the region and its children are valid regions (EXPENSIVE!) 301 void verifyRegionNest() const; 302 303 public: 304 /// @brief Create a new region. 305 /// 306 /// @param Entry The entry basic block of the region. 307 /// @param Exit The exit basic block of the region. 308 /// @param RI The region info object that is managing this region. 309 /// @param DT The dominator tree of the current function. 310 /// @param Parent The surrounding region or NULL if this is a top level 311 /// region. 312 RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, 313 RegionT *Parent = nullptr); 314 315 RegionBase(const RegionBase &) = delete; 316 RegionBase &operator=(const RegionBase &) = delete; 317 318 /// Delete the Region and all its subregions. 319 ~RegionBase(); 320 321 /// @brief Get the entry BasicBlock of the Region. 322 /// @return The entry BasicBlock of the region. 323 BlockT *getEntry() const { 324 return RegionNodeBase<Tr>::getEntry(); 325 } 326 327 /// @brief Replace the entry basic block of the region with the new basic 328 /// block. 329 /// 330 /// @param BB The new entry basic block of the region. 331 void replaceEntry(BlockT *BB); 332 333 /// @brief Replace the exit basic block of the region with the new basic 334 /// block. 335 /// 336 /// @param BB The new exit basic block of the region. 337 void replaceExit(BlockT *BB); 338 339 /// @brief Recursively replace the entry basic block of the region. 340 /// 341 /// This function replaces the entry basic block with a new basic block. It 342 /// also updates all child regions that have the same entry basic block as 343 /// this region. 344 /// 345 /// @param NewEntry The new entry basic block. 346 void replaceEntryRecursive(BlockT *NewEntry); 347 348 /// @brief Recursively replace the exit basic block of the region. 349 /// 350 /// This function replaces the exit basic block with a new basic block. It 351 /// also updates all child regions that have the same exit basic block as 352 /// this region. 353 /// 354 /// @param NewExit The new exit basic block. 355 void replaceExitRecursive(BlockT *NewExit); 356 357 /// @brief Get the exit BasicBlock of the Region. 358 /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel 359 /// Region. 360 BlockT *getExit() const { return exit; } 361 362 /// @brief Get the parent of the Region. 363 /// @return The parent of the Region or NULL if this is a top level 364 /// Region. 365 RegionT *getParent() const { 366 return RegionNodeBase<Tr>::getParent(); 367 } 368 369 /// @brief Get the RegionNode representing the current Region. 370 /// @return The RegionNode representing the current Region. 371 RegionNodeT *getNode() const { 372 return const_cast<RegionNodeT *>( 373 reinterpret_cast<const RegionNodeT *>(this)); 374 } 375 376 /// @brief Get the nesting level of this Region. 377 /// 378 /// An toplevel Region has depth 0. 379 /// 380 /// @return The depth of the region. 381 unsigned getDepth() const; 382 383 /// @brief Check if a Region is the TopLevel region. 384 /// 385 /// The toplevel region represents the whole function. 386 bool isTopLevelRegion() const { return exit == nullptr; } 387 388 /// @brief Return a new (non-canonical) region, that is obtained by joining 389 /// this region with its predecessors. 390 /// 391 /// @return A region also starting at getEntry(), but reaching to the next 392 /// basic block that forms with getEntry() a (non-canonical) region. 393 /// NULL if such a basic block does not exist. 394 RegionT *getExpandedRegion() const; 395 396 /// @brief Return the first block of this region's single entry edge, 397 /// if existing. 398 /// 399 /// @return The BasicBlock starting this region's single entry edge, 400 /// else NULL. 401 BlockT *getEnteringBlock() const; 402 403 /// @brief Return the first block of this region's single exit edge, 404 /// if existing. 405 /// 406 /// @return The BasicBlock starting this region's single exit edge, 407 /// else NULL. 408 BlockT *getExitingBlock() const; 409 410 /// @brief Collect all blocks of this region's single exit edge, if existing. 411 /// 412 /// @return True if this region contains all the predecessors of the exit. 413 bool getExitingBlocks(SmallVectorImpl<BlockT *> &Exitings) const; 414 415 /// @brief Is this a simple region? 416 /// 417 /// A region is simple if it has exactly one exit and one entry edge. 418 /// 419 /// @return True if the Region is simple. 420 bool isSimple() const; 421 422 /// @brief Returns the name of the Region. 423 /// @return The Name of the Region. 424 std::string getNameStr() const; 425 426 /// @brief Return the RegionInfo object, that belongs to this Region. 427 RegionInfoT *getRegionInfo() const { return RI; } 428 429 /// PrintStyle - Print region in difference ways. 430 enum PrintStyle { PrintNone, PrintBB, PrintRN }; 431 432 /// @brief Print the region. 433 /// 434 /// @param OS The output stream the Region is printed to. 435 /// @param printTree Print also the tree of subregions. 436 /// @param level The indentation level used for printing. 437 void print(raw_ostream &OS, bool printTree = true, unsigned level = 0, 438 PrintStyle Style = PrintNone) const; 439 440 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 441 /// @brief Print the region to stderr. 442 void dump() const; 443 #endif 444 445 /// @brief Check if the region contains a BasicBlock. 446 /// 447 /// @param BB The BasicBlock that might be contained in this Region. 448 /// @return True if the block is contained in the region otherwise false. 449 bool contains(const BlockT *BB) const; 450 451 /// @brief Check if the region contains another region. 452 /// 453 /// @param SubRegion The region that might be contained in this Region. 454 /// @return True if SubRegion is contained in the region otherwise false. 455 bool contains(const RegionT *SubRegion) const { 456 // Toplevel Region. 457 if (!getExit()) 458 return true; 459 460 return contains(SubRegion->getEntry()) && 461 (contains(SubRegion->getExit()) || 462 SubRegion->getExit() == getExit()); 463 } 464 465 /// @brief Check if the region contains an Instruction. 466 /// 467 /// @param Inst The Instruction that might be contained in this region. 468 /// @return True if the Instruction is contained in the region otherwise 469 /// false. 470 bool contains(const InstT *Inst) const { return contains(Inst->getParent()); } 471 472 /// @brief Check if the region contains a loop. 473 /// 474 /// @param L The loop that might be contained in this region. 475 /// @return True if the loop is contained in the region otherwise false. 476 /// In case a NULL pointer is passed to this function the result 477 /// is false, except for the region that describes the whole function. 478 /// In that case true is returned. 479 bool contains(const LoopT *L) const; 480 481 /// @brief Get the outermost loop in the region that contains a loop. 482 /// 483 /// Find for a Loop L the outermost loop OuterL that is a parent loop of L 484 /// and is itself contained in the region. 485 /// 486 /// @param L The loop the lookup is started. 487 /// @return The outermost loop in the region, NULL if such a loop does not 488 /// exist or if the region describes the whole function. 489 LoopT *outermostLoopInRegion(LoopT *L) const; 490 491 /// @brief Get the outermost loop in the region that contains a basic block. 492 /// 493 /// Find for a basic block BB the outermost loop L that contains BB and is 494 /// itself contained in the region. 495 /// 496 /// @param LI A pointer to a LoopInfo analysis. 497 /// @param BB The basic block surrounded by the loop. 498 /// @return The outermost loop in the region, NULL if such a loop does not 499 /// exist or if the region describes the whole function. 500 LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const; 501 502 /// @brief Get the subregion that starts at a BasicBlock 503 /// 504 /// @param BB The BasicBlock the subregion should start. 505 /// @return The Subregion if available, otherwise NULL. 506 RegionT *getSubRegionNode(BlockT *BB) const; 507 508 /// @brief Get the RegionNode for a BasicBlock 509 /// 510 /// @param BB The BasicBlock at which the RegionNode should start. 511 /// @return If available, the RegionNode that represents the subregion 512 /// starting at BB. If no subregion starts at BB, the RegionNode 513 /// representing BB. 514 RegionNodeT *getNode(BlockT *BB) const; 515 516 /// @brief Get the BasicBlock RegionNode for a BasicBlock 517 /// 518 /// @param BB The BasicBlock for which the RegionNode is requested. 519 /// @return The RegionNode representing the BB. 520 RegionNodeT *getBBNode(BlockT *BB) const; 521 522 /// @brief Add a new subregion to this Region. 523 /// 524 /// @param SubRegion The new subregion that will be added. 525 /// @param moveChildren Move the children of this region, that are also 526 /// contained in SubRegion into SubRegion. 527 void addSubRegion(RegionT *SubRegion, bool moveChildren = false); 528 529 /// @brief Remove a subregion from this Region. 530 /// 531 /// The subregion is not deleted, as it will probably be inserted into another 532 /// region. 533 /// @param SubRegion The SubRegion that will be removed. 534 RegionT *removeSubRegion(RegionT *SubRegion); 535 536 /// @brief Move all direct child nodes of this Region to another Region. 537 /// 538 /// @param To The Region the child nodes will be transferred to. 539 void transferChildrenTo(RegionT *To); 540 541 /// @brief Verify if the region is a correct region. 542 /// 543 /// Check if this is a correctly build Region. This is an expensive check, as 544 /// the complete CFG of the Region will be walked. 545 void verifyRegion() const; 546 547 /// @brief Clear the cache for BB RegionNodes. 548 /// 549 /// After calling this function the BasicBlock RegionNodes will be stored at 550 /// different memory locations. RegionNodes obtained before this function is 551 /// called are therefore not comparable to RegionNodes abtained afterwords. 552 void clearNodeCache(); 553 554 /// @name Subregion Iterators 555 /// 556 /// These iterators iterator over all subregions of this Region. 557 //@{ 558 using iterator = typename RegionSet::iterator; 559 using const_iterator = typename RegionSet::const_iterator; 560 561 iterator begin() { return children.begin(); } 562 iterator end() { return children.end(); } 563 564 const_iterator begin() const { return children.begin(); } 565 const_iterator end() const { return children.end(); } 566 //@} 567 568 /// @name BasicBlock Iterators 569 /// 570 /// These iterators iterate over all BasicBlocks that are contained in this 571 /// Region. The iterator also iterates over BasicBlocks that are elements of 572 /// a subregion of this Region. It is therefore called a flat iterator. 573 //@{ 574 template <bool IsConst> 575 class block_iterator_wrapper 576 : public df_iterator< 577 typename std::conditional<IsConst, const BlockT, BlockT>::type *> { 578 using super = 579 df_iterator< 580 typename std::conditional<IsConst, const BlockT, BlockT>::type *>; 581 582 public: 583 using Self = block_iterator_wrapper<IsConst>; 584 using value_type = typename super::value_type; 585 586 // Construct the begin iterator. 587 block_iterator_wrapper(value_type Entry, value_type Exit) 588 : super(df_begin(Entry)) { 589 // Mark the exit of the region as visited, so that the children of the 590 // exit and the exit itself, i.e. the block outside the region will never 591 // be visited. 592 super::Visited.insert(Exit); 593 } 594 595 // Construct the end iterator. 596 block_iterator_wrapper() : super(df_end<value_type>((BlockT *)nullptr)) {} 597 598 /*implicit*/ block_iterator_wrapper(super I) : super(I) {} 599 600 // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. 601 // This was introduced for backwards compatibility, but should 602 // be removed as soon as all users are fixed. 603 BlockT *operator*() const { 604 return const_cast<BlockT *>(super::operator*()); 605 } 606 }; 607 608 using block_iterator = block_iterator_wrapper<false>; 609 using const_block_iterator = block_iterator_wrapper<true>; 610 611 block_iterator block_begin() { return block_iterator(getEntry(), getExit()); } 612 613 block_iterator block_end() { return block_iterator(); } 614 615 const_block_iterator block_begin() const { 616 return const_block_iterator(getEntry(), getExit()); 617 } 618 const_block_iterator block_end() const { return const_block_iterator(); } 619 620 using block_range = iterator_range<block_iterator>; 621 using const_block_range = iterator_range<const_block_iterator>; 622 623 /// @brief Returns a range view of the basic blocks in the region. 624 inline block_range blocks() { 625 return block_range(block_begin(), block_end()); 626 } 627 628 /// @brief Returns a range view of the basic blocks in the region. 629 /// 630 /// This is the 'const' version of the range view. 631 inline const_block_range blocks() const { 632 return const_block_range(block_begin(), block_end()); 633 } 634 //@} 635 636 /// @name Element Iterators 637 /// 638 /// These iterators iterate over all BasicBlock and subregion RegionNodes that 639 /// are direct children of this Region. It does not iterate over any 640 /// RegionNodes that are also element of a subregion of this Region. 641 //@{ 642 using element_iterator = 643 df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false, 644 GraphTraits<RegionNodeT *>>; 645 646 using const_element_iterator = 647 df_iterator<const RegionNodeT *, 648 df_iterator_default_set<const RegionNodeT *>, false, 649 GraphTraits<const RegionNodeT *>>; 650 651 element_iterator element_begin(); 652 element_iterator element_end(); 653 iterator_range<element_iterator> elements() { 654 return make_range(element_begin(), element_end()); 655 } 656 657 const_element_iterator element_begin() const; 658 const_element_iterator element_end() const; 659 iterator_range<const_element_iterator> elements() const { 660 return make_range(element_begin(), element_end()); 661 } 662 //@} 663 }; 664 665 /// Print a RegionNode. 666 template <class Tr> 667 inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node); 668 669 //===----------------------------------------------------------------------===// 670 /// @brief Analysis that detects all canonical Regions. 671 /// 672 /// The RegionInfo pass detects all canonical regions in a function. The Regions 673 /// are connected using the parent relation. This builds a Program Structure 674 /// Tree. 675 template <class Tr> 676 class RegionInfoBase { 677 friend class RegionInfo; 678 friend class MachineRegionInfo; 679 680 using BlockT = typename Tr::BlockT; 681 using FuncT = typename Tr::FuncT; 682 using RegionT = typename Tr::RegionT; 683 using RegionInfoT = typename Tr::RegionInfoT; 684 using DomTreeT = typename Tr::DomTreeT; 685 using DomTreeNodeT = typename Tr::DomTreeNodeT; 686 using PostDomTreeT = typename Tr::PostDomTreeT; 687 using DomFrontierT = typename Tr::DomFrontierT; 688 using BlockTraits = GraphTraits<BlockT *>; 689 using InvBlockTraits = GraphTraits<Inverse<BlockT *>>; 690 using SuccIterTy = typename BlockTraits::ChildIteratorType; 691 using PredIterTy = typename InvBlockTraits::ChildIteratorType; 692 693 using BBtoBBMap = DenseMap<BlockT *, BlockT *>; 694 using BBtoRegionMap = DenseMap<BlockT *, RegionT *>; 695 696 RegionInfoBase(); 697 698 RegionInfoBase(RegionInfoBase &&Arg) 699 : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)), 700 TopLevelRegion(std::move(Arg.TopLevelRegion)), 701 BBtoRegion(std::move(Arg.BBtoRegion)) { 702 Arg.wipe(); 703 } 704 705 RegionInfoBase &operator=(RegionInfoBase &&RHS) { 706 DT = std::move(RHS.DT); 707 PDT = std::move(RHS.PDT); 708 DF = std::move(RHS.DF); 709 TopLevelRegion = std::move(RHS.TopLevelRegion); 710 BBtoRegion = std::move(RHS.BBtoRegion); 711 RHS.wipe(); 712 return *this; 713 } 714 715 virtual ~RegionInfoBase(); 716 717 DomTreeT *DT; 718 PostDomTreeT *PDT; 719 DomFrontierT *DF; 720 721 /// The top level region. 722 RegionT *TopLevelRegion = nullptr; 723 724 /// Map every BB to the smallest region, that contains BB. 725 BBtoRegionMap BBtoRegion; 726 727 protected: 728 /// \brief Update refences to a RegionInfoT held by the RegionT managed here 729 /// 730 /// This is a post-move helper. Regions hold references to the owning 731 /// RegionInfo object. After a move these need to be fixed. 732 template<typename TheRegionT> 733 void updateRegionTree(RegionInfoT &RI, TheRegionT *R) { 734 if (!R) 735 return; 736 R->RI = &RI; 737 for (auto &SubR : *R) 738 updateRegionTree(RI, SubR.get()); 739 } 740 741 private: 742 /// \brief Wipe this region tree's state without releasing any resources. 743 /// 744 /// This is essentially a post-move helper only. It leaves the object in an 745 /// assignable and destroyable state, but otherwise invalid. 746 void wipe() { 747 DT = nullptr; 748 PDT = nullptr; 749 DF = nullptr; 750 TopLevelRegion = nullptr; 751 BBtoRegion.clear(); 752 } 753 754 // Check whether the entries of BBtoRegion for the BBs of region 755 // SR are correct. Triggers an assertion if not. Calls itself recursively for 756 // subregions. 757 void verifyBBMap(const RegionT *SR) const; 758 759 // Returns true if BB is in the dominance frontier of 760 // entry, because it was inherited from exit. In the other case there is an 761 // edge going from entry to BB without passing exit. 762 bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const; 763 764 // Check if entry and exit surround a valid region, based on 765 // dominance tree and dominance frontier. 766 bool isRegion(BlockT *entry, BlockT *exit) const; 767 768 // Saves a shortcut pointing from entry to exit. 769 // This function may extend this shortcut if possible. 770 void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const; 771 772 // Returns the next BB that postdominates N, while skipping 773 // all post dominators that cannot finish a canonical region. 774 DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const; 775 776 // A region is trivial, if it contains only one BB. 777 bool isTrivialRegion(BlockT *entry, BlockT *exit) const; 778 779 // Creates a single entry single exit region. 780 RegionT *createRegion(BlockT *entry, BlockT *exit); 781 782 // Detect all regions starting with bb 'entry'. 783 void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut); 784 785 // Detects regions in F. 786 void scanForRegions(FuncT &F, BBtoBBMap *ShortCut); 787 788 // Get the top most parent with the same entry block. 789 RegionT *getTopMostParent(RegionT *region); 790 791 // Build the region hierarchy after all region detected. 792 void buildRegionsTree(DomTreeNodeT *N, RegionT *region); 793 794 // Update statistic about created regions. 795 virtual void updateStatistics(RegionT *R) = 0; 796 797 // Detect all regions in function and build the region tree. 798 void calculate(FuncT &F); 799 800 public: 801 RegionInfoBase(const RegionInfoBase &) = delete; 802 RegionInfoBase &operator=(const RegionInfoBase &) = delete; 803 804 static bool VerifyRegionInfo; 805 static typename RegionT::PrintStyle printStyle; 806 807 void print(raw_ostream &OS) const; 808 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 809 void dump() const; 810 #endif 811 812 void releaseMemory(); 813 814 /// @brief Get the smallest region that contains a BasicBlock. 815 /// 816 /// @param BB The basic block. 817 /// @return The smallest region, that contains BB or NULL, if there is no 818 /// region containing BB. 819 RegionT *getRegionFor(BlockT *BB) const; 820 821 /// @brief Set the smallest region that surrounds a basic block. 822 /// 823 /// @param BB The basic block surrounded by a region. 824 /// @param R The smallest region that surrounds BB. 825 void setRegionFor(BlockT *BB, RegionT *R); 826 827 /// @brief A shortcut for getRegionFor(). 828 /// 829 /// @param BB The basic block. 830 /// @return The smallest region, that contains BB or NULL, if there is no 831 /// region containing BB. 832 RegionT *operator[](BlockT *BB) const; 833 834 /// @brief Return the exit of the maximal refined region, that starts at a 835 /// BasicBlock. 836 /// 837 /// @param BB The BasicBlock the refined region starts. 838 BlockT *getMaxRegionExit(BlockT *BB) const; 839 840 /// @brief Find the smallest region that contains two regions. 841 /// 842 /// @param A The first region. 843 /// @param B The second region. 844 /// @return The smallest region containing A and B. 845 RegionT *getCommonRegion(RegionT *A, RegionT *B) const; 846 847 /// @brief Find the smallest region that contains two basic blocks. 848 /// 849 /// @param A The first basic block. 850 /// @param B The second basic block. 851 /// @return The smallest region that contains A and B. 852 RegionT *getCommonRegion(BlockT *A, BlockT *B) const { 853 return getCommonRegion(getRegionFor(A), getRegionFor(B)); 854 } 855 856 /// @brief Find the smallest region that contains a set of regions. 857 /// 858 /// @param Regions A vector of regions. 859 /// @return The smallest region that contains all regions in Regions. 860 RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const; 861 862 /// @brief Find the smallest region that contains a set of basic blocks. 863 /// 864 /// @param BBs A vector of basic blocks. 865 /// @return The smallest region that contains all basic blocks in BBS. 866 RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const; 867 868 RegionT *getTopLevelRegion() const { return TopLevelRegion; } 869 870 /// @brief Clear the Node Cache for all Regions. 871 /// 872 /// @see Region::clearNodeCache() 873 void clearNodeCache() { 874 if (TopLevelRegion) 875 TopLevelRegion->clearNodeCache(); 876 } 877 878 void verifyAnalysis() const; 879 }; 880 881 class Region; 882 883 class RegionNode : public RegionNodeBase<RegionTraits<Function>> { 884 public: 885 inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false) 886 : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {} 887 888 bool operator==(const Region &RN) const { 889 return this == reinterpret_cast<const RegionNode *>(&RN); 890 } 891 }; 892 893 class Region : public RegionBase<RegionTraits<Function>> { 894 public: 895 Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, 896 Region *Parent = nullptr); 897 ~Region(); 898 899 bool operator==(const RegionNode &RN) const { 900 return &RN == reinterpret_cast<const RegionNode *>(this); 901 } 902 }; 903 904 class RegionInfo : public RegionInfoBase<RegionTraits<Function>> { 905 public: 906 using Base = RegionInfoBase<RegionTraits<Function>>; 907 908 explicit RegionInfo(); 909 910 RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) { 911 updateRegionTree(*this, TopLevelRegion); 912 } 913 914 RegionInfo &operator=(RegionInfo &&RHS) { 915 Base::operator=(std::move(static_cast<Base &>(RHS))); 916 updateRegionTree(*this, TopLevelRegion); 917 return *this; 918 } 919 920 ~RegionInfo() override; 921 922 /// Handle invalidation explicitly. 923 bool invalidate(Function &F, const PreservedAnalyses &PA, 924 FunctionAnalysisManager::Invalidator &); 925 926 // updateStatistics - Update statistic about created regions. 927 void updateStatistics(Region *R) final; 928 929 void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, 930 DominanceFrontier *DF); 931 932 #ifndef NDEBUG 933 /// @brief Opens a viewer to show the GraphViz visualization of the regions. 934 /// 935 /// Useful during debugging as an alternative to dump(). 936 void view(); 937 938 /// @brief Opens a viewer to show the GraphViz visualization of this region 939 /// without instructions in the BasicBlocks. 940 /// 941 /// Useful during debugging as an alternative to dump(). 942 void viewOnly(); 943 #endif 944 }; 945 946 class RegionInfoPass : public FunctionPass { 947 RegionInfo RI; 948 949 public: 950 static char ID; 951 952 explicit RegionInfoPass(); 953 ~RegionInfoPass() override; 954 955 RegionInfo &getRegionInfo() { return RI; } 956 957 const RegionInfo &getRegionInfo() const { return RI; } 958 959 /// @name FunctionPass interface 960 //@{ 961 bool runOnFunction(Function &F) override; 962 void releaseMemory() override; 963 void verifyAnalysis() const override; 964 void getAnalysisUsage(AnalysisUsage &AU) const override; 965 void print(raw_ostream &OS, const Module *) const override; 966 void dump() const; 967 //@} 968 }; 969 970 /// \brief Analysis pass that exposes the \c RegionInfo for a function. 971 class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> { 972 friend AnalysisInfoMixin<RegionInfoAnalysis>; 973 974 static AnalysisKey Key; 975 976 public: 977 using Result = RegionInfo; 978 979 RegionInfo run(Function &F, FunctionAnalysisManager &AM); 980 }; 981 982 /// \brief Printer pass for the \c RegionInfo. 983 class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> { 984 raw_ostream &OS; 985 986 public: 987 explicit RegionInfoPrinterPass(raw_ostream &OS); 988 989 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 990 }; 991 992 /// \brief Verifier pass for the \c RegionInfo. 993 struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> { 994 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 995 }; 996 997 template <> 998 template <> 999 inline BasicBlock * 1000 RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const { 1001 assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); 1002 return getEntry(); 1003 } 1004 1005 template <> 1006 template <> 1007 inline Region * 1008 RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const { 1009 assert(isSubRegion() && "This is not a subregion RegionNode!"); 1010 auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this); 1011 return reinterpret_cast<Region *>(Unconst); 1012 } 1013 1014 template <class Tr> 1015 inline raw_ostream &operator<<(raw_ostream &OS, 1016 const RegionNodeBase<Tr> &Node) { 1017 using BlockT = typename Tr::BlockT; 1018 using RegionT = typename Tr::RegionT; 1019 1020 if (Node.isSubRegion()) 1021 return OS << Node.template getNodeAs<RegionT>()->getNameStr(); 1022 else 1023 return OS << Node.template getNodeAs<BlockT>()->getName(); 1024 } 1025 1026 extern template class RegionBase<RegionTraits<Function>>; 1027 extern template class RegionNodeBase<RegionTraits<Function>>; 1028 extern template class RegionInfoBase<RegionTraits<Function>>; 1029 1030 } // end namespace llvm 1031 1032 #endif // LLVM_ANALYSIS_REGIONINFO_H 1033