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