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