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