1212793Sdim//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// 10212793Sdim// Calculate a program structure tree built out of single entry single exit 11212793Sdim// regions. 12212793Sdim// The basic ideas are taken from "The Program Structure Tree - Richard Johnson, 13212793Sdim// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The 14212793Sdim// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana 15212793Sdim// Koehler - 2009". 16212793Sdim// The algorithm to calculate these data structures however is completely 17212793Sdim// different, as it takes advantage of existing information already available 18212793Sdim// in (Post)dominace tree and dominance frontier passes. This leads to a simpler 19212793Sdim// and in practice hopefully better performing algorithm. The runtime of the 20212793Sdim// algorithms described in the papers above are both linear in graph size, 21212793Sdim// O(V+E), whereas this algorithm is not, as the dominance frontier information 22212793Sdim// itself is not, but in practice runtime seems to be in the order of magnitude 23212793Sdim// of dominance tree calculation. 24212793Sdim// 25212793Sdim//===----------------------------------------------------------------------===// 26212793Sdim 27249423Sdim#ifndef LLVM_ANALYSIS_REGIONINFO_H 28249423Sdim#define LLVM_ANALYSIS_REGIONINFO_H 29212793Sdim 30212793Sdim#include "llvm/ADT/PointerIntPair.h" 31221345Sdim#include "llvm/Analysis/DominanceFrontier.h" 32212793Sdim#include "llvm/Analysis/PostDominators.h" 33212793Sdim#include "llvm/Support/Allocator.h" 34221345Sdim#include <map> 35212793Sdim 36212793Sdimnamespace llvm { 37212793Sdim 38212793Sdimclass Region; 39212793Sdimclass RegionInfo; 40212793Sdimclass raw_ostream; 41212793Sdimclass Loop; 42212793Sdimclass LoopInfo; 43212793Sdim 44212793Sdim/// @brief Marker class to iterate over the elements of a Region in flat mode. 45212793Sdim/// 46212793Sdim/// The class is used to either iterate in Flat mode or by not using it to not 47212793Sdim/// iterate in Flat mode. During a Flat mode iteration all Regions are entered 48212793Sdim/// and the iteration returns every BasicBlock. If the Flat mode is not 49212793Sdim/// selected for SubRegions just one RegionNode containing the subregion is 50212793Sdim/// returned. 51212793Sdimtemplate <class GraphType> 52212793Sdimclass FlatIt {}; 53212793Sdim 54212793Sdim/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a 55212793Sdim/// Region. 56212793Sdimclass RegionNode { 57243830Sdim RegionNode(const RegionNode &) LLVM_DELETED_FUNCTION; 58243830Sdim const RegionNode &operator=(const RegionNode &) LLVM_DELETED_FUNCTION; 59212793Sdim 60218893Sdimprotected: 61212793Sdim /// This is the entry basic block that starts this region node. If this is a 62212793Sdim /// BasicBlock RegionNode, then entry is just the basic block, that this 63212793Sdim /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. 64212793Sdim /// 65212793Sdim /// In the BBtoRegionNode map of the parent of this node, BB will always map 66212793Sdim /// to this node no matter which kind of node this one is. 67212793Sdim /// 68212793Sdim /// The node can hold either a Region or a BasicBlock. 69212793Sdim /// Use one bit to save, if this RegionNode is a subregion or BasicBlock 70212793Sdim /// RegionNode. 71212793Sdim PointerIntPair<BasicBlock*, 1, bool> entry; 72212793Sdim 73212793Sdim /// @brief The parent Region of this RegionNode. 74212793Sdim /// @see getParent() 75212793Sdim Region* parent; 76212793Sdim 77212793Sdimpublic: 78212793Sdim /// @brief Create a RegionNode. 79212793Sdim /// 80212793Sdim /// @param Parent The parent of this RegionNode. 81212793Sdim /// @param Entry The entry BasicBlock of the RegionNode. If this 82212793Sdim /// RegionNode represents a BasicBlock, this is the 83212793Sdim /// BasicBlock itself. If it represents a subregion, this 84212793Sdim /// is the entry BasicBlock of the subregion. 85212793Sdim /// @param isSubRegion If this RegionNode represents a SubRegion. 86212793Sdim inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0) 87212793Sdim : entry(Entry, isSubRegion), parent(Parent) {} 88212793Sdim 89212793Sdim /// @brief Get the parent Region of this RegionNode. 90212793Sdim /// 91212793Sdim /// The parent Region is the Region this RegionNode belongs to. If for 92212793Sdim /// example a BasicBlock is element of two Regions, there exist two 93212793Sdim /// RegionNodes for this BasicBlock. Each with the getParent() function 94212793Sdim /// pointing to the Region this RegionNode belongs to. 95212793Sdim /// 96212793Sdim /// @return Get the parent Region of this RegionNode. 97212793Sdim inline Region* getParent() const { return parent; } 98212793Sdim 99212793Sdim /// @brief Get the entry BasicBlock of this RegionNode. 100212793Sdim /// 101212793Sdim /// If this RegionNode represents a BasicBlock this is just the BasicBlock 102212793Sdim /// itself, otherwise we return the entry BasicBlock of the Subregion 103212793Sdim /// 104212793Sdim /// @return The entry BasicBlock of this RegionNode. 105212793Sdim inline BasicBlock* getEntry() const { return entry.getPointer(); } 106212793Sdim 107212793Sdim /// @brief Get the content of this RegionNode. 108212793Sdim /// 109212793Sdim /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() 110212793Sdim /// check the type of the content with the isSubRegion() function call. 111212793Sdim /// 112212793Sdim /// @return The content of this RegionNode. 113212793Sdim template<class T> 114212793Sdim inline T* getNodeAs() const; 115212793Sdim 116212793Sdim /// @brief Is this RegionNode a subregion? 117212793Sdim /// 118212793Sdim /// @return True if it contains a subregion. False if it contains a 119212793Sdim /// BasicBlock. 120212793Sdim inline bool isSubRegion() const { 121212793Sdim return entry.getInt(); 122212793Sdim } 123212793Sdim}; 124212793Sdim 125212793Sdim/// Print a RegionNode. 126212793Sdiminline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node); 127212793Sdim 128212793Sdimtemplate<> 129212793Sdiminline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const { 130212793Sdim assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); 131212793Sdim return getEntry(); 132212793Sdim} 133212793Sdim 134212793Sdimtemplate<> 135212793Sdiminline Region* RegionNode::getNodeAs<Region>() const { 136212793Sdim assert(isSubRegion() && "This is not a subregion RegionNode!"); 137212793Sdim return reinterpret_cast<Region*>(const_cast<RegionNode*>(this)); 138212793Sdim} 139212793Sdim 140212793Sdim//===----------------------------------------------------------------------===// 141212793Sdim/// @brief A single entry single exit Region. 142212793Sdim/// 143212793Sdim/// A Region is a connected subgraph of a control flow graph that has exactly 144212793Sdim/// two connections to the remaining graph. It can be used to analyze or 145212793Sdim/// optimize parts of the control flow graph. 146212793Sdim/// 147221345Sdim/// A <em> simple Region </em> is connected to the remaining graph by just two 148212793Sdim/// edges. One edge entering the Region and another one leaving the Region. 149212793Sdim/// 150212793Sdim/// An <em> extended Region </em> (or just Region) is a subgraph that can be 151212793Sdim/// transform into a simple Region. The transformation is done by adding 152212793Sdim/// BasicBlocks that merge several entry or exit edges so that after the merge 153212793Sdim/// just one entry and one exit edge exists. 154212793Sdim/// 155212793Sdim/// The \e Entry of a Region is the first BasicBlock that is passed after 156212793Sdim/// entering the Region. It is an element of the Region. The entry BasicBlock 157212793Sdim/// dominates all BasicBlocks in the Region. 158212793Sdim/// 159212793Sdim/// The \e Exit of a Region is the first BasicBlock that is passed after 160212793Sdim/// leaving the Region. It is not an element of the Region. The exit BasicBlock, 161212793Sdim/// postdominates all BasicBlocks in the Region. 162212793Sdim/// 163212793Sdim/// A <em> canonical Region </em> cannot be constructed by combining smaller 164212793Sdim/// Regions. 165212793Sdim/// 166212793Sdim/// Region A is the \e parent of Region B, if B is completely contained in A. 167212793Sdim/// 168212793Sdim/// Two canonical Regions either do not intersect at all or one is 169212793Sdim/// the parent of the other. 170212793Sdim/// 171212793Sdim/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of 172212793Sdim/// Regions in the control flow graph and E is the \e parent relation of these 173212793Sdim/// Regions. 174212793Sdim/// 175212793Sdim/// Example: 176212793Sdim/// 177212793Sdim/// \verbatim 178212793Sdim/// A simple control flow graph, that contains two regions. 179212793Sdim/// 180212793Sdim/// 1 181212793Sdim/// / | 182212793Sdim/// 2 | 183212793Sdim/// / \ 3 184212793Sdim/// 4 5 | 185212793Sdim/// | | | 186212793Sdim/// 6 7 8 187212793Sdim/// \ | / 188212793Sdim/// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} 189212793Sdim/// 9 Region B: 2 -> 9 {2,4,5,6,7} 190212793Sdim/// \endverbatim 191212793Sdim/// 192212793Sdim/// You can obtain more examples by either calling 193212793Sdim/// 194212793Sdim/// <tt> "opt -regions -analyze anyprogram.ll" </tt> 195212793Sdim/// or 196212793Sdim/// <tt> "opt -view-regions-only anyprogram.ll" </tt> 197212793Sdim/// 198212793Sdim/// on any LLVM file you are interested in. 199212793Sdim/// 200212793Sdim/// The first call returns a textual representation of the program structure 201212793Sdim/// tree, the second one creates a graphical representation using graphviz. 202212793Sdimclass Region : public RegionNode { 203212793Sdim friend class RegionInfo; 204243830Sdim Region(const Region &) LLVM_DELETED_FUNCTION; 205243830Sdim const Region &operator=(const Region &) LLVM_DELETED_FUNCTION; 206212793Sdim 207212793Sdim // Information necessary to manage this Region. 208212793Sdim RegionInfo* RI; 209212793Sdim DominatorTree *DT; 210212793Sdim 211212793Sdim // The exit BasicBlock of this region. 212212793Sdim // (The entry BasicBlock is part of RegionNode) 213212793Sdim BasicBlock *exit; 214212793Sdim 215212793Sdim typedef std::vector<Region*> RegionSet; 216212793Sdim 217212793Sdim // The subregions of this region. 218212793Sdim RegionSet children; 219212793Sdim 220212793Sdim typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT; 221212793Sdim 222212793Sdim // Save the BasicBlock RegionNodes that are element of this Region. 223212793Sdim mutable BBNodeMapT BBNodeMap; 224212793Sdim 225212793Sdim /// verifyBBInRegion - Check if a BB is in this Region. This check also works 226212793Sdim /// if the region is incorrectly built. (EXPENSIVE!) 227212793Sdim void verifyBBInRegion(BasicBlock* BB) const; 228212793Sdim 229212793Sdim /// verifyWalk - Walk over all the BBs of the region starting from BB and 230212793Sdim /// verify that all reachable basic blocks are elements of the region. 231212793Sdim /// (EXPENSIVE!) 232212793Sdim void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const; 233212793Sdim 234212793Sdim /// verifyRegionNest - Verify if the region and its children are valid 235212793Sdim /// regions (EXPENSIVE!) 236212793Sdim void verifyRegionNest() const; 237212793Sdim 238212793Sdimpublic: 239212793Sdim /// @brief Create a new region. 240212793Sdim /// 241212793Sdim /// @param Entry The entry basic block of the region. 242212793Sdim /// @param Exit The exit basic block of the region. 243212793Sdim /// @param RI The region info object that is managing this region. 244212793Sdim /// @param DT The dominator tree of the current function. 245212793Sdim /// @param Parent The surrounding region or NULL if this is a top level 246212793Sdim /// region. 247212793Sdim Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI, 248212793Sdim DominatorTree *DT, Region *Parent = 0); 249212793Sdim 250212793Sdim /// Delete the Region and all its subregions. 251212793Sdim ~Region(); 252212793Sdim 253212793Sdim /// @brief Get the entry BasicBlock of the Region. 254212793Sdim /// @return The entry BasicBlock of the region. 255212793Sdim BasicBlock *getEntry() const { return RegionNode::getEntry(); } 256212793Sdim 257218893Sdim /// @brief Replace the entry basic block of the region with the new basic 258218893Sdim /// block. 259218893Sdim /// 260218893Sdim /// @param BB The new entry basic block of the region. 261218893Sdim void replaceEntry(BasicBlock *BB); 262218893Sdim 263218893Sdim /// @brief Replace the exit basic block of the region with the new basic 264218893Sdim /// block. 265218893Sdim /// 266218893Sdim /// @param BB The new exit basic block of the region. 267218893Sdim void replaceExit(BasicBlock *BB); 268218893Sdim 269251662Sdim /// @brief Recursively replace the entry basic block of the region. 270251662Sdim /// 271251662Sdim /// This function replaces the entry basic block with a new basic block. It 272251662Sdim /// also updates all child regions that have the same entry basic block as 273251662Sdim /// this region. 274251662Sdim /// 275251662Sdim /// @param NewEntry The new entry basic block. 276251662Sdim void replaceEntryRecursive(BasicBlock *NewEntry); 277251662Sdim 278251662Sdim /// @brief Recursively replace the exit basic block of the region. 279251662Sdim /// 280251662Sdim /// This function replaces the exit basic block with a new basic block. It 281251662Sdim /// also updates all child regions that have the same exit basic block as 282251662Sdim /// this region. 283251662Sdim /// 284251662Sdim /// @param NewExit The new exit basic block. 285251662Sdim void replaceExitRecursive(BasicBlock *NewExit); 286251662Sdim 287212793Sdim /// @brief Get the exit BasicBlock of the Region. 288212793Sdim /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel 289212793Sdim /// Region. 290212793Sdim BasicBlock *getExit() const { return exit; } 291212793Sdim 292212793Sdim /// @brief Get the parent of the Region. 293212793Sdim /// @return The parent of the Region or NULL if this is a top level 294212793Sdim /// Region. 295212793Sdim Region *getParent() const { return RegionNode::getParent(); } 296212793Sdim 297212793Sdim /// @brief Get the RegionNode representing the current Region. 298212793Sdim /// @return The RegionNode representing the current Region. 299212793Sdim RegionNode* getNode() const { 300212793Sdim return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this)); 301212793Sdim } 302212793Sdim 303212793Sdim /// @brief Get the nesting level of this Region. 304212793Sdim /// 305212793Sdim /// An toplevel Region has depth 0. 306212793Sdim /// 307212793Sdim /// @return The depth of the region. 308212793Sdim unsigned getDepth() const; 309212793Sdim 310218893Sdim /// @brief Check if a Region is the TopLevel region. 311218893Sdim /// 312218893Sdim /// The toplevel region represents the whole function. 313218893Sdim bool isTopLevelRegion() const { return exit == NULL; } 314218893Sdim 315218893Sdim /// @brief Return a new (non canonical) region, that is obtained by joining 316218893Sdim /// this region with its predecessors. 317218893Sdim /// 318218893Sdim /// @return A region also starting at getEntry(), but reaching to the next 319218893Sdim /// basic block that forms with getEntry() a (non canonical) region. 320218893Sdim /// NULL if such a basic block does not exist. 321218893Sdim Region *getExpandedRegion() const; 322218893Sdim 323218893Sdim /// @brief Return the first block of this region's single entry edge, 324218893Sdim /// if existing. 325218893Sdim /// 326218893Sdim /// @return The BasicBlock starting this region's single entry edge, 327218893Sdim /// else NULL. 328218893Sdim BasicBlock *getEnteringBlock() const; 329218893Sdim 330218893Sdim /// @brief Return the first block of this region's single exit edge, 331218893Sdim /// if existing. 332218893Sdim /// 333218893Sdim /// @return The BasicBlock starting this region's single exit edge, 334218893Sdim /// else NULL. 335218893Sdim BasicBlock *getExitingBlock() const; 336218893Sdim 337212793Sdim /// @brief Is this a simple region? 338212793Sdim /// 339212793Sdim /// A region is simple if it has exactly one exit and one entry edge. 340212793Sdim /// 341212793Sdim /// @return True if the Region is simple. 342212793Sdim bool isSimple() const; 343212793Sdim 344212793Sdim /// @brief Returns the name of the Region. 345212793Sdim /// @return The Name of the Region. 346212793Sdim std::string getNameStr() const; 347212793Sdim 348212793Sdim /// @brief Return the RegionInfo object, that belongs to this Region. 349212793Sdim RegionInfo *getRegionInfo() const { 350212793Sdim return RI; 351212793Sdim } 352212793Sdim 353221345Sdim /// PrintStyle - Print region in difference ways. 354221345Sdim enum PrintStyle { PrintNone, PrintBB, PrintRN }; 355221345Sdim 356212793Sdim /// @brief Print the region. 357212793Sdim /// 358212793Sdim /// @param OS The output stream the Region is printed to. 359212793Sdim /// @param printTree Print also the tree of subregions. 360212793Sdim /// @param level The indentation level used for printing. 361221345Sdim void print(raw_ostream& OS, bool printTree = true, unsigned level = 0, 362221345Sdim enum PrintStyle Style = PrintNone) const; 363212793Sdim 364212793Sdim /// @brief Print the region to stderr. 365212793Sdim void dump() const; 366212793Sdim 367212793Sdim /// @brief Check if the region contains a BasicBlock. 368212793Sdim /// 369212793Sdim /// @param BB The BasicBlock that might be contained in this Region. 370212793Sdim /// @return True if the block is contained in the region otherwise false. 371212793Sdim bool contains(const BasicBlock *BB) const; 372212793Sdim 373212793Sdim /// @brief Check if the region contains another region. 374212793Sdim /// 375212793Sdim /// @param SubRegion The region that might be contained in this Region. 376212793Sdim /// @return True if SubRegion is contained in the region otherwise false. 377212793Sdim bool contains(const Region *SubRegion) const { 378212793Sdim // Toplevel Region. 379212793Sdim if (!getExit()) 380212793Sdim return true; 381212793Sdim 382212793Sdim return contains(SubRegion->getEntry()) 383212793Sdim && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit()); 384212793Sdim } 385212793Sdim 386212793Sdim /// @brief Check if the region contains an Instruction. 387212793Sdim /// 388212793Sdim /// @param Inst The Instruction that might be contained in this region. 389212793Sdim /// @return True if the Instruction is contained in the region otherwise false. 390212793Sdim bool contains(const Instruction *Inst) const { 391212793Sdim return contains(Inst->getParent()); 392212793Sdim } 393212793Sdim 394212793Sdim /// @brief Check if the region contains a loop. 395212793Sdim /// 396212793Sdim /// @param L The loop that might be contained in this region. 397212793Sdim /// @return True if the loop is contained in the region otherwise false. 398212793Sdim /// In case a NULL pointer is passed to this function the result 399212793Sdim /// is false, except for the region that describes the whole function. 400212793Sdim /// In that case true is returned. 401212793Sdim bool contains(const Loop *L) const; 402212793Sdim 403212793Sdim /// @brief Get the outermost loop in the region that contains a loop. 404212793Sdim /// 405212793Sdim /// Find for a Loop L the outermost loop OuterL that is a parent loop of L 406212793Sdim /// and is itself contained in the region. 407212793Sdim /// 408212793Sdim /// @param L The loop the lookup is started. 409212793Sdim /// @return The outermost loop in the region, NULL if such a loop does not 410212793Sdim /// exist or if the region describes the whole function. 411212793Sdim Loop *outermostLoopInRegion(Loop *L) const; 412212793Sdim 413212793Sdim /// @brief Get the outermost loop in the region that contains a basic block. 414212793Sdim /// 415212793Sdim /// Find for a basic block BB the outermost loop L that contains BB and is 416212793Sdim /// itself contained in the region. 417212793Sdim /// 418212793Sdim /// @param LI A pointer to a LoopInfo analysis. 419212793Sdim /// @param BB The basic block surrounded by the loop. 420212793Sdim /// @return The outermost loop in the region, NULL if such a loop does not 421212793Sdim /// exist or if the region describes the whole function. 422212793Sdim Loop *outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const; 423212793Sdim 424212793Sdim /// @brief Get the subregion that starts at a BasicBlock 425212793Sdim /// 426212793Sdim /// @param BB The BasicBlock the subregion should start. 427212793Sdim /// @return The Subregion if available, otherwise NULL. 428212793Sdim Region* getSubRegionNode(BasicBlock *BB) const; 429212793Sdim 430212793Sdim /// @brief Get the RegionNode for a BasicBlock 431212793Sdim /// 432212793Sdim /// @param BB The BasicBlock at which the RegionNode should start. 433212793Sdim /// @return If available, the RegionNode that represents the subregion 434212793Sdim /// starting at BB. If no subregion starts at BB, the RegionNode 435212793Sdim /// representing BB. 436212793Sdim RegionNode* getNode(BasicBlock *BB) const; 437212793Sdim 438212793Sdim /// @brief Get the BasicBlock RegionNode for a BasicBlock 439212793Sdim /// 440212793Sdim /// @param BB The BasicBlock for which the RegionNode is requested. 441212793Sdim /// @return The RegionNode representing the BB. 442212793Sdim RegionNode* getBBNode(BasicBlock *BB) const; 443212793Sdim 444212793Sdim /// @brief Add a new subregion to this Region. 445212793Sdim /// 446212793Sdim /// @param SubRegion The new subregion that will be added. 447218893Sdim /// @param moveChildren Move the children of this region, that are also 448218893Sdim /// contained in SubRegion into SubRegion. 449218893Sdim void addSubRegion(Region *SubRegion, bool moveChildren = false); 450212793Sdim 451212793Sdim /// @brief Remove a subregion from this Region. 452212793Sdim /// 453212793Sdim /// The subregion is not deleted, as it will probably be inserted into another 454212793Sdim /// region. 455212793Sdim /// @param SubRegion The SubRegion that will be removed. 456212793Sdim Region *removeSubRegion(Region *SubRegion); 457212793Sdim 458212793Sdim /// @brief Move all direct child nodes of this Region to another Region. 459212793Sdim /// 460221345Sdim /// @param To The Region the child nodes will be transferred to. 461212793Sdim void transferChildrenTo(Region *To); 462212793Sdim 463212793Sdim /// @brief Verify if the region is a correct region. 464212793Sdim /// 465212793Sdim /// Check if this is a correctly build Region. This is an expensive check, as 466212793Sdim /// the complete CFG of the Region will be walked. 467212793Sdim void verifyRegion() const; 468212793Sdim 469212793Sdim /// @brief Clear the cache for BB RegionNodes. 470212793Sdim /// 471212793Sdim /// After calling this function the BasicBlock RegionNodes will be stored at 472212793Sdim /// different memory locations. RegionNodes obtained before this function is 473212793Sdim /// called are therefore not comparable to RegionNodes abtained afterwords. 474212793Sdim void clearNodeCache(); 475212793Sdim 476212793Sdim /// @name Subregion Iterators 477212793Sdim /// 478212793Sdim /// These iterators iterator over all subregions of this Region. 479212793Sdim //@{ 480212793Sdim typedef RegionSet::iterator iterator; 481212793Sdim typedef RegionSet::const_iterator const_iterator; 482212793Sdim 483212793Sdim iterator begin() { return children.begin(); } 484212793Sdim iterator end() { return children.end(); } 485212793Sdim 486212793Sdim const_iterator begin() const { return children.begin(); } 487212793Sdim const_iterator end() const { return children.end(); } 488212793Sdim //@} 489212793Sdim 490239462Sdim /// @name BasicBlock Iterators 491239462Sdim /// 492239462Sdim /// These iterators iterate over all BasicBlocks that are contained in this 493239462Sdim /// Region. The iterator also iterates over BasicBlocks that are elements of 494239462Sdim /// a subregion of this Region. It is therefore called a flat iterator. 495239462Sdim //@{ 496239462Sdim template <bool IsConst> 497239462Sdim class block_iterator_wrapper 498239462Sdim : public df_iterator<typename conditional<IsConst, 499239462Sdim const BasicBlock, 500239462Sdim BasicBlock>::type*> { 501239462Sdim typedef df_iterator<typename conditional<IsConst, 502239462Sdim const BasicBlock, 503239462Sdim BasicBlock>::type*> 504239462Sdim super; 505239462Sdim public: 506239462Sdim typedef block_iterator_wrapper<IsConst> Self; 507239462Sdim typedef typename super::pointer pointer; 508239462Sdim 509239462Sdim // Construct the begin iterator. 510239462Sdim block_iterator_wrapper(pointer Entry, pointer Exit) : super(df_begin(Entry)) 511239462Sdim { 512239462Sdim // Mark the exit of the region as visited, so that the children of the 513239462Sdim // exit and the exit itself, i.e. the block outside the region will never 514239462Sdim // be visited. 515239462Sdim super::Visited.insert(Exit); 516239462Sdim } 517239462Sdim 518239462Sdim // Construct the end iterator. 519239462Sdim block_iterator_wrapper() : super(df_end<pointer>((BasicBlock *)0)) {} 520239462Sdim 521239462Sdim /*implicit*/ block_iterator_wrapper(super I) : super(I) {} 522239462Sdim 523239462Sdim // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. 524239462Sdim // This was introduced for backwards compatibility, but should 525239462Sdim // be removed as soon as all users are fixed. 526239462Sdim BasicBlock *operator*() const { 527239462Sdim return const_cast<BasicBlock*>(super::operator*()); 528239462Sdim } 529239462Sdim }; 530239462Sdim 531239462Sdim typedef block_iterator_wrapper<false> block_iterator; 532239462Sdim typedef block_iterator_wrapper<true> const_block_iterator; 533239462Sdim 534239462Sdim block_iterator block_begin() { 535239462Sdim return block_iterator(getEntry(), getExit()); 536239462Sdim } 537239462Sdim 538239462Sdim block_iterator block_end() { 539239462Sdim return block_iterator(); 540239462Sdim } 541239462Sdim 542239462Sdim const_block_iterator block_begin() const { 543239462Sdim return const_block_iterator(getEntry(), getExit()); 544239462Sdim } 545239462Sdim const_block_iterator block_end() const { 546239462Sdim return const_block_iterator(); 547239462Sdim } 548239462Sdim //@} 549239462Sdim 550212793Sdim /// @name Element Iterators 551212793Sdim /// 552212793Sdim /// These iterators iterate over all BasicBlock and subregion RegionNodes that 553212793Sdim /// are direct children of this Region. It does not iterate over any 554212793Sdim /// RegionNodes that are also element of a subregion of this Region. 555212793Sdim //@{ 556212793Sdim typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, 557212793Sdim GraphTraits<RegionNode*> > element_iterator; 558212793Sdim 559212793Sdim typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, 560212793Sdim false, GraphTraits<const RegionNode*> > 561212793Sdim const_element_iterator; 562212793Sdim 563212793Sdim element_iterator element_begin(); 564212793Sdim element_iterator element_end(); 565212793Sdim 566212793Sdim const_element_iterator element_begin() const; 567212793Sdim const_element_iterator element_end() const; 568212793Sdim //@} 569212793Sdim}; 570212793Sdim 571212793Sdim//===----------------------------------------------------------------------===// 572212793Sdim/// @brief Analysis that detects all canonical Regions. 573212793Sdim/// 574212793Sdim/// The RegionInfo pass detects all canonical regions in a function. The Regions 575212793Sdim/// are connected using the parent relation. This builds a Program Structure 576212793Sdim/// Tree. 577212793Sdimclass RegionInfo : public FunctionPass { 578212793Sdim typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap; 579212793Sdim typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap; 580212793Sdim typedef SmallPtrSet<Region*, 4> RegionSet; 581212793Sdim 582243830Sdim RegionInfo(const RegionInfo &) LLVM_DELETED_FUNCTION; 583243830Sdim const RegionInfo &operator=(const RegionInfo &) LLVM_DELETED_FUNCTION; 584212793Sdim 585212793Sdim DominatorTree *DT; 586212793Sdim PostDominatorTree *PDT; 587212793Sdim DominanceFrontier *DF; 588212793Sdim 589212793Sdim /// The top level region. 590212793Sdim Region *TopLevelRegion; 591212793Sdim 592212793Sdim /// Map every BB to the smallest region, that contains BB. 593212793Sdim BBtoRegionMap BBtoRegion; 594212793Sdim 595212793Sdim // isCommonDomFrontier - Returns true if BB is in the dominance frontier of 596212793Sdim // entry, because it was inherited from exit. In the other case there is an 597212793Sdim // edge going from entry to BB without passing exit. 598212793Sdim bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry, 599212793Sdim BasicBlock* exit) const; 600212793Sdim 601212793Sdim // isRegion - Check if entry and exit surround a valid region, based on 602212793Sdim // dominance tree and dominance frontier. 603212793Sdim bool isRegion(BasicBlock* entry, BasicBlock* exit) const; 604212793Sdim 605212793Sdim // insertShortCut - Saves a shortcut pointing from entry to exit. 606212793Sdim // This function may extend this shortcut if possible. 607212793Sdim void insertShortCut(BasicBlock* entry, BasicBlock* exit, 608212793Sdim BBtoBBMap* ShortCut) const; 609212793Sdim 610212793Sdim // getNextPostDom - Returns the next BB that postdominates N, while skipping 611212793Sdim // all post dominators that cannot finish a canonical region. 612212793Sdim DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const; 613212793Sdim 614212793Sdim // isTrivialRegion - A region is trivial, if it contains only one BB. 615212793Sdim bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const; 616212793Sdim 617212793Sdim // createRegion - Creates a single entry single exit region. 618212793Sdim Region *createRegion(BasicBlock *entry, BasicBlock *exit); 619212793Sdim 620212793Sdim // findRegionsWithEntry - Detect all regions starting with bb 'entry'. 621212793Sdim void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut); 622212793Sdim 623212793Sdim // scanForRegions - Detects regions in F. 624212793Sdim void scanForRegions(Function &F, BBtoBBMap *ShortCut); 625212793Sdim 626212793Sdim // getTopMostParent - Get the top most parent with the same entry block. 627212793Sdim Region *getTopMostParent(Region *region); 628212793Sdim 629212793Sdim // buildRegionsTree - build the region hierarchy after all region detected. 630212793Sdim void buildRegionsTree(DomTreeNode *N, Region *region); 631212793Sdim 632212793Sdim // Calculate - detecte all regions in function and build the region tree. 633212793Sdim void Calculate(Function& F); 634212793Sdim 635212793Sdim void releaseMemory(); 636212793Sdim 637212793Sdim // updateStatistics - Update statistic about created regions. 638212793Sdim void updateStatistics(Region *R); 639212793Sdim 640212793Sdim // isSimple - Check if a region is a simple region with exactly one entry 641212793Sdim // edge and exactly one exit edge. 642212793Sdim bool isSimple(Region* R) const; 643212793Sdim 644212793Sdimpublic: 645212793Sdim static char ID; 646212793Sdim explicit RegionInfo(); 647212793Sdim 648212793Sdim ~RegionInfo(); 649212793Sdim 650212793Sdim /// @name FunctionPass interface 651212793Sdim //@{ 652212793Sdim virtual bool runOnFunction(Function &F); 653212793Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 654212793Sdim virtual void print(raw_ostream &OS, const Module *) const; 655212793Sdim virtual void verifyAnalysis() const; 656212793Sdim //@} 657212793Sdim 658212793Sdim /// @brief Get the smallest region that contains a BasicBlock. 659212793Sdim /// 660212793Sdim /// @param BB The basic block. 661212793Sdim /// @return The smallest region, that contains BB or NULL, if there is no 662212793Sdim /// region containing BB. 663212793Sdim Region *getRegionFor(BasicBlock *BB) const; 664212793Sdim 665218893Sdim /// @brief Set the smallest region that surrounds a basic block. 666218893Sdim /// 667218893Sdim /// @param BB The basic block surrounded by a region. 668218893Sdim /// @param R The smallest region that surrounds BB. 669218893Sdim void setRegionFor(BasicBlock *BB, Region *R); 670218893Sdim 671212793Sdim /// @brief A shortcut for getRegionFor(). 672212793Sdim /// 673212793Sdim /// @param BB The basic block. 674212793Sdim /// @return The smallest region, that contains BB or NULL, if there is no 675212793Sdim /// region containing BB. 676212793Sdim Region *operator[](BasicBlock *BB) const; 677212793Sdim 678212793Sdim /// @brief Return the exit of the maximal refined region, that starts at a 679212793Sdim /// BasicBlock. 680212793Sdim /// 681212793Sdim /// @param BB The BasicBlock the refined region starts. 682212793Sdim BasicBlock *getMaxRegionExit(BasicBlock *BB) const; 683212793Sdim 684212793Sdim /// @brief Find the smallest region that contains two regions. 685212793Sdim /// 686212793Sdim /// @param A The first region. 687212793Sdim /// @param B The second region. 688212793Sdim /// @return The smallest region containing A and B. 689212793Sdim Region *getCommonRegion(Region* A, Region *B) const; 690212793Sdim 691212793Sdim /// @brief Find the smallest region that contains two basic blocks. 692212793Sdim /// 693212793Sdim /// @param A The first basic block. 694212793Sdim /// @param B The second basic block. 695212793Sdim /// @return The smallest region that contains A and B. 696212793Sdim Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const { 697212793Sdim return getCommonRegion(getRegionFor(A), getRegionFor(B)); 698212793Sdim } 699212793Sdim 700212793Sdim /// @brief Find the smallest region that contains a set of regions. 701212793Sdim /// 702212793Sdim /// @param Regions A vector of regions. 703212793Sdim /// @return The smallest region that contains all regions in Regions. 704212793Sdim Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const; 705212793Sdim 706212793Sdim /// @brief Find the smallest region that contains a set of basic blocks. 707212793Sdim /// 708212793Sdim /// @param BBs A vector of basic blocks. 709212793Sdim /// @return The smallest region that contains all basic blocks in BBS. 710212793Sdim Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const; 711212793Sdim 712212793Sdim Region *getTopLevelRegion() const { 713212793Sdim return TopLevelRegion; 714212793Sdim } 715212793Sdim 716218893Sdim /// @brief Update RegionInfo after a basic block was split. 717218893Sdim /// 718218893Sdim /// @param NewBB The basic block that was created before OldBB. 719218893Sdim /// @param OldBB The old basic block. 720218893Sdim void splitBlock(BasicBlock* NewBB, BasicBlock *OldBB); 721218893Sdim 722212793Sdim /// @brief Clear the Node Cache for all Regions. 723212793Sdim /// 724212793Sdim /// @see Region::clearNodeCache() 725212793Sdim void clearNodeCache() { 726212793Sdim if (TopLevelRegion) 727212793Sdim TopLevelRegion->clearNodeCache(); 728212793Sdim } 729212793Sdim}; 730212793Sdim 731212793Sdiminline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) { 732212793Sdim if (Node.isSubRegion()) 733212793Sdim return OS << Node.getNodeAs<Region>()->getNameStr(); 734212793Sdim else 735234353Sdim return OS << Node.getNodeAs<BasicBlock>()->getName(); 736212793Sdim} 737212793Sdim} // End llvm namespace 738212793Sdim#endif 739212793Sdim 740