RegionInfo.h revision 4bcc0228dcc90385e90f22cef38b2614d3aa3cd1
144d362409d5469aed47d19e7908d19bd194493aThomas Graf//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// 244d362409d5469aed47d19e7908d19bd194493aThomas Graf// 344d362409d5469aed47d19e7908d19bd194493aThomas Graf// The LLVM Compiler Infrastructure 444d362409d5469aed47d19e7908d19bd194493aThomas Graf// 544d362409d5469aed47d19e7908d19bd194493aThomas Graf// This file is distributed under the University of Illinois Open Source 644d362409d5469aed47d19e7908d19bd194493aThomas Graf// License. See LICENSE.TXT for details. 744d362409d5469aed47d19e7908d19bd194493aThomas Graf// 844d362409d5469aed47d19e7908d19bd194493aThomas Graf//===----------------------------------------------------------------------===// 9535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf// 1044d362409d5469aed47d19e7908d19bd194493aThomas Graf// Calculate a program structure tree built out of single entry single exit 1144d362409d5469aed47d19e7908d19bd194493aThomas Graf// regions. 1244d362409d5469aed47d19e7908d19bd194493aThomas Graf// The basic ideas are taken from "The Program Structure Tree - Richard Johnson, 1344d362409d5469aed47d19e7908d19bd194493aThomas Graf// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The 1444d362409d5469aed47d19e7908d19bd194493aThomas Graf// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana 1544d362409d5469aed47d19e7908d19bd194493aThomas Graf// Koehler - 2009". 1644d362409d5469aed47d19e7908d19bd194493aThomas Graf// The algorithm to calculate these data structures however is completely 1744d362409d5469aed47d19e7908d19bd194493aThomas Graf// different, as it takes advantage of existing information already available 1844d362409d5469aed47d19e7908d19bd194493aThomas Graf// in (Post)dominace tree and dominance frontier passes. This leads to a simpler 1944d362409d5469aed47d19e7908d19bd194493aThomas Graf// and in practice hopefully better performing algorithm. The runtime of the 2044d362409d5469aed47d19e7908d19bd194493aThomas Graf// algorithms described in the papers above are both linear in graph size, 2144d362409d5469aed47d19e7908d19bd194493aThomas Graf// O(V+E), whereas this algorithm is not, as the dominance frontier information 2244d362409d5469aed47d19e7908d19bd194493aThomas Graf// itself is not, but in practice runtime seems to be in the order of magnitude 2344d362409d5469aed47d19e7908d19bd194493aThomas Graf// of dominance tree calculation. 2444d362409d5469aed47d19e7908d19bd194493aThomas Graf// 252bdee95a765457fe4206b89d51974ae56e75c588Thomas Graf//===----------------------------------------------------------------------===// 2644d362409d5469aed47d19e7908d19bd194493aThomas Graf 2744d362409d5469aed47d19e7908d19bd194493aThomas Graf#ifndef LLVM_ANALYSIS_REGION_INFO_H 2844d362409d5469aed47d19e7908d19bd194493aThomas Graf#define LLVM_ANALYSIS_REGION_INFO_H 2944d362409d5469aed47d19e7908d19bd194493aThomas Graf 301155370f520cb64657e25153255cf7dc1424317fThomas Graf#include "llvm/ADT/PointerIntPair.h" 3144d362409d5469aed47d19e7908d19bd194493aThomas Graf#include "llvm/Analysis/Dominators.h" 3244d362409d5469aed47d19e7908d19bd194493aThomas Graf#include "llvm/Analysis/PostDominators.h" 3344d362409d5469aed47d19e7908d19bd194493aThomas Graf#include "llvm/Support/Allocator.h" 3444d362409d5469aed47d19e7908d19bd194493aThomas Graf 3544d362409d5469aed47d19e7908d19bd194493aThomas Grafnamespace llvm { 3644d362409d5469aed47d19e7908d19bd194493aThomas Graf 3744d362409d5469aed47d19e7908d19bd194493aThomas Grafclass Region; 3844d362409d5469aed47d19e7908d19bd194493aThomas Grafclass RegionInfo; 3944d362409d5469aed47d19e7908d19bd194493aThomas Grafclass raw_ostream; 4044d362409d5469aed47d19e7908d19bd194493aThomas Grafclass Loop; 4144d362409d5469aed47d19e7908d19bd194493aThomas Grafclass LoopInfo; 4244d362409d5469aed47d19e7908d19bd194493aThomas Graf 431155370f520cb64657e25153255cf7dc1424317fThomas Graf/// @brief Marker class to iterate over the elements of a Region in flat mode. 4444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 4544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// The class is used to either iterate in Flat mode or by not using it to not 4644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// iterate in Flat mode. During a Flat mode iteration all Regions are entered 4744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// and the iteration returns every BasicBlock. If the Flat mode is not 481155370f520cb64657e25153255cf7dc1424317fThomas Graf/// selected for SubRegions just one RegionNode containing the subregion is 4944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// returned. 5044d362409d5469aed47d19e7908d19bd194493aThomas Graftemplate <class GraphType> 5144d362409d5469aed47d19e7908d19bd194493aThomas Grafclass FlatIt {}; 5244d362409d5469aed47d19e7908d19bd194493aThomas Graf 5344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a 5444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Region. 551155370f520cb64657e25153255cf7dc1424317fThomas Grafclass RegionNode { 5644d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 5744d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionNode(const RegionNode &); 5844d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 5944d362409d5469aed47d19e7908d19bd194493aThomas Graf const RegionNode &operator=(const RegionNode &); 6044d362409d5469aed47d19e7908d19bd194493aThomas Graf 611155370f520cb64657e25153255cf7dc1424317fThomas Grafprotected: 6244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// This is the entry basic block that starts this region node. If this is a 631155370f520cb64657e25153255cf7dc1424317fThomas Graf /// BasicBlock RegionNode, then entry is just the basic block, that this 641155370f520cb64657e25153255cf7dc1424317fThomas Graf /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. 651155370f520cb64657e25153255cf7dc1424317fThomas Graf /// 661155370f520cb64657e25153255cf7dc1424317fThomas Graf /// In the BBtoRegionNode map of the parent of this node, BB will always map 671155370f520cb64657e25153255cf7dc1424317fThomas Graf /// to this node no matter which kind of node this one is. 681155370f520cb64657e25153255cf7dc1424317fThomas Graf /// 691155370f520cb64657e25153255cf7dc1424317fThomas Graf /// The node can hold either a Region or a BasicBlock. 701155370f520cb64657e25153255cf7dc1424317fThomas Graf /// Use one bit to save, if this RegionNode is a subregion or BasicBlock 7144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// RegionNode. 7244d362409d5469aed47d19e7908d19bd194493aThomas Graf PointerIntPair<BasicBlock*, 1, bool> entry; 7344d362409d5469aed47d19e7908d19bd194493aThomas Graf 7444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief The parent Region of this RegionNode. 7544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @see getParent() 7644d362409d5469aed47d19e7908d19bd194493aThomas Graf Region* parent; 7744d362409d5469aed47d19e7908d19bd194493aThomas Graf 7844d362409d5469aed47d19e7908d19bd194493aThomas Grafpublic: 7944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Create a RegionNode. 8044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 8144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Parent The parent of this RegionNode. 8244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Entry The entry BasicBlock of the RegionNode. If this 8344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// RegionNode represents a BasicBlock, this is the 8444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// BasicBlock itself. If it represents a subregion, this 8544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// is the entry BasicBlock of the subregion. 8644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param isSubRegion If this RegionNode represents a SubRegion. 8744d362409d5469aed47d19e7908d19bd194493aThomas Graf inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0) 8844d362409d5469aed47d19e7908d19bd194493aThomas Graf : entry(Entry, isSubRegion), parent(Parent) {} 8944d362409d5469aed47d19e7908d19bd194493aThomas Graf 9044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the parent Region of this RegionNode. 9144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 9244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// The parent Region is the Region this RegionNode belongs to. If for 931155370f520cb64657e25153255cf7dc1424317fThomas Graf /// example a BasicBlock is element of two Regions, there exist two 9444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// RegionNodes for this BasicBlock. Each with the getParent() function 9544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// pointing to the Region this RegionNode belongs to. 9644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 9744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return Get the parent Region of this RegionNode. 9844d362409d5469aed47d19e7908d19bd194493aThomas Graf inline Region* getParent() const { return parent; } 99535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf 10044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the entry BasicBlock of this RegionNode. 10144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 10244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// If this RegionNode represents a BasicBlock this is just the BasicBlock 10344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// itself, otherwise we return the entry BasicBlock of the Subregion 10444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 10544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The entry BasicBlock of this RegionNode. 10644d362409d5469aed47d19e7908d19bd194493aThomas Graf inline BasicBlock* getEntry() const { return entry.getPointer(); } 10744d362409d5469aed47d19e7908d19bd194493aThomas Graf 10844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the content of this RegionNode. 10944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 11044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() 11144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// check the type of the content with the isSubRegion() function call. 11244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 11344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The content of this RegionNode. 11444d362409d5469aed47d19e7908d19bd194493aThomas Graf template<class T> 11544d362409d5469aed47d19e7908d19bd194493aThomas Graf inline T* getNodeAs() const; 11644d362409d5469aed47d19e7908d19bd194493aThomas Graf 11744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Is this RegionNode a subregion? 11844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 11944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if it contains a subregion. False if it contains a 12044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// BasicBlock. 12144d362409d5469aed47d19e7908d19bd194493aThomas Graf inline bool isSubRegion() const { 12244d362409d5469aed47d19e7908d19bd194493aThomas Graf return entry.getInt(); 12344d362409d5469aed47d19e7908d19bd194493aThomas Graf } 12444d362409d5469aed47d19e7908d19bd194493aThomas Graf}; 12544d362409d5469aed47d19e7908d19bd194493aThomas Graf 12644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Print a RegionNode. 12744d362409d5469aed47d19e7908d19bd194493aThomas Grafinline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node); 12844d362409d5469aed47d19e7908d19bd194493aThomas Graf 12944d362409d5469aed47d19e7908d19bd194493aThomas Graftemplate<> 13044d362409d5469aed47d19e7908d19bd194493aThomas Grafinline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const { 13144d362409d5469aed47d19e7908d19bd194493aThomas Graf assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); 1326de17f3308cfd53ad922d144a1b28ddd962d6678Thomas Graf return getEntry(); 13323ee46ef7115c2e311c36e43a833e6c3deada18aThomas Graf} 13444d362409d5469aed47d19e7908d19bd194493aThomas Graf 13544d362409d5469aed47d19e7908d19bd194493aThomas Graftemplate<> 13644d362409d5469aed47d19e7908d19bd194493aThomas Grafinline Region* RegionNode::getNodeAs<Region>() const { 13744d362409d5469aed47d19e7908d19bd194493aThomas Graf assert(isSubRegion() && "This is not a subregion RegionNode!"); 13844d362409d5469aed47d19e7908d19bd194493aThomas Graf return reinterpret_cast<Region*>(const_cast<RegionNode*>(this)); 13944d362409d5469aed47d19e7908d19bd194493aThomas Graf} 14044d362409d5469aed47d19e7908d19bd194493aThomas Graf 14144d362409d5469aed47d19e7908d19bd194493aThomas Graf//===----------------------------------------------------------------------===// 14244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// @brief A single entry single exit Region. 14344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 14444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// A Region is a connected subgraph of a control flow graph that has exactly 14544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// two connections to the remaining graph. It can be used to analyze or 14644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// optimize parts of the control flow graph. 14744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 14844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// A <em> simple Region </em> is connected to the remaing graph by just two 14944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// edges. One edge entering the Region and another one leaving the Region. 15044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 15144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// An <em> extended Region </em> (or just Region) is a subgraph that can be 15244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// transform into a simple Region. The transformation is done by adding 15344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// BasicBlocks that merge several entry or exit edges so that after the merge 15444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// just one entry and one exit edge exists. 15544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 15644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// The \e Entry of a Region is the first BasicBlock that is passed after 15744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// entering the Region. It is an element of the Region. The entry BasicBlock 15844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// dominates all BasicBlocks in the Region. 15944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 16044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// The \e Exit of a Region is the first BasicBlock that is passed after 16144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// leaving the Region. It is not an element of the Region. The exit BasicBlock, 16244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// postdominates all BasicBlocks in the Region. 16344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 16444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// A <em> canonical Region </em> cannot be constructed by combining smaller 16544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Regions. 16644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 16744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Region A is the \e parent of Region B, if B is completely contained in A. 16844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 16944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Two canonical Regions either do not intersect at all or one is 1703ad4665be2f192291238cbe78118a57ec42436c6Thomas Graf/// the parent of the other. 1713ad4665be2f192291238cbe78118a57ec42436c6Thomas Graf/// 172a7469ce758fac3631df6ce72eb3f89150070e7f8Thomas Graf/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of 173a7469ce758fac3631df6ce72eb3f89150070e7f8Thomas Graf/// Regions in the control flow graph and E is the \e parent relation of these 174a7469ce758fac3631df6ce72eb3f89150070e7f8Thomas Graf/// Regions. 17544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 17644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Example: 17744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 17844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// \verbatim 17944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// A simple control flow graph, that contains two regions. 18044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 18144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 1 18244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// / | 18344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 2 | 18444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// / \ 3 18544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 4 5 | 18644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// | | | 18744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 6 7 8 18844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// \ | / 18944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} 19044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 9 Region B: 2 -> 9 {2,4,5,6,7} 19144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// \endverbatim 19244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 19344d362409d5469aed47d19e7908d19bd194493aThomas Graf/// You can obtain more examples by either calling 19444d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 19544d362409d5469aed47d19e7908d19bd194493aThomas Graf/// <tt> "opt -regions -analyze anyprogram.ll" </tt> 19644d362409d5469aed47d19e7908d19bd194493aThomas Graf/// or 19744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// <tt> "opt -view-regions-only anyprogram.ll" </tt> 19844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 19944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// on any LLVM file you are interested in. 20044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 20144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// The first call returns a textual representation of the program structure 20244d362409d5469aed47d19e7908d19bd194493aThomas Graf/// tree, the second one creates a graphical representation using graphviz. 20344d362409d5469aed47d19e7908d19bd194493aThomas Grafclass Region : public RegionNode { 20444d362409d5469aed47d19e7908d19bd194493aThomas Graf friend class RegionInfo; 20544d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 20644d362409d5469aed47d19e7908d19bd194493aThomas Graf Region(const Region &); 20744d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 20844d362409d5469aed47d19e7908d19bd194493aThomas Graf const Region &operator=(const Region &); 20944d362409d5469aed47d19e7908d19bd194493aThomas Graf 21044d362409d5469aed47d19e7908d19bd194493aThomas Graf // Information necessary to manage this Region. 21144d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionInfo* RI; 21244d362409d5469aed47d19e7908d19bd194493aThomas Graf DominatorTree *DT; 21344d362409d5469aed47d19e7908d19bd194493aThomas Graf 21444d362409d5469aed47d19e7908d19bd194493aThomas Graf // The exit BasicBlock of this region. 21544d362409d5469aed47d19e7908d19bd194493aThomas Graf // (The entry BasicBlock is part of RegionNode) 21644d362409d5469aed47d19e7908d19bd194493aThomas Graf BasicBlock *exit; 21744d362409d5469aed47d19e7908d19bd194493aThomas Graf 21844d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef std::vector<Region*> RegionSet; 21944d362409d5469aed47d19e7908d19bd194493aThomas Graf 22044d362409d5469aed47d19e7908d19bd194493aThomas Graf // The subregions of this region. 22144d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionSet children; 22244d362409d5469aed47d19e7908d19bd194493aThomas Graf 22344d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT; 22444d362409d5469aed47d19e7908d19bd194493aThomas Graf 22544d362409d5469aed47d19e7908d19bd194493aThomas Graf // Save the BasicBlock RegionNodes that are element of this Region. 22644d362409d5469aed47d19e7908d19bd194493aThomas Graf mutable BBNodeMapT BBNodeMap; 22744d362409d5469aed47d19e7908d19bd194493aThomas Graf 22844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// verifyBBInRegion - Check if a BB is in this Region. This check also works 22944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// if the region is incorrectly built. (EXPENSIVE!) 23044d362409d5469aed47d19e7908d19bd194493aThomas Graf void verifyBBInRegion(BasicBlock* BB) const; 23144d362409d5469aed47d19e7908d19bd194493aThomas Graf 23244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// verifyWalk - Walk over all the BBs of the region starting from BB and 23344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// verify that all reachable basic blocks are elements of the region. 23444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// (EXPENSIVE!) 23544d362409d5469aed47d19e7908d19bd194493aThomas Graf void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const; 23644d362409d5469aed47d19e7908d19bd194493aThomas Graf 23744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// verifyRegionNest - Verify if the region and its children are valid 23844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// regions (EXPENSIVE!) 23944d362409d5469aed47d19e7908d19bd194493aThomas Graf void verifyRegionNest() const; 24044d362409d5469aed47d19e7908d19bd194493aThomas Graf 24144d362409d5469aed47d19e7908d19bd194493aThomas Grafpublic: 24244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Create a new region. 24344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 24444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Entry The entry basic block of the region. 24544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Exit The exit basic block of the region. 24644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param RI The region info object that is managing this region. 24744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param DT The dominator tree of the current function. 248535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf /// @param Parent The surrounding region or NULL if this is a top level 24944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// region. 250535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI, 25144d362409d5469aed47d19e7908d19bd194493aThomas Graf DominatorTree *DT, Region *Parent = 0); 25244d362409d5469aed47d19e7908d19bd194493aThomas Graf 25344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Delete the Region and all its subregions. 25444d362409d5469aed47d19e7908d19bd194493aThomas Graf ~Region(); 25544d362409d5469aed47d19e7908d19bd194493aThomas Graf 25644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the entry BasicBlock of the Region. 25744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The entry BasicBlock of the region. 25844d362409d5469aed47d19e7908d19bd194493aThomas Graf BasicBlock *getEntry() const { return RegionNode::getEntry(); } 25944d362409d5469aed47d19e7908d19bd194493aThomas Graf 26044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Replace the entry basic block of the region with the new basic 26144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// block. 26244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 26344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The new entry basic block of the region. 264535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf void replaceEntry(BasicBlock *BB); 26544d362409d5469aed47d19e7908d19bd194493aThomas Graf 26644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Replace the exit basic block of the region with the new basic 26744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// block. 268535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf /// 269535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf /// @param BB The new exit basic block of the region. 27044d362409d5469aed47d19e7908d19bd194493aThomas Graf void replaceExit(BasicBlock *BB); 27144d362409d5469aed47d19e7908d19bd194493aThomas Graf 27244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the exit BasicBlock of the Region. 273535e83162249ed6274ba46bc72d8cc683ba20e17Thomas Graf /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel 27444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Region. 27544d362409d5469aed47d19e7908d19bd194493aThomas Graf BasicBlock *getExit() const { return exit; } 27644d362409d5469aed47d19e7908d19bd194493aThomas Graf 27744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the parent of the Region. 27844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The parent of the Region or NULL if this is a top level 27944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Region. 28044d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *getParent() const { return RegionNode::getParent(); } 28144d362409d5469aed47d19e7908d19bd194493aThomas Graf 28244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the RegionNode representing the current Region. 28344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The RegionNode representing the current Region. 28444d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionNode* getNode() const { 28544d362409d5469aed47d19e7908d19bd194493aThomas Graf return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this)); 28644d362409d5469aed47d19e7908d19bd194493aThomas Graf } 28744d362409d5469aed47d19e7908d19bd194493aThomas Graf 28844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the nesting level of this Region. 28944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 29044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// An toplevel Region has depth 0. 29144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 29244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The depth of the region. 29344d362409d5469aed47d19e7908d19bd194493aThomas Graf unsigned getDepth() const; 29444d362409d5469aed47d19e7908d19bd194493aThomas Graf 29544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Is this a simple region? 29644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 29744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// A region is simple if it has exactly one exit and one entry edge. 29844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 29944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if the Region is simple. 30044d362409d5469aed47d19e7908d19bd194493aThomas Graf bool isSimple() const; 30144d362409d5469aed47d19e7908d19bd194493aThomas Graf 30244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Returns the name of the Region. 30344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The Name of the Region. 30444d362409d5469aed47d19e7908d19bd194493aThomas Graf std::string getNameStr() const; 30544d362409d5469aed47d19e7908d19bd194493aThomas Graf 30644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Return the RegionInfo object, that belongs to this Region. 30744d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionInfo *getRegionInfo() const { 30844d362409d5469aed47d19e7908d19bd194493aThomas Graf return RI; 30944d362409d5469aed47d19e7908d19bd194493aThomas Graf } 31044d362409d5469aed47d19e7908d19bd194493aThomas Graf 31144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Print the region. 31244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 31344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param OS The output stream the Region is printed to. 31444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param printTree Print also the tree of subregions. 31544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param level The indentation level used for printing. 31644d362409d5469aed47d19e7908d19bd194493aThomas Graf void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const; 31744d362409d5469aed47d19e7908d19bd194493aThomas Graf 31844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Print the region to stderr. 31944d362409d5469aed47d19e7908d19bd194493aThomas Graf void dump() const; 32044d362409d5469aed47d19e7908d19bd194493aThomas Graf 32144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Check if the region contains a BasicBlock. 32244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 32344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The BasicBlock that might be contained in this Region. 32444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if the block is contained in the region otherwise false. 32544d362409d5469aed47d19e7908d19bd194493aThomas Graf bool contains(const BasicBlock *BB) const; 32644d362409d5469aed47d19e7908d19bd194493aThomas Graf 32744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Check if the region contains another region. 32844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 32944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param SubRegion The region that might be contained in this Region. 33044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if SubRegion is contained in the region otherwise false. 33144d362409d5469aed47d19e7908d19bd194493aThomas Graf bool contains(const Region *SubRegion) const { 33244d362409d5469aed47d19e7908d19bd194493aThomas Graf // Toplevel Region. 33344d362409d5469aed47d19e7908d19bd194493aThomas Graf if (!getExit()) 33444d362409d5469aed47d19e7908d19bd194493aThomas Graf return true; 33544d362409d5469aed47d19e7908d19bd194493aThomas Graf 33644d362409d5469aed47d19e7908d19bd194493aThomas Graf return contains(SubRegion->getEntry()) 33744d362409d5469aed47d19e7908d19bd194493aThomas Graf && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit()); 33844d362409d5469aed47d19e7908d19bd194493aThomas Graf } 33944d362409d5469aed47d19e7908d19bd194493aThomas Graf 34044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Check if the region contains an Instruction. 34144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 34244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Inst The Instruction that might be contained in this region. 34344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if the Instruction is contained in the region otherwise false. 34444d362409d5469aed47d19e7908d19bd194493aThomas Graf bool contains(const Instruction *Inst) const { 34544d362409d5469aed47d19e7908d19bd194493aThomas Graf return contains(Inst->getParent()); 34644d362409d5469aed47d19e7908d19bd194493aThomas Graf } 34744d362409d5469aed47d19e7908d19bd194493aThomas Graf 34844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Check if the region contains a loop. 34944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 35044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param L The loop that might be contained in this region. 35144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return True if the loop is contained in the region otherwise false. 35244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// In case a NULL pointer is passed to this function the result 35344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// is false, except for the region that describes the whole function. 35444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// In that case true is returned. 35544d362409d5469aed47d19e7908d19bd194493aThomas Graf bool contains(const Loop *L) const; 35644d362409d5469aed47d19e7908d19bd194493aThomas Graf 35744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the outermost loop in the region that contains a loop. 35844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 35944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Find for a Loop L the outermost loop OuterL that is a parent loop of L 36044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// and is itself contained in the region. 36144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 36244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param L The loop the lookup is started. 36344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The outermost loop in the region, NULL if such a loop does not 36444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// exist or if the region describes the whole function. 36544d362409d5469aed47d19e7908d19bd194493aThomas Graf Loop *outermostLoopInRegion(Loop *L) const; 36644d362409d5469aed47d19e7908d19bd194493aThomas Graf 36744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the outermost loop in the region that contains a basic block. 36844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 36944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Find for a basic block BB the outermost loop L that contains BB and is 37044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// itself contained in the region. 37144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 37244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param LI A pointer to a LoopInfo analysis. 37344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The basic block surrounded by the loop. 37444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The outermost loop in the region, NULL if such a loop does not 37544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// exist or if the region describes the whole function. 37644d362409d5469aed47d19e7908d19bd194493aThomas Graf Loop *outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const; 37744d362409d5469aed47d19e7908d19bd194493aThomas Graf 37844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the subregion that starts at a BasicBlock 37944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 38044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The BasicBlock the subregion should start. 38144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The Subregion if available, otherwise NULL. 38244d362409d5469aed47d19e7908d19bd194493aThomas Graf Region* getSubRegionNode(BasicBlock *BB) const; 38344d362409d5469aed47d19e7908d19bd194493aThomas Graf 38444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the RegionNode for a BasicBlock 38544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 38644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The BasicBlock at which the RegionNode should start. 38744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return If available, the RegionNode that represents the subregion 38844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// starting at BB. If no subregion starts at BB, the RegionNode 38944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// representing BB. 39044d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionNode* getNode(BasicBlock *BB) const; 39144d362409d5469aed47d19e7908d19bd194493aThomas Graf 39244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Get the BasicBlock RegionNode for a BasicBlock 39344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 39444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The BasicBlock for which the RegionNode is requested. 39544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The RegionNode representing the BB. 39644d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionNode* getBBNode(BasicBlock *BB) const; 39744d362409d5469aed47d19e7908d19bd194493aThomas Graf 39844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Add a new subregion to this Region. 39944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 40044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param SubRegion The new subregion that will be added. 40144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param moveChildren Move the children of this region, that are also 40244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// contained in SubRegion into SubRegion. 40344d362409d5469aed47d19e7908d19bd194493aThomas Graf void addSubRegion(Region *SubRegion, bool moveChildren = false); 40444d362409d5469aed47d19e7908d19bd194493aThomas Graf 40544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Remove a subregion from this Region. 40644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 40744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// The subregion is not deleted, as it will probably be inserted into another 40844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// region. 40944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param SubRegion The SubRegion that will be removed. 41044d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *removeSubRegion(Region *SubRegion); 41144d362409d5469aed47d19e7908d19bd194493aThomas Graf 41244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Move all direct child nodes of this Region to another Region. 41344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 41444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param To The Region the child nodes will be transfered to. 41544d362409d5469aed47d19e7908d19bd194493aThomas Graf void transferChildrenTo(Region *To); 41644d362409d5469aed47d19e7908d19bd194493aThomas Graf 41744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Verify if the region is a correct region. 41844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 41944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Check if this is a correctly build Region. This is an expensive check, as 42044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// the complete CFG of the Region will be walked. 42144d362409d5469aed47d19e7908d19bd194493aThomas Graf void verifyRegion() const; 42244d362409d5469aed47d19e7908d19bd194493aThomas Graf 42344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Clear the cache for BB RegionNodes. 42444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 42544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// After calling this function the BasicBlock RegionNodes will be stored at 42644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// different memory locations. RegionNodes obtained before this function is 42744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// called are therefore not comparable to RegionNodes abtained afterwords. 42844d362409d5469aed47d19e7908d19bd194493aThomas Graf void clearNodeCache(); 42944d362409d5469aed47d19e7908d19bd194493aThomas Graf 43044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @name Subregion Iterators 43144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 43244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// These iterators iterator over all subregions of this Region. 43344d362409d5469aed47d19e7908d19bd194493aThomas Graf //@{ 43444d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef RegionSet::iterator iterator; 43544d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef RegionSet::const_iterator const_iterator; 43644d362409d5469aed47d19e7908d19bd194493aThomas Graf 43744d362409d5469aed47d19e7908d19bd194493aThomas Graf iterator begin() { return children.begin(); } 43844d362409d5469aed47d19e7908d19bd194493aThomas Graf iterator end() { return children.end(); } 43944d362409d5469aed47d19e7908d19bd194493aThomas Graf 44044d362409d5469aed47d19e7908d19bd194493aThomas Graf const_iterator begin() const { return children.begin(); } 44144d362409d5469aed47d19e7908d19bd194493aThomas Graf const_iterator end() const { return children.end(); } 44244d362409d5469aed47d19e7908d19bd194493aThomas Graf //@} 44344d362409d5469aed47d19e7908d19bd194493aThomas Graf 44444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @name BasicBlock Iterators 44544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 44644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// These iterators iterate over all BasicBlock RegionNodes that are 44744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// contained in this Region. The iterator also iterates over BasicBlocks 44844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// that are elements of a subregion of this Region. It is therefore called a 44944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// flat iterator. 45044d362409d5469aed47d19e7908d19bd194493aThomas Graf //@{ 45144d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, 45244d362409d5469aed47d19e7908d19bd194493aThomas Graf GraphTraits<FlatIt<RegionNode*> > > block_iterator; 45344d362409d5469aed47d19e7908d19bd194493aThomas Graf 45444d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, 45544d362409d5469aed47d19e7908d19bd194493aThomas Graf false, GraphTraits<FlatIt<const RegionNode*> > > 45644d362409d5469aed47d19e7908d19bd194493aThomas Graf const_block_iterator; 45744d362409d5469aed47d19e7908d19bd194493aThomas Graf 45844d362409d5469aed47d19e7908d19bd194493aThomas Graf block_iterator block_begin(); 45944d362409d5469aed47d19e7908d19bd194493aThomas Graf block_iterator block_end(); 46044d362409d5469aed47d19e7908d19bd194493aThomas Graf 46144d362409d5469aed47d19e7908d19bd194493aThomas Graf const_block_iterator block_begin() const; 46244d362409d5469aed47d19e7908d19bd194493aThomas Graf const_block_iterator block_end() const; 46344d362409d5469aed47d19e7908d19bd194493aThomas Graf //@} 46444d362409d5469aed47d19e7908d19bd194493aThomas Graf 46544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @name Element Iterators 46644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 46744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// These iterators iterate over all BasicBlock and subregion RegionNodes that 46844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// are direct children of this Region. It does not iterate over any 46944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// RegionNodes that are also element of a subregion of this Region. 47044d362409d5469aed47d19e7908d19bd194493aThomas Graf //@{ 47144d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, 47244d362409d5469aed47d19e7908d19bd194493aThomas Graf GraphTraits<RegionNode*> > element_iterator; 47344d362409d5469aed47d19e7908d19bd194493aThomas Graf 47444d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, 47544d362409d5469aed47d19e7908d19bd194493aThomas Graf false, GraphTraits<const RegionNode*> > 47644d362409d5469aed47d19e7908d19bd194493aThomas Graf const_element_iterator; 47744d362409d5469aed47d19e7908d19bd194493aThomas Graf 47844d362409d5469aed47d19e7908d19bd194493aThomas Graf element_iterator element_begin(); 4795d92f9c03d85cefee5afe7f40d7ea69dfde4cf77Thomas Graf element_iterator element_end(); 4805d92f9c03d85cefee5afe7f40d7ea69dfde4cf77Thomas Graf 48144d362409d5469aed47d19e7908d19bd194493aThomas Graf const_element_iterator element_begin() const; 48244d362409d5469aed47d19e7908d19bd194493aThomas Graf const_element_iterator element_end() const; 48344d362409d5469aed47d19e7908d19bd194493aThomas Graf //@} 48444d362409d5469aed47d19e7908d19bd194493aThomas Graf}; 48544d362409d5469aed47d19e7908d19bd194493aThomas Graf 48644d362409d5469aed47d19e7908d19bd194493aThomas Graf//===----------------------------------------------------------------------===// 48744d362409d5469aed47d19e7908d19bd194493aThomas Graf/// @brief Analysis that detects all canonical Regions. 48844d362409d5469aed47d19e7908d19bd194493aThomas Graf/// 48944d362409d5469aed47d19e7908d19bd194493aThomas Graf/// The RegionInfo pass detects all canonical regions in a function. The Regions 49044d362409d5469aed47d19e7908d19bd194493aThomas Graf/// are connected using the parent relation. This builds a Program Structure 49144d362409d5469aed47d19e7908d19bd194493aThomas Graf/// Tree. 49244d362409d5469aed47d19e7908d19bd194493aThomas Grafclass RegionInfo : public FunctionPass { 49344d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap; 49444d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap; 49544d362409d5469aed47d19e7908d19bd194493aThomas Graf typedef SmallPtrSet<Region*, 4> RegionSet; 49644d362409d5469aed47d19e7908d19bd194493aThomas Graf 49744d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 49844d362409d5469aed47d19e7908d19bd194493aThomas Graf RegionInfo(const RegionInfo &); 49944d362409d5469aed47d19e7908d19bd194493aThomas Graf // DO NOT IMPLEMENT 50044d362409d5469aed47d19e7908d19bd194493aThomas Graf const RegionInfo &operator=(const RegionInfo &); 50144d362409d5469aed47d19e7908d19bd194493aThomas Graf 50244d362409d5469aed47d19e7908d19bd194493aThomas Graf DominatorTree *DT; 50344d362409d5469aed47d19e7908d19bd194493aThomas Graf PostDominatorTree *PDT; 50444d362409d5469aed47d19e7908d19bd194493aThomas Graf DominanceFrontier *DF; 50544d362409d5469aed47d19e7908d19bd194493aThomas Graf 50644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// The top level region. 50744d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *TopLevelRegion; 50844d362409d5469aed47d19e7908d19bd194493aThomas Graf 50944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// Map every BB to the smallest region, that contains BB. 51044d362409d5469aed47d19e7908d19bd194493aThomas Graf BBtoRegionMap BBtoRegion; 51144d362409d5469aed47d19e7908d19bd194493aThomas Graf 51244d362409d5469aed47d19e7908d19bd194493aThomas Graf // isCommonDomFrontier - Returns true if BB is in the dominance frontier of 51344d362409d5469aed47d19e7908d19bd194493aThomas Graf // entry, because it was inherited from exit. In the other case there is an 51444d362409d5469aed47d19e7908d19bd194493aThomas Graf // edge going from entry to BB without passing exit. 51544d362409d5469aed47d19e7908d19bd194493aThomas Graf bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry, 51644d362409d5469aed47d19e7908d19bd194493aThomas Graf BasicBlock* exit) const; 51744d362409d5469aed47d19e7908d19bd194493aThomas Graf 51844d362409d5469aed47d19e7908d19bd194493aThomas Graf // isRegion - Check if entry and exit surround a valid region, based on 51944d362409d5469aed47d19e7908d19bd194493aThomas Graf // dominance tree and dominance frontier. 52044d362409d5469aed47d19e7908d19bd194493aThomas Graf bool isRegion(BasicBlock* entry, BasicBlock* exit) const; 52144d362409d5469aed47d19e7908d19bd194493aThomas Graf 52244d362409d5469aed47d19e7908d19bd194493aThomas Graf // insertShortCut - Saves a shortcut pointing from entry to exit. 52344d362409d5469aed47d19e7908d19bd194493aThomas Graf // This function may extend this shortcut if possible. 52444d362409d5469aed47d19e7908d19bd194493aThomas Graf void insertShortCut(BasicBlock* entry, BasicBlock* exit, 52544d362409d5469aed47d19e7908d19bd194493aThomas Graf BBtoBBMap* ShortCut) const; 52644d362409d5469aed47d19e7908d19bd194493aThomas Graf 52744d362409d5469aed47d19e7908d19bd194493aThomas Graf // getNextPostDom - Returns the next BB that postdominates N, while skipping 52844d362409d5469aed47d19e7908d19bd194493aThomas Graf // all post dominators that cannot finish a canonical region. 52944d362409d5469aed47d19e7908d19bd194493aThomas Graf DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const; 53044d362409d5469aed47d19e7908d19bd194493aThomas Graf 53144d362409d5469aed47d19e7908d19bd194493aThomas Graf // isTrivialRegion - A region is trivial, if it contains only one BB. 53244d362409d5469aed47d19e7908d19bd194493aThomas Graf bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const; 53344d362409d5469aed47d19e7908d19bd194493aThomas Graf 53444d362409d5469aed47d19e7908d19bd194493aThomas Graf // createRegion - Creates a single entry single exit region. 53544d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *createRegion(BasicBlock *entry, BasicBlock *exit); 53644d362409d5469aed47d19e7908d19bd194493aThomas Graf 53744d362409d5469aed47d19e7908d19bd194493aThomas Graf // findRegionsWithEntry - Detect all regions starting with bb 'entry'. 53844d362409d5469aed47d19e7908d19bd194493aThomas Graf void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut); 53944d362409d5469aed47d19e7908d19bd194493aThomas Graf 54044d362409d5469aed47d19e7908d19bd194493aThomas Graf // scanForRegions - Detects regions in F. 54144d362409d5469aed47d19e7908d19bd194493aThomas Graf void scanForRegions(Function &F, BBtoBBMap *ShortCut); 54244d362409d5469aed47d19e7908d19bd194493aThomas Graf 54344d362409d5469aed47d19e7908d19bd194493aThomas Graf // getTopMostParent - Get the top most parent with the same entry block. 54444d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *getTopMostParent(Region *region); 54544d362409d5469aed47d19e7908d19bd194493aThomas Graf 54644d362409d5469aed47d19e7908d19bd194493aThomas Graf // buildRegionsTree - build the region hierarchy after all region detected. 54744d362409d5469aed47d19e7908d19bd194493aThomas Graf void buildRegionsTree(DomTreeNode *N, Region *region); 54844d362409d5469aed47d19e7908d19bd194493aThomas Graf 54944d362409d5469aed47d19e7908d19bd194493aThomas Graf // Calculate - detecte all regions in function and build the region tree. 55044d362409d5469aed47d19e7908d19bd194493aThomas Graf void Calculate(Function& F); 55144d362409d5469aed47d19e7908d19bd194493aThomas Graf 55244d362409d5469aed47d19e7908d19bd194493aThomas Graf void releaseMemory(); 55344d362409d5469aed47d19e7908d19bd194493aThomas Graf 55444d362409d5469aed47d19e7908d19bd194493aThomas Graf // updateStatistics - Update statistic about created regions. 55544d362409d5469aed47d19e7908d19bd194493aThomas Graf void updateStatistics(Region *R); 55644d362409d5469aed47d19e7908d19bd194493aThomas Graf 55744d362409d5469aed47d19e7908d19bd194493aThomas Graf // isSimple - Check if a region is a simple region with exactly one entry 55844d362409d5469aed47d19e7908d19bd194493aThomas Graf // edge and exactly one exit edge. 55944d362409d5469aed47d19e7908d19bd194493aThomas Graf bool isSimple(Region* R) const; 56044d362409d5469aed47d19e7908d19bd194493aThomas Graf 56144d362409d5469aed47d19e7908d19bd194493aThomas Grafpublic: 56244d362409d5469aed47d19e7908d19bd194493aThomas Graf static char ID; 56344d362409d5469aed47d19e7908d19bd194493aThomas Graf explicit RegionInfo(); 56444d362409d5469aed47d19e7908d19bd194493aThomas Graf 56544d362409d5469aed47d19e7908d19bd194493aThomas Graf ~RegionInfo(); 56644d362409d5469aed47d19e7908d19bd194493aThomas Graf 56744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @name FunctionPass interface 56844d362409d5469aed47d19e7908d19bd194493aThomas Graf //@{ 56944d362409d5469aed47d19e7908d19bd194493aThomas Graf virtual bool runOnFunction(Function &F); 57044d362409d5469aed47d19e7908d19bd194493aThomas Graf virtual void getAnalysisUsage(AnalysisUsage &AU) const; 571241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar virtual void print(raw_ostream &OS, const Module *) const; 572241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar virtual void verifyAnalysis() const; 573241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar //@} 574241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar 575241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// @brief Get the smallest region that contains a BasicBlock. 576241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// 577241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// @param BB The basic block. 578241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// @return The smallest region, that contains BB or NULL, if there is no 579241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// region containing BB. 580241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar Region *getRegionFor(BasicBlock *BB) const; 581241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar 582241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// @brief Set the smallest region that surrounds a basic block. 58344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 58444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The basic block surrounded by a region. 58544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param R The smallest region that surrounds BB. 58644d362409d5469aed47d19e7908d19bd194493aThomas Graf void setRegionFor(BasicBlock *BB, Region *R); 58744d362409d5469aed47d19e7908d19bd194493aThomas Graf 58844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief A shortcut for getRegionFor(). 58944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 59044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The basic block. 59144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The smallest region, that contains BB or NULL, if there is no 59244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// region containing BB. 59344d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *operator[](BasicBlock *BB) const; 594241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar 595241b2b83ba5672f5c86154d29eeb8ef4c7c6e9b4Tad Kollar /// @brief Return the exit of the maximal refined region, that starts at a 59644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// BasicBlock. 59744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 59844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BB The BasicBlock the refined region starts. 59944d362409d5469aed47d19e7908d19bd194493aThomas Graf BasicBlock *getMaxRegionExit(BasicBlock *BB) const; 60044d362409d5469aed47d19e7908d19bd194493aThomas Graf 60144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Find the smallest region that contains two regions. 60244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 60344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param A The first region. 60444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param B The second region. 60544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The smallest region containing A and B. 60644d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *getCommonRegion(Region* A, Region *B) const; 60744d362409d5469aed47d19e7908d19bd194493aThomas Graf 60844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Find the smallest region that contains two basic blocks. 60944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 61044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param A The first basic block. 61144d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param B The second basic block. 61244d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The smallest region that contains A and B. 61344d362409d5469aed47d19e7908d19bd194493aThomas Graf Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const { 61444d362409d5469aed47d19e7908d19bd194493aThomas Graf return getCommonRegion(getRegionFor(A), getRegionFor(B)); 61544d362409d5469aed47d19e7908d19bd194493aThomas Graf } 61644d362409d5469aed47d19e7908d19bd194493aThomas Graf 61744d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Find the smallest region that contains a set of regions. 61844d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 61944d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param Regions A vector of regions. 62044d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The smallest region that contains all regions in Regions. 62144d362409d5469aed47d19e7908d19bd194493aThomas Graf Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const; 62244d362409d5469aed47d19e7908d19bd194493aThomas Graf 62344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Find the smallest region that contains a set of basic blocks. 62444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 62544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @param BBs A vector of basic blocks. 62644d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @return The smallest region that contains all basic blocks in BBS. 62744d362409d5469aed47d19e7908d19bd194493aThomas Graf Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const; 62844d362409d5469aed47d19e7908d19bd194493aThomas Graf 62944d362409d5469aed47d19e7908d19bd194493aThomas Graf Region *getTopLevelRegion() const { 63044d362409d5469aed47d19e7908d19bd194493aThomas Graf return TopLevelRegion; 63144d362409d5469aed47d19e7908d19bd194493aThomas Graf } 63244d362409d5469aed47d19e7908d19bd194493aThomas Graf 63344d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @brief Clear the Node Cache for all Regions. 63444d362409d5469aed47d19e7908d19bd194493aThomas Graf /// 63544d362409d5469aed47d19e7908d19bd194493aThomas Graf /// @see Region::clearNodeCache() 63644d362409d5469aed47d19e7908d19bd194493aThomas Graf void clearNodeCache() { 63744d362409d5469aed47d19e7908d19bd194493aThomas Graf if (TopLevelRegion) 63844d362409d5469aed47d19e7908d19bd194493aThomas Graf TopLevelRegion->clearNodeCache(); 63944d362409d5469aed47d19e7908d19bd194493aThomas Graf } 64044d362409d5469aed47d19e7908d19bd194493aThomas Graf}; 64144d362409d5469aed47d19e7908d19bd194493aThomas Graf 64244d362409d5469aed47d19e7908d19bd194493aThomas Grafinline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) { 64344d362409d5469aed47d19e7908d19bd194493aThomas Graf if (Node.isSubRegion()) 64444d362409d5469aed47d19e7908d19bd194493aThomas Graf return OS << Node.getNodeAs<Region>()->getNameStr(); 64544d362409d5469aed47d19e7908d19bd194493aThomas Graf else 64644d362409d5469aed47d19e7908d19bd194493aThomas Graf return OS << Node.getNodeAs<BasicBlock>()->getNameStr(); 64744d362409d5469aed47d19e7908d19bd194493aThomas Graf} 64844d362409d5469aed47d19e7908d19bd194493aThomas Graf} // End llvm namespace 64944d362409d5469aed47d19e7908d19bd194493aThomas Graf#endif 65044d362409d5469aed47d19e7908d19bd194493aThomas Graf 65144d362409d5469aed47d19e7908d19bd194493aThomas Graf