1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Calculate a program structure tree built out of single entry single exit 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// regions. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The basic ideas are taken from "The Program Structure Tree - Richard Johnson, 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Koehler - 2009". 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The algorithm to calculate these data structures however is completely 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// different, as it takes advantage of existing information already available 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// in (Post)dominace tree and dominance frontier passes. This leads to a simpler 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// and in practice hopefully better performing algorithm. The runtime of the 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// algorithms described in the papers above are both linear in graph size, 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// O(V+E), whereas this algorithm is not, as the dominance frontier information 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// itself is not, but in practice runtime seems to be in the order of magnitude 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// of dominance tree calculation. 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ANALYSIS_REGION_INFO_H 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ANALYSIS_REGION_INFO_H 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/PointerIntPair.h" 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/DominanceFrontier.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/PostDominators.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Allocator.h" 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <map> 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Region; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass RegionInfo; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass raw_ostream; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Loop; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass LoopInfo; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief Marker class to iterate over the elements of a Region in flat mode. 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The class is used to either iterate in Flat mode or by not using it to not 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// iterate in Flat mode. During a Flat mode iteration all Regions are entered 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// and the iteration returns every BasicBlock. If the Flat mode is not 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// selected for SubRegions just one RegionNode containing the subregion is 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// returned. 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <class GraphType> 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass FlatIt {}; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Region. 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass RegionNode { 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode(const RegionNode &); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const RegionNode &operator=(const RegionNode &); 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprotected: 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This is the entry basic block that starts this region node. If this is a 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BasicBlock RegionNode, then entry is just the basic block, that this 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// In the BBtoRegionNode map of the parent of this node, BB will always map 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// to this node no matter which kind of node this one is. 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// The node can hold either a Region or a BasicBlock. 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Use one bit to save, if this RegionNode is a subregion or BasicBlock 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RegionNode. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PointerIntPair<BasicBlock*, 1, bool> entry; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief The parent Region of this RegionNode. 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @see getParent() 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* parent; 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create a RegionNode. 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Parent The parent of this RegionNode. 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Entry The entry BasicBlock of the RegionNode. If this 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RegionNode represents a BasicBlock, this is the 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BasicBlock itself. If it represents a subregion, this 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// is the entry BasicBlock of the subregion. 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param isSubRegion If this RegionNode represents a SubRegion. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0) 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : entry(Entry, isSubRegion), parent(Parent) {} 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the parent Region of this RegionNode. 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// The parent Region is the Region this RegionNode belongs to. If for 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// example a BasicBlock is element of two Regions, there exist two 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RegionNodes for this BasicBlock. Each with the getParent() function 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// pointing to the Region this RegionNode belongs to. 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return Get the parent Region of this RegionNode. 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Region* getParent() const { return parent; } 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the entry BasicBlock of this RegionNode. 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// If this RegionNode represents a BasicBlock this is just the BasicBlock 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// itself, otherwise we return the entry BasicBlock of the Subregion 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The entry BasicBlock of this RegionNode. 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline BasicBlock* getEntry() const { return entry.getPointer(); } 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the content of this RegionNode. 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// check the type of the content with the isSubRegion() function call. 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The content of this RegionNode. 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<class T> 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline T* getNodeAs() const; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Is this RegionNode a subregion? 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if it contains a subregion. False if it contains a 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BasicBlock. 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool isSubRegion() const { 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return entry.getInt(); 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Print a RegionNode. 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node); 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<> 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const { 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getEntry(); 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<> 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline Region* RegionNode::getNodeAs<Region>() const { 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(isSubRegion() && "This is not a subregion RegionNode!"); 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return reinterpret_cast<Region*>(const_cast<RegionNode*>(this)); 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief A single entry single exit Region. 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// A Region is a connected subgraph of a control flow graph that has exactly 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// two connections to the remaining graph. It can be used to analyze or 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// optimize parts of the control flow graph. 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// A <em> simple Region </em> is connected to the remaining graph by just two 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// edges. One edge entering the Region and another one leaving the Region. 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// An <em> extended Region </em> (or just Region) is a subgraph that can be 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// transform into a simple Region. The transformation is done by adding 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BasicBlocks that merge several entry or exit edges so that after the merge 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// just one entry and one exit edge exists. 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The \e Entry of a Region is the first BasicBlock that is passed after 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// entering the Region. It is an element of the Region. The entry BasicBlock 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// dominates all BasicBlocks in the Region. 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The \e Exit of a Region is the first BasicBlock that is passed after 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// leaving the Region. It is not an element of the Region. The exit BasicBlock, 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// postdominates all BasicBlocks in the Region. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// A <em> canonical Region </em> cannot be constructed by combining smaller 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Regions. 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Region A is the \e parent of Region B, if B is completely contained in A. 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Two canonical Regions either do not intersect at all or one is 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the parent of the other. 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Regions in the control flow graph and E is the \e parent relation of these 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Regions. 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Example: 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// \verbatim 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// A simple control flow graph, that contains two regions. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 1 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// / | 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 2 | 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// / \ 3 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 4 5 | 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// | | | 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 6 7 8 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// \ | / 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 9 Region B: 2 -> 9 {2,4,5,6,7} 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// \endverbatim 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// You can obtain more examples by either calling 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// <tt> "opt -regions -analyze anyprogram.ll" </tt> 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// or 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// <tt> "opt -view-regions-only anyprogram.ll" </tt> 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// on any LLVM file you are interested in. 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The first call returns a textual representation of the program structure 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// tree, the second one creates a graphical representation using graphviz. 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Region : public RegionNode { 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman friend class RegionInfo; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region(const Region &); 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Region &operator=(const Region &); 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Information necessary to manage this Region. 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionInfo* RI; 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree *DT; 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The exit BasicBlock of this region. 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // (The entry BasicBlock is part of RegionNode) 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *exit; 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<Region*> RegionSet; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The subregions of this region. 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionSet children; 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT; 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Save the BasicBlock RegionNodes that are element of this Region. 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman mutable BBNodeMapT BBNodeMap; 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// verifyBBInRegion - Check if a BB is in this Region. This check also works 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// if the region is incorrectly built. (EXPENSIVE!) 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void verifyBBInRegion(BasicBlock* BB) const; 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// verifyWalk - Walk over all the BBs of the region starting from BB and 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// verify that all reachable basic blocks are elements of the region. 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// (EXPENSIVE!) 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const; 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// verifyRegionNest - Verify if the region and its children are valid 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// regions (EXPENSIVE!) 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void verifyRegionNest() const; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create a new region. 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Entry The entry basic block of the region. 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Exit The exit basic block of the region. 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param RI The region info object that is managing this region. 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param DT The dominator tree of the current function. 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Parent The surrounding region or NULL if this is a top level 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// region. 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI, 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree *DT, Region *Parent = 0); 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Delete the Region and all its subregions. 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ~Region(); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the entry BasicBlock of the Region. 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The entry BasicBlock of the region. 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *getEntry() const { return RegionNode::getEntry(); } 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Replace the entry basic block of the region with the new basic 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// block. 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BB The new entry basic block of the region. 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void replaceEntry(BasicBlock *BB); 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Replace the exit basic block of the region with the new basic 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// block. 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BB The new exit basic block of the region. 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void replaceExit(BasicBlock *BB); 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the exit BasicBlock of the Region. 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Region. 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *getExit() const { return exit; } 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the parent of the Region. 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The parent of the Region or NULL if this is a top level 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Region. 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *getParent() const { return RegionNode::getParent(); } 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the RegionNode representing the current Region. 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The RegionNode representing the current Region. 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode* getNode() const { 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this)); 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the nesting level of this Region. 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// An toplevel Region has depth 0. 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The depth of the region. 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getDepth() const; 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Check if a Region is the TopLevel region. 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The toplevel region represents the whole function. 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isTopLevelRegion() const { return exit == NULL; } 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Return a new (non canonical) region, that is obtained by joining 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// this region with its predecessors. 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return A region also starting at getEntry(), but reaching to the next 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// basic block that forms with getEntry() a (non canonical) region. 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// NULL if such a basic block does not exist. 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Region *getExpandedRegion() const; 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Return the first block of this region's single entry edge, 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// if existing. 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return The BasicBlock starting this region's single entry edge, 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// else NULL. 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *getEnteringBlock() const; 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Return the first block of this region's single exit edge, 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// if existing. 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return The BasicBlock starting this region's single exit edge, 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// else NULL. 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *getExitingBlock() const; 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Is this a simple region? 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// A region is simple if it has exactly one exit and one entry edge. 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if the Region is simple. 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isSimple() const; 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Returns the name of the Region. 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The Name of the Region. 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string getNameStr() const; 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Return the RegionInfo object, that belongs to this Region. 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionInfo *getRegionInfo() const { 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RI; 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// PrintStyle - Print region in difference ways. 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum PrintStyle { PrintNone, PrintBB, PrintRN }; 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Print the region. 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param OS The output stream the Region is printed to. 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param printTree Print also the tree of subregions. 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param level The indentation level used for printing. 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void print(raw_ostream& OS, bool printTree = true, unsigned level = 0, 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum PrintStyle Style = PrintNone) const; 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Print the region to stderr. 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void dump() const; 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Check if the region contains a BasicBlock. 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The BasicBlock that might be contained in this Region. 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if the block is contained in the region otherwise false. 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool contains(const BasicBlock *BB) const; 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Check if the region contains another region. 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param SubRegion The region that might be contained in this Region. 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if SubRegion is contained in the region otherwise false. 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool contains(const Region *SubRegion) const { 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Toplevel Region. 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!getExit()) 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return contains(SubRegion->getEntry()) 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit()); 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Check if the region contains an Instruction. 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Inst The Instruction that might be contained in this region. 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if the Instruction is contained in the region otherwise false. 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool contains(const Instruction *Inst) const { 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return contains(Inst->getParent()); 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Check if the region contains a loop. 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param L The loop that might be contained in this region. 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return True if the loop is contained in the region otherwise false. 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// In case a NULL pointer is passed to this function the result 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// is false, except for the region that describes the whole function. 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// In that case true is returned. 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool contains(const Loop *L) const; 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the outermost loop in the region that contains a loop. 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Find for a Loop L the outermost loop OuterL that is a parent loop of L 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// and is itself contained in the region. 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param L The loop the lookup is started. 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The outermost loop in the region, NULL if such a loop does not 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// exist or if the region describes the whole function. 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *outermostLoopInRegion(Loop *L) const; 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the outermost loop in the region that contains a basic block. 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Find for a basic block BB the outermost loop L that contains BB and is 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// itself contained in the region. 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param LI A pointer to a LoopInfo analysis. 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The basic block surrounded by the loop. 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The outermost loop in the region, NULL if such a loop does not 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// exist or if the region describes the whole function. 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loop *outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const; 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the subregion that starts at a BasicBlock 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The BasicBlock the subregion should start. 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The Subregion if available, otherwise NULL. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* getSubRegionNode(BasicBlock *BB) const; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the RegionNode for a BasicBlock 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The BasicBlock at which the RegionNode should start. 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return If available, the RegionNode that represents the subregion 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// starting at BB. If no subregion starts at BB, the RegionNode 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// representing BB. 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode* getNode(BasicBlock *BB) const; 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the BasicBlock RegionNode for a BasicBlock 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The BasicBlock for which the RegionNode is requested. 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The RegionNode representing the BB. 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode* getBBNode(BasicBlock *BB) const; 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Add a new subregion to this Region. 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param SubRegion The new subregion that will be added. 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param moveChildren Move the children of this region, that are also 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// contained in SubRegion into SubRegion. 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addSubRegion(Region *SubRegion, bool moveChildren = false); 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Remove a subregion from this Region. 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// The subregion is not deleted, as it will probably be inserted into another 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// region. 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param SubRegion The SubRegion that will be removed. 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *removeSubRegion(Region *SubRegion); 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Move all direct child nodes of this Region to another Region. 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param To The Region the child nodes will be transferred to. 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void transferChildrenTo(Region *To); 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Verify if the region is a correct region. 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Check if this is a correctly build Region. This is an expensive check, as 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the complete CFG of the Region will be walked. 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void verifyRegion() const; 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Clear the cache for BB RegionNodes. 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// After calling this function the BasicBlock RegionNodes will be stored at 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// different memory locations. RegionNodes obtained before this function is 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// called are therefore not comparable to RegionNodes abtained afterwords. 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clearNodeCache(); 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @name Subregion Iterators 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// These iterators iterator over all subregions of this Region. 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@{ 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RegionSet::iterator iterator; 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RegionSet::const_iterator const_iterator; 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator begin() { return children.begin(); } 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator end() { return children.end(); } 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator begin() const { return children.begin(); } 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator end() const { return children.end(); } 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@} 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @name BasicBlock Iterators 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// These iterators iterate over all BasicBlock RegionNodes that are 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// contained in this Region. The iterator also iterates over BasicBlocks 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// that are elements of a subregion of this Region. It is therefore called a 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// flat iterator. 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@{ 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GraphTraits<FlatIt<RegionNode*> > > block_iterator; 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman false, GraphTraits<FlatIt<const RegionNode*> > > 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_block_iterator; 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman block_iterator block_begin(); 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman block_iterator block_end(); 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_block_iterator block_begin() const; 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_block_iterator block_end() const; 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@} 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @name Element Iterators 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// These iterators iterate over all BasicBlock and subregion RegionNodes that 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// are direct children of this Region. It does not iterate over any 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// RegionNodes that are also element of a subregion of this Region. 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@{ 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GraphTraits<RegionNode*> > element_iterator; 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman false, GraphTraits<const RegionNode*> > 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_element_iterator; 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman element_iterator element_begin(); 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman element_iterator element_end(); 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_element_iterator element_begin() const; 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_element_iterator element_end() const; 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@} 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief Analysis that detects all canonical Regions. 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The RegionInfo pass detects all canonical regions in a function. The Regions 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// are connected using the parent relation. This builds a Program Structure 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Tree. 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass RegionInfo : public FunctionPass { 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap; 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap; 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallPtrSet<Region*, 4> RegionSet; 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionInfo(const RegionInfo &); 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DO NOT IMPLEMENT 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const RegionInfo &operator=(const RegionInfo &); 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree *DT; 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PostDominatorTree *PDT; 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominanceFrontier *DF; 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// The top level region. 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *TopLevelRegion; 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Map every BB to the smallest region, that contains BB. 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BBtoRegionMap BBtoRegion; 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isCommonDomFrontier - Returns true if BB is in the dominance frontier of 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // entry, because it was inherited from exit. In the other case there is an 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // edge going from entry to BB without passing exit. 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry, 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* exit) const; 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isRegion - Check if entry and exit surround a valid region, based on 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dominance tree and dominance frontier. 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isRegion(BasicBlock* entry, BasicBlock* exit) const; 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // insertShortCut - Saves a shortcut pointing from entry to exit. 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This function may extend this shortcut if possible. 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void insertShortCut(BasicBlock* entry, BasicBlock* exit, 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BBtoBBMap* ShortCut) const; 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getNextPostDom - Returns the next BB that postdominates N, while skipping 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // all post dominators that cannot finish a canonical region. 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const; 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isTrivialRegion - A region is trivial, if it contains only one BB. 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const; 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // createRegion - Creates a single entry single exit region. 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *createRegion(BasicBlock *entry, BasicBlock *exit); 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // findRegionsWithEntry - Detect all regions starting with bb 'entry'. 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut); 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // scanForRegions - Detects regions in F. 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void scanForRegions(Function &F, BBtoBBMap *ShortCut); 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getTopMostParent - Get the top most parent with the same entry block. 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *getTopMostParent(Region *region); 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // buildRegionsTree - build the region hierarchy after all region detected. 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void buildRegionsTree(DomTreeNode *N, Region *region); 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Calculate - detecte all regions in function and build the region tree. 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Calculate(Function& F); 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void releaseMemory(); 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // updateStatistics - Update statistic about created regions. 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void updateStatistics(Region *R); 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isSimple - Check if a region is a simple region with exactly one entry 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // edge and exactly one exit edge. 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isSimple(Region* R) const; 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit RegionInfo(); 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ~RegionInfo(); 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @name FunctionPass interface 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@{ 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnFunction(Function &F); 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void print(raw_ostream &OS, const Module *) const; 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void verifyAnalysis() const; 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //@} 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get the smallest region that contains a BasicBlock. 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The basic block. 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region, that contains BB or NULL, if there is no 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// region containing BB. 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *getRegionFor(BasicBlock *BB) const; 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Set the smallest region that surrounds a basic block. 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BB The basic block surrounded by a region. 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param R The smallest region that surrounds BB. 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setRegionFor(BasicBlock *BB, Region *R); 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief A shortcut for getRegionFor(). 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The basic block. 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region, that contains BB or NULL, if there is no 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// region containing BB. 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *operator[](BasicBlock *BB) const; 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Return the exit of the maximal refined region, that starts at a 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BasicBlock. 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BB The BasicBlock the refined region starts. 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *getMaxRegionExit(BasicBlock *BB) const; 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Find the smallest region that contains two regions. 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param A The first region. 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param B The second region. 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region containing A and B. 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *getCommonRegion(Region* A, Region *B) const; 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Find the smallest region that contains two basic blocks. 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param A The first basic block. 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param B The second basic block. 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region that contains A and B. 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const { 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getCommonRegion(getRegionFor(A), getRegionFor(B)); 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Find the smallest region that contains a set of regions. 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param Regions A vector of regions. 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region that contains all regions in Regions. 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const; 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Find the smallest region that contains a set of basic blocks. 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @param BBs A vector of basic blocks. 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @return The smallest region that contains all basic blocks in BBS. 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const; 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region *getTopLevelRegion() const { 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TopLevelRegion; 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @brief Update RegionInfo after a basic block was split. 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param NewBB The basic block that was created before OldBB. 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param OldBB The old basic block. 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitBlock(BasicBlock* NewBB, BasicBlock *OldBB); 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Clear the Node Cache for all Regions. 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @see Region::clearNodeCache() 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clearNodeCache() { 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TopLevelRegion) 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TopLevelRegion->clearNodeCache(); 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) { 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Node.isSubRegion()) 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return OS << Node.getNodeAs<Region>()->getNameStr(); 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return OS << Node.getNodeAs<BasicBlock>()->getNameStr(); 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End llvm namespace 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 689