1f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// 2f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 3f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// The LLVM Compiler Infrastructure 4f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 5f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// This file is distributed under the University of Illinois Open Source 6f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// License. See LICENSE.TXT for details. 7f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 8f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 9f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 10f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Calculate a program structure tree built out of single entry single exit 11f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// regions. 12f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// The basic ideas are taken from "The Program Structure Tree - Richard Johnson, 13f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The 14f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana 15f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Koehler - 2009". 16f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// The algorithm to calculate these data structures however is completely 17f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// different, as it takes advantage of existing information already available 18f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// in (Post)dominace tree and dominance frontier passes. This leads to a simpler 19f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// and in practice hopefully better performing algorithm. The runtime of the 20f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// algorithms described in the papers above are both linear in graph size, 21f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// O(V+E), whereas this algorithm is not, as the dominance frontier information 22f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// itself is not, but in practice runtime seems to be in the order of magnitude 23f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// of dominance tree calculation. 24f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 25c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// WARNING: LLVM is generally very concerned about compile time such that 26c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// the use of additional analysis passes in the default 27c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// optimization sequence is avoided as much as possible. 28c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// Specifically, if you do not need the RegionInfo, but dominance 29c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// information could be sufficient please base your work only on 30c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// the dominator tree. Most passes maintain it, such that using 31c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// it has often near zero cost. In contrast RegionInfo is by 32c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// default not available, is not maintained by existing 33c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// transformations and there is no intention to do so. 34c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines// 35f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 36f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 37674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_REGIONINFO_H 38674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_REGIONINFO_H 39f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 4037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/DepthFirstIterator.h" 41f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/ADT/PointerIntPair.h" 4237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/IR/CFG.h" 4337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/IR/Dominators.h" 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/PassManager.h" 451a8b9dd7fb945ab78232f3853219cc693bcb5fadChris Lattner#include <map> 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <memory> 4737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <set> 48f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 49f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grossernamespace llvm { 50f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 51f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// Class to be specialized for different users of RegionInfo 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// pass around an unreasonable number of template parameters. 5437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class FuncT_> 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct RegionTraits { 5637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // FuncT 5737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // BlockT 5837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // RegionT 5937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // RegionNodeT 6037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // RegionInfoT 6137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename FuncT_::UnknownRegionTypeError BrokenT; 6237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 6337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass DominatorTree; 6537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass DominanceFrontier; 66082d587d35a41ee06985d7867b72fb2632962281Tobias Grosserclass Loop; 67082d587d35a41ee06985d7867b72fb2632962281Tobias Grosserclass LoopInfo; 6837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct PostDominatorTree; 6937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass raw_ostream; 7037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass Region; 7137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class RegionTr> 7237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionBase; 7337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionNode; 7437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionInfo; 7537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class RegionTr> 7637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionInfoBase; 7737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 7837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <> 7937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct RegionTraits<Function> { 8037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef Function FuncT; 8137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef BasicBlock BlockT; 8237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef Region RegionT; 8337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef RegionNode RegionNodeT; 8437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef RegionInfo RegionInfoT; 8537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominatorTree DomTreeT; 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DomTreeNode DomTreeNodeT; 8737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DominanceFrontier DomFrontierT; 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef PostDominatorTree PostDomTreeT; 8937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef Instruction InstT; 9037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef Loop LoopT; 9137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef LoopInfo LoopInfoT; 9237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 9337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static unsigned getNumSuccessors(BasicBlock *BB) { 9437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BB->getTerminator()->getNumSuccessors(); 9537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 9637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 97f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 98f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// @brief Marker class to iterate over the elements of a Region in flat mode. 99f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 100f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The class is used to either iterate in Flat mode or by not using it to not 101f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// iterate in Flat mode. During a Flat mode iteration all Regions are entered 102f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// and the iteration returns every BasicBlock. If the Flat mode is not 103f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// selected for SubRegions just one RegionNode containing the subregion is 104f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// returned. 105f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grossertemplate <class GraphType> 106f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserclass FlatIt {}; 107f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 108f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a 109f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Region. 11037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 11137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionNodeBase { 11237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines friend class RegionBase<Tr>; 11337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::BlockT BlockT; 11637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionT RegionT; 11737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprivate: 119ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RegionNodeBase(const RegionNodeBase &) = delete; 120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const RegionNodeBase &operator=(const RegionNodeBase &) = delete; 121f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 122f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// This is the entry basic block that starts this region node. If this is a 123f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// BasicBlock RegionNode, then entry is just the basic block, that this 124f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. 125f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 126f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// In the BBtoRegionNode map of the parent of this node, BB will always map 127f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// to this node no matter which kind of node this one is. 128f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 129f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// The node can hold either a Region or a BasicBlock. 130f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Use one bit to save, if this RegionNode is a subregion or BasicBlock 131f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// RegionNode. 13237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PointerIntPair<BlockT *, 1, bool> entry; 133f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 134f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief The parent Region of this RegionNode. 135f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @see getParent() 13637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *parent; 137f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 13837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprotected: 139f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Create a RegionNode. 140f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 141f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Parent The parent of this RegionNode. 142f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Entry The entry BasicBlock of the RegionNode. If this 143f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// RegionNode represents a BasicBlock, this is the 144f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// BasicBlock itself. If it represents a subregion, this 145f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// is the entry BasicBlock of the subregion. 146f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param isSubRegion If this RegionNode represents a SubRegion. 14737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline RegionNodeBase(RegionT *Parent, BlockT *Entry, 14837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isSubRegion = false) 14937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : entry(Entry, isSubRegion), parent(Parent) {} 150f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 15137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 152f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the parent Region of this RegionNode. 153f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 154f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// The parent Region is the Region this RegionNode belongs to. If for 155f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// example a BasicBlock is element of two Regions, there exist two 156f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// RegionNodes for this BasicBlock. Each with the getParent() function 157f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// pointing to the Region this RegionNode belongs to. 158f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 159f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return Get the parent Region of this RegionNode. 16037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline RegionT *getParent() const { return parent; } 161f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 162f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the entry BasicBlock of this RegionNode. 163f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 164f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// If this RegionNode represents a BasicBlock this is just the BasicBlock 165f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// itself, otherwise we return the entry BasicBlock of the Subregion 166f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 167f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The entry BasicBlock of this RegionNode. 16837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline BlockT *getEntry() const { return entry.getPointer(); } 169f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 170f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the content of this RegionNode. 171f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 172f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() 173f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// check the type of the content with the isSubRegion() function call. 174f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 175f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The content of this RegionNode. 17637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines template <class T> inline T *getNodeAs() const; 177f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 178f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Is this RegionNode a subregion? 179f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 180f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return True if it contains a subregion. False if it contains a 181f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// BasicBlock. 18237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline bool isSubRegion() const { return entry.getInt(); } 183f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser}; 184f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 185f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 186f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// @brief A single entry single exit Region. 187f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 188f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// A Region is a connected subgraph of a control flow graph that has exactly 189f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// two connections to the remaining graph. It can be used to analyze or 190f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// optimize parts of the control flow graph. 191f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 1927a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// A <em> simple Region </em> is connected to the remaining graph by just two 193f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// edges. One edge entering the Region and another one leaving the Region. 194f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 195f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// An <em> extended Region </em> (or just Region) is a subgraph that can be 196f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// transform into a simple Region. The transformation is done by adding 197f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// BasicBlocks that merge several entry or exit edges so that after the merge 198f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// just one entry and one exit edge exists. 199f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 200f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The \e Entry of a Region is the first BasicBlock that is passed after 201f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// entering the Region. It is an element of the Region. The entry BasicBlock 202f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// dominates all BasicBlocks in the Region. 203f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 204f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The \e Exit of a Region is the first BasicBlock that is passed after 205f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// leaving the Region. It is not an element of the Region. The exit BasicBlock, 206f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// postdominates all BasicBlocks in the Region. 207f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 208f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// A <em> canonical Region </em> cannot be constructed by combining smaller 209f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Regions. 210f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 211f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Region A is the \e parent of Region B, if B is completely contained in A. 212f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 213f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Two canonical Regions either do not intersect at all or one is 214f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// the parent of the other. 215f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 216f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of 217f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Regions in the control flow graph and E is the \e parent relation of these 218f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Regions. 219f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 220f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Example: 221f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 222f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// \verbatim 223f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// A simple control flow graph, that contains two regions. 224f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 225f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 1 226f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// / | 227f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 2 | 228f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// / \ 3 229f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 4 5 | 230f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// | | | 231f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 6 7 8 232f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// \ | / 233f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} 234f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 9 Region B: 2 -> 9 {2,4,5,6,7} 235f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// \endverbatim 236f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 237f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// You can obtain more examples by either calling 238f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 239f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// <tt> "opt -regions -analyze anyprogram.ll" </tt> 240f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// or 241f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// <tt> "opt -view-regions-only anyprogram.ll" </tt> 242f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 243f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// on any LLVM file you are interested in. 244f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 245f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The first call returns a textual representation of the program structure 246f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// tree, the second one creates a graphical representation using graphviz. 24737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 24837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionBase : public RegionNodeBase<Tr> { 24937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::FuncT FuncT; 25037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::BlockT BlockT; 25137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionInfoT RegionInfoT; 25237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionT RegionT; 25337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionNodeT RegionNodeT; 25437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::DomTreeT DomTreeT; 25537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::LoopT LoopT; 25637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::LoopInfoT LoopInfoT; 25737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::InstT InstT; 25837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 25937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<BlockT *> BlockTraits; 26037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; 26137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename BlockTraits::ChildIteratorType SuccIterTy; 26237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename InvBlockTraits::ChildIteratorType PredIterTy; 26337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 26437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines friend class RegionInfoBase<Tr>; 265ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RegionBase(const RegionBase &) = delete; 266ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const RegionBase &operator=(const RegionBase &) = delete; 267f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 268f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Information necessary to manage this Region. 26937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionInfoT *RI; 27037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomTreeT *DT; 271f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 272f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // The exit BasicBlock of this region. 273f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // (The entry BasicBlock is part of RegionNode) 27437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit; 275f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 27637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef std::vector<std::unique_ptr<RegionT>> RegionSet; 277f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 278f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // The subregions of this region. 279f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser RegionSet children; 280f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 28137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef std::map<BlockT *, RegionNodeT *> BBNodeMapT; 282f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 283f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Save the BasicBlock RegionNodes that are element of this Region. 284f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser mutable BBNodeMapT BBNodeMap; 285f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 286f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Check if a BB is in this Region. This check also works 287f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// if the region is incorrectly built. (EXPENSIVE!) 28837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void verifyBBInRegion(BlockT *BB) const; 289f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 290f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Walk over all the BBs of the region starting from BB and 291f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// verify that all reachable basic blocks are elements of the region. 292f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// (EXPENSIVE!) 29337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const; 294f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Verify if the region and its children are valid regions (EXPENSIVE!) 296f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser void verifyRegionNest() const; 297f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 298f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserpublic: 299f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Create a new region. 300f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 301f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Entry The entry basic block of the region. 302f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Exit The exit basic block of the region. 303f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param RI The region info object that is managing this region. 304f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param DT The dominator tree of the current function. 305f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Parent The surrounding region or NULL if this is a top level 306f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// region. 30737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, 30837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *Parent = nullptr); 309f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 310f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Delete the Region and all its subregions. 31137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ~RegionBase(); 312f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 313f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the entry BasicBlock of the Region. 314f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The entry BasicBlock of the region. 31537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getEntry() const { 31637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return RegionNodeBase<Tr>::getEntry(); 31737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 318f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 3194bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// @brief Replace the entry basic block of the region with the new basic 3204bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// block. 3214bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// 3224bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// @param BB The new entry basic block of the region. 32337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void replaceEntry(BlockT *BB); 3244bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser 3254bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// @brief Replace the exit basic block of the region with the new basic 3264bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// block. 3274bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// 3284bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser /// @param BB The new exit basic block of the region. 32937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void replaceExit(BlockT *BB); 3304bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser 331d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// @brief Recursively replace the entry basic block of the region. 332d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// 333d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// This function replaces the entry basic block with a new basic block. It 334d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// also updates all child regions that have the same entry basic block as 335d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// this region. 336d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// 337d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// @param NewEntry The new entry basic block. 33837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void replaceEntryRecursive(BlockT *NewEntry); 339d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser 340d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// @brief Recursively replace the exit basic block of the region. 341d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// 342d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// This function replaces the exit basic block with a new basic block. It 343d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// also updates all child regions that have the same exit basic block as 344d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// this region. 345d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// 346d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser /// @param NewExit The new exit basic block. 34737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void replaceExitRecursive(BlockT *NewExit); 348d03fdfb97c1a693101bfef5800c262237f5d382fTobias Grosser 349f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the exit BasicBlock of the Region. 350f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel 351f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Region. 35237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getExit() const { return exit; } 353f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 354f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the parent of the Region. 355f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The parent of the Region or NULL if this is a top level 356f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Region. 35737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getParent() const { 35837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return RegionNodeBase<Tr>::getParent(); 35937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 360f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 361f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the RegionNode representing the current Region. 362f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The RegionNode representing the current Region. 36337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionNodeT *getNode() const { 36437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return const_cast<RegionNodeT *>( 36537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines reinterpret_cast<const RegionNodeT *>(this)); 366f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 367f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 368f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the nesting level of this Region. 369f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 370f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// An toplevel Region has depth 0. 371f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 372f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The depth of the region. 373f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser unsigned getDepth() const; 374f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 375b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser /// @brief Check if a Region is the TopLevel region. 376b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser /// 377b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser /// The toplevel region represents the whole function. 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isTopLevelRegion() const { return exit == nullptr; } 379b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser 38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// @brief Return a new (non-canonical) region, that is obtained by joining 381c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser /// this region with its predecessors. 382c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser /// 383c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser /// @return A region also starting at getEntry(), but reaching to the next 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// basic block that forms with getEntry() a (non-canonical) region. 385c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser /// NULL if such a basic block does not exist. 38637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getExpandedRegion() const; 387c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 38821d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// @brief Return the first block of this region's single entry edge, 38921d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// if existing. 39021d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// 39121d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// @return The BasicBlock starting this region's single entry edge, 39221d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// else NULL. 39337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getEnteringBlock() const; 39421d842c35326281798f685661b88dedcd09c13aaTobias Grosser 39521d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// @brief Return the first block of this region's single exit edge, 39621d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// if existing. 39721d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// 39821d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// @return The BasicBlock starting this region's single exit edge, 39921d842c35326281798f685661b88dedcd09c13aaTobias Grosser /// else NULL. 40037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getExitingBlock() const; 40121d842c35326281798f685661b88dedcd09c13aaTobias Grosser 402f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Is this a simple region? 403f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 404f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// A region is simple if it has exactly one exit and one entry edge. 405f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 406f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return True if the Region is simple. 407f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser bool isSimple() const; 408f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 409f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Returns the name of the Region. 410f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The Name of the Region. 411082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser std::string getNameStr() const; 412f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 413f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Return the RegionInfo object, that belongs to this Region. 41437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionInfoT *getRegionInfo() const { return RI; } 415f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 416cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser /// PrintStyle - Print region in difference ways. 41737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines enum PrintStyle { PrintNone, PrintBB, PrintRN }; 418cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser 419f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Print the region. 420f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 421f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param OS The output stream the Region is printed to. 422f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param printTree Print also the tree of subregions. 423f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param level The indentation level used for printing. 42437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void print(raw_ostream &OS, bool printTree = true, unsigned level = 0, 42537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PrintStyle Style = PrintNone) const; 426f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 42737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 428f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Print the region to stderr. 429f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser void dump() const; 43037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 431f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 432f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Check if the region contains a BasicBlock. 433f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 434f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The BasicBlock that might be contained in this Region. 435f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return True if the block is contained in the region otherwise false. 43637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool contains(const BlockT *BB) const; 437f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 438f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Check if the region contains another region. 439f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 440f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param SubRegion The region that might be contained in this Region. 441f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return True if SubRegion is contained in the region otherwise false. 44237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool contains(const RegionT *SubRegion) const { 443f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Toplevel Region. 444f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!getExit()) 445f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 446f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 44737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return contains(SubRegion->getEntry()) && 44837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (contains(SubRegion->getExit()) || 44937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SubRegion->getExit() == getExit()); 450f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 451f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 452f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Check if the region contains an Instruction. 453f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 454f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Inst The Instruction that might be contained in this region. 45537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// @return True if the Instruction is contained in the region otherwise 45637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// false. 45737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool contains(const InstT *Inst) const { return contains(Inst->getParent()); } 458f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 459082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @brief Check if the region contains a loop. 460082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// 461082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @param L The loop that might be contained in this region. 462082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @return True if the loop is contained in the region otherwise false. 463082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// In case a NULL pointer is passed to this function the result 464082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// is false, except for the region that describes the whole function. 465082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// In that case true is returned. 46637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool contains(const LoopT *L) const; 467082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 468082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @brief Get the outermost loop in the region that contains a loop. 469082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// 470082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// Find for a Loop L the outermost loop OuterL that is a parent loop of L 471082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// and is itself contained in the region. 472082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// 473082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @param L The loop the lookup is started. 474082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @return The outermost loop in the region, NULL if such a loop does not 475082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// exist or if the region describes the whole function. 47637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LoopT *outermostLoopInRegion(LoopT *L) const; 477082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 478082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @brief Get the outermost loop in the region that contains a basic block. 479082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// 480082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// Find for a basic block BB the outermost loop L that contains BB and is 481082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// itself contained in the region. 482082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// 483082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @param LI A pointer to a LoopInfo analysis. 484082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @param BB The basic block surrounded by the loop. 485082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// @return The outermost loop in the region, NULL if such a loop does not 486082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser /// exist or if the region describes the whole function. 48737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const; 488082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 489f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the subregion that starts at a BasicBlock 490f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 491f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The BasicBlock the subregion should start. 492f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The Subregion if available, otherwise NULL. 49337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getSubRegionNode(BlockT *BB) const; 494f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 495f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the RegionNode for a BasicBlock 496f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 497f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The BasicBlock at which the RegionNode should start. 498f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return If available, the RegionNode that represents the subregion 499f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// starting at BB. If no subregion starts at BB, the RegionNode 500f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// representing BB. 50137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionNodeT *getNode(BlockT *BB) const; 502f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 503f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the BasicBlock RegionNode for a BasicBlock 504f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 505f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The BasicBlock for which the RegionNode is requested. 506f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The RegionNode representing the BB. 50737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionNodeT *getBBNode(BlockT *BB) const; 508f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 509f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Add a new subregion to this Region. 510f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 511f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param SubRegion The new subregion that will be added. 5129649390e1fcb6d42e228364230f16409ad150fefTobias Grosser /// @param moveChildren Move the children of this region, that are also 5139649390e1fcb6d42e228364230f16409ad150fefTobias Grosser /// contained in SubRegion into SubRegion. 51437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void addSubRegion(RegionT *SubRegion, bool moveChildren = false); 515f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 516f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Remove a subregion from this Region. 517f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 518f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// The subregion is not deleted, as it will probably be inserted into another 519f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// region. 520f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param SubRegion The SubRegion that will be removed. 52137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *removeSubRegion(RegionT *SubRegion); 522f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 523f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Move all direct child nodes of this Region to another Region. 524f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 5257a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// @param To The Region the child nodes will be transferred to. 52637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void transferChildrenTo(RegionT *To); 527f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 528f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Verify if the region is a correct region. 529f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 530f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Check if this is a correctly build Region. This is an expensive check, as 531f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// the complete CFG of the Region will be walked. 532f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser void verifyRegion() const; 533f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 534f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Clear the cache for BB RegionNodes. 535f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 536f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// After calling this function the BasicBlock RegionNodes will be stored at 537f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// different memory locations. RegionNodes obtained before this function is 538f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// called are therefore not comparable to RegionNodes abtained afterwords. 539f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser void clearNodeCache(); 540f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 541f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @name Subregion Iterators 542f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 543f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// These iterators iterator over all subregions of this Region. 544f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser //@{ 54537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename RegionSet::iterator iterator; 54637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename RegionSet::const_iterator const_iterator; 547f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 548f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser iterator begin() { return children.begin(); } 549f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser iterator end() { return children.end(); } 550f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 551f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser const_iterator begin() const { return children.begin(); } 552f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser const_iterator end() const { return children.end(); } 553f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser //@} 554f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 5557c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth /// @name BasicBlock Iterators 5567c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth /// 5577c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth /// These iterators iterate over all BasicBlocks that are contained in this 5587c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth /// Region. The iterator also iterates over BasicBlocks that are elements of 5597c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth /// a subregion of this Region. It is therefore called a flat iterator. 5607c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth //@{ 561f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng template <bool IsConst> 5627c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth class block_iterator_wrapper 56337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : public df_iterator< 56437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename std::conditional<IsConst, const BlockT, BlockT>::type *> { 56537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef df_iterator< 56637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename std::conditional<IsConst, const BlockT, BlockT>::type *> super; 56736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5687c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth public: 569f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng typedef block_iterator_wrapper<IsConst> Self; 5707c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth typedef typename super::pointer pointer; 5717c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth 572f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // Construct the begin iterator. 57337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines block_iterator_wrapper(pointer Entry, pointer Exit) 57437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : super(df_begin(Entry)) { 575f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // Mark the exit of the region as visited, so that the children of the 576f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // exit and the exit itself, i.e. the block outside the region will never 577f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // be visited. 578f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng super::Visited.insert(Exit); 5797c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth } 5807c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth 581f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // Construct the end iterator. 58237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines block_iterator_wrapper() : super(df_end<pointer>((BlockT *)nullptr)) {} 583f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng 584f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng /*implicit*/ block_iterator_wrapper(super I) : super(I) {} 5857c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth 586f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. 587f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // This was introduced for backwards compatibility, but should 588f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng // be removed as soon as all users are fixed. 58937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *operator*() const { 59037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return const_cast<BlockT *>(super::operator*()); 5917c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth } 5927c52c97a2232756bbcc2fb4e664892bdb8b2d90cChandler Carruth }; 593f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 594f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng typedef block_iterator_wrapper<false> block_iterator; 59537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef block_iterator_wrapper<true> const_block_iterator; 596f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 59737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines block_iterator block_begin() { return block_iterator(getEntry(), getExit()); } 598f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng 59937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines block_iterator block_end() { return block_iterator(); } 600f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng 601f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng const_block_iterator block_begin() const { 602f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng return const_block_iterator(getEntry(), getExit()); 603f63f8834250e5bd50b1cc5b2649acdf42988abadHongbin Zheng } 60437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const_block_iterator block_end() const { return const_block_iterator(); } 60536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef iterator_range<block_iterator> block_range; 60736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef iterator_range<const_block_iterator> const_block_range; 60836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// @brief Returns a range view of the basic blocks in the region. 61036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines inline block_range blocks() { 61136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return block_range(block_begin(), block_end()); 61236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 61336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 61436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// @brief Returns a range view of the basic blocks in the region. 61536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 61636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This is the 'const' version of the range view. 61736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines inline const_block_range blocks() const { 61836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return const_block_range(block_begin(), block_end()); 61936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 620f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser //@} 621f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 622f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @name Element Iterators 623f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 624f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// These iterators iterate over all BasicBlock and subregion RegionNodes that 625f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// are direct children of this Region. It does not iterate over any 626f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// RegionNodes that are also element of a subregion of this Region. 627f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser //@{ 62837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef df_iterator<RegionNodeT *, SmallPtrSet<RegionNodeT *, 8>, false, 62937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines GraphTraits<RegionNodeT *>> element_iterator; 630f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 63137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef df_iterator<const RegionNodeT *, SmallPtrSet<const RegionNodeT *, 8>, 63237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines false, 63337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines GraphTraits<const RegionNodeT *>> const_element_iterator; 634f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 635f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser element_iterator element_begin(); 636f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser element_iterator element_end(); 637f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 638f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser const_element_iterator element_begin() const; 639f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser const_element_iterator element_end() const; 640f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser //@} 641f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser}; 642f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 64337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Print a RegionNode. 64437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 64537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesinline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node); 64637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 647f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 648f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// @brief Analysis that detects all canonical Regions. 649f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// 650f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// The RegionInfo pass detects all canonical regions in a function. The Regions 651f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// are connected using the parent relation. This builds a Program Structure 652f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Tree. 65337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 65437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionInfoBase { 65537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::BlockT BlockT; 65637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::FuncT FuncT; 65737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionT RegionT; 65837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionInfoT RegionInfoT; 65937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::DomTreeT DomTreeT; 66037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::DomTreeNodeT DomTreeNodeT; 66137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::PostDomTreeT PostDomTreeT; 66237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::DomFrontierT DomFrontierT; 66337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<BlockT *> BlockTraits; 66437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; 66537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename BlockTraits::ChildIteratorType SuccIterTy; 66637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename InvBlockTraits::ChildIteratorType PredIterTy; 66737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 66837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines friend class RegionInfo; 66937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines friend class MachineRegionInfo; 67037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DenseMap<BlockT *, BlockT *> BBtoBBMap; 67137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef DenseMap<BlockT *, RegionT *> BBtoRegionMap; 67237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef SmallPtrSet<RegionT *, 4> RegionSet; 67337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 67437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionInfoBase(); 67537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines virtual ~RegionInfoBase(); 676f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 677ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RegionInfoBase(const RegionInfoBase &) = delete; 678ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const RegionInfoBase &operator=(const RegionInfoBase &) = delete; 679f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 680de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegionInfoBase(RegionInfoBase &&Arg) 681de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)), 682de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TopLevelRegion(std::move(Arg.TopLevelRegion)), 683de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBtoRegion(std::move(Arg.BBtoRegion)) { 684de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Arg.wipe(); 685de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 686de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegionInfoBase &operator=(RegionInfoBase &&RHS) { 687de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DT = std::move(RHS.DT); 688de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PDT = std::move(RHS.PDT); 689de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DF = std::move(RHS.DF); 690de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TopLevelRegion = std::move(RHS.TopLevelRegion); 691de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBtoRegion = std::move(RHS.BBtoRegion); 692de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RHS.wipe(); 693de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return *this; 694de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 695de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 69637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomTreeT *DT; 69737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PostDomTreeT *PDT; 69837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomFrontierT *DF; 699f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 700f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// The top level region. 70137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *TopLevelRegion; 702f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 70337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesprivate: 704f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// Map every BB to the smallest region, that contains BB. 705f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegionMap BBtoRegion; 706f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 707de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \brief Wipe this region tree's state without releasing any resources. 708de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// 709de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This is essentially a post-move helper only. It leaves the object in an 710de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// assignable and destroyable state, but otherwise invalid. 711de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void wipe() { 712de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DT = nullptr; 713de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PDT = nullptr; 714de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DF = nullptr; 715de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TopLevelRegion = nullptr; 716de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBtoRegion.clear(); 717de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 718de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 719f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Check whether the entries of BBtoRegion for the BBs of region 720f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // SR are correct. Triggers an assertion if not. Calls itself recursively for 721f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // subregions. 722f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void verifyBBMap(const RegionT *SR) const; 723f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 724f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Returns true if BB is in the dominance frontier of 725f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // entry, because it was inherited from exit. In the other case there is an 726f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // edge going from entry to BB without passing exit. 72737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const; 728f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 729f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Check if entry and exit surround a valid region, based on 730f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // dominance tree and dominance frontier. 73137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isRegion(BlockT *entry, BlockT *exit) const; 732f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 733f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Saves a shortcut pointing from entry to exit. 734f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // This function may extend this shortcut if possible. 73537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const; 736f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 737f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Returns the next BB that postdominates N, while skipping 738f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // all post dominators that cannot finish a canonical region. 73937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const; 740f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 741f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A region is trivial, if it contains only one BB. 74237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool isTrivialRegion(BlockT *entry, BlockT *exit) const; 743f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 744f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Creates a single entry single exit region. 74537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *createRegion(BlockT *entry, BlockT *exit); 746f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 747f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Detect all regions starting with bb 'entry'. 74837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut); 749f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 750f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Detects regions in F. 75137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void scanForRegions(FuncT &F, BBtoBBMap *ShortCut); 752f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 753f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Get the top most parent with the same entry block. 75437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getTopMostParent(RegionT *region); 755f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 756f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Build the region hierarchy after all region detected. 75737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void buildRegionsTree(DomTreeNodeT *N, RegionT *region); 758f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 759f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Update statistic about created regions. 76037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines virtual void updateStatistics(RegionT *R) = 0; 761f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 762f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Detect all regions in function and build the region tree. 76337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void calculate(FuncT &F); 764f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 765f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserpublic: 76637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static bool VerifyRegionInfo; 76737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static typename RegionT::PrintStyle printStyle; 768f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 76937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void print(raw_ostream &OS) const; 77037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 77137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void dump() const; 77237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 773f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 77437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void releaseMemory(); 775f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 776f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Get the smallest region that contains a BasicBlock. 777f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 778f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The basic block. 779f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region, that contains BB or NULL, if there is no 780f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// region containing BB. 78137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getRegionFor(BlockT *BB) const; 782f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 7839ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser /// @brief Set the smallest region that surrounds a basic block. 7849ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser /// 7859ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser /// @param BB The basic block surrounded by a region. 7869ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser /// @param R The smallest region that surrounds BB. 78737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void setRegionFor(BlockT *BB, RegionT *R); 7889ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser 789f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief A shortcut for getRegionFor(). 790f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 791f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BB The basic block. 792f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region, that contains BB or NULL, if there is no 793f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// region containing BB. 79437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *operator[](BlockT *BB) const; 795f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 7960e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser /// @brief Return the exit of the maximal refined region, that starts at a 7970e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser /// BasicBlock. 7980e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser /// 7990e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser /// @param BB The BasicBlock the refined region starts. 80037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *getMaxRegionExit(BlockT *BB) const; 8010e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 802f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Find the smallest region that contains two regions. 803f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 804f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param A The first region. 805f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param B The second region. 806f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region containing A and B. 80737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getCommonRegion(RegionT *A, RegionT *B) const; 808f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 809f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Find the smallest region that contains two basic blocks. 810f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 811f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param A The first basic block. 812f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param B The second basic block. 813f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region that contains A and B. 81437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getCommonRegion(BlockT *A, BlockT *B) const { 815f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return getCommonRegion(getRegionFor(A), getRegionFor(B)); 816f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 817f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 818f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Find the smallest region that contains a set of regions. 819f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 820f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param Regions A vector of regions. 821f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region that contains all regions in Regions. 82237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const; 823f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 824f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Find the smallest region that contains a set of basic blocks. 825f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 826f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @param BBs A vector of basic blocks. 827f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @return The smallest region that contains all basic blocks in BBS. 82837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const; 829f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 83037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *getTopLevelRegion() const { return TopLevelRegion; } 831f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 832f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @brief Clear the Node Cache for all Regions. 833f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// 834f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser /// @see Region::clearNodeCache() 835f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser void clearNodeCache() { 836f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (TopLevelRegion) 837f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser TopLevelRegion->clearNodeCache(); 838f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 83937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void verifyAnalysis() const; 84137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 84237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass Region; 84437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionNode : public RegionNodeBase<RegionTraits<Function>> { 84637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 84737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false) 84837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {} 84937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 85037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool operator==(const Region &RN) const { 85137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return this == reinterpret_cast<const RegionNode *>(&RN); 85237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 85337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 85437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 85537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass Region : public RegionBase<RegionTraits<Function>> { 85637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 85737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, 85837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Region *Parent = nullptr); 85937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ~Region(); 86037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool operator==(const RegionNode &RN) const { 86237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return &RN == reinterpret_cast<const RegionNode *>(this); 86337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 86437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 86537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionInfo : public RegionInfoBase<RegionTraits<Function>> { 86737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 868de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef RegionInfoBase<RegionTraits<Function>> Base; 869de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 87037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines explicit RegionInfo(); 87137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 8720c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar ~RegionInfo() override; 87337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 874de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegionInfo(RegionInfo &&Arg) 875de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Base(std::move(static_cast<Base &>(Arg))) {} 876de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegionInfo &operator=(RegionInfo &&RHS) { 877de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Base::operator=(std::move(static_cast<Base &>(RHS))); 878de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return *this; 879de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 880de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 88137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // updateStatistics - Update statistic about created regions. 88237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void updateStatistics(Region *R) final; 88337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 88437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, 88537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DominanceFrontier *DF); 886f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 887f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#ifndef NDEBUG 888f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// @brief Opens a viewer to show the GraphViz visualization of the regions. 889f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// 890f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Useful during debugging as an alternative to dump(). 891f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void view(); 892f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 893f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// @brief Opens a viewer to show the GraphViz visualization of this region 894f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// without instructions in the BasicBlocks. 895f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// 896f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar /// Useful during debugging as an alternative to dump(). 897f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void viewOnly(); 898f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#endif 89937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 90037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 90137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass RegionInfoPass : public FunctionPass { 90237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionInfo RI; 90337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 90437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 90537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static char ID; 90637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines explicit RegionInfoPass(); 90737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 9080c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar ~RegionInfoPass() override; 90937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 91037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionInfo &getRegionInfo() { return RI; } 91137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 91237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const RegionInfo &getRegionInfo() const { return RI; } 91337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 91437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// @name FunctionPass interface 91537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines //@{ 91637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool runOnFunction(Function &F) override; 91737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void releaseMemory() override; 91837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void verifyAnalysis() const override; 91937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 92037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void print(raw_ostream &OS, const Module *) const override; 92137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void dump() const; 92237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines //@} 923f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser}; 924f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 925de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// \brief Analysis pass that exposes the \c RegionInfo for a function. 926de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarclass RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> { 927de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar friend AnalysisInfoMixin<RegionInfoAnalysis>; 928de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static char PassID; 929de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 930de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 931de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef RegionInfo Result; 932de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 933de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegionInfo run(Function &F, AnalysisManager<Function> &AM); 934de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 935de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 936de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// \brief Printer pass for the \c RegionInfo. 937de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarclass RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> { 938de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar raw_ostream &OS; 939de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 940de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 941de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar explicit RegionInfoPrinterPass(raw_ostream &OS); 942de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); 943de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 944de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 945de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// \brief Verifier pass for the \c RegionInfo. 946de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstruct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> { 947de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); 948de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 949de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 95037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <> 95137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <> 95237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesinline BasicBlock * 95337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const { 95437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); 95537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return getEntry(); 95637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 95737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 95837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <> 95937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <> 96037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesinline Region * 96137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const { 96237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(isSubRegion() && "This is not a subregion RegionNode!"); 96337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this); 96437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return reinterpret_cast<Region *>(Unconst); 96537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 96637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 96737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 96837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesinline raw_ostream &operator<<(raw_ostream &OS, 96937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const RegionNodeBase<Tr> &Node) { 97037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::BlockT BlockT; 97137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionT RegionT; 97237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 973f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (Node.isSubRegion()) 97437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return OS << Node.template getNodeAs<RegionT>()->getNameStr(); 975f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser else 97637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return OS << Node.template getNodeAs<BlockT>()->getName(); 977f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 97837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 979f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarextern template class RegionBase<RegionTraits<Function>>; 980f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarextern template class RegionNodeBase<RegionTraits<Function>>; 981f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarextern template class RegionInfoBase<RegionTraits<Function>>; 98237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 983f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} // End llvm namespace 984f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#endif 985