X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=include%2Fllvm%2FAnalysis%2FRegionInfo.h;h=48d7ee6b5476636396ad76b00ce1ad9125c9f0d1;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=a54509f5e8e3b3da82b7119f87684cf6957f4c3f;hpb=082d587d35a41ee06985d7867b72fb2632962281;p=oota-llvm.git diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index a54509f5e8e..48d7ee6b547 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -28,9 +28,10 @@ #define LLVM_ANALYSIS_REGION_INFO_H #include "llvm/ADT/PointerIntPair.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Support/Allocator.h" +#include namespace llvm { @@ -53,11 +54,10 @@ class FlatIt {}; /// @brief A RegionNode represents a subregion or a BasicBlock that is part of a /// Region. class RegionNode { - // DO NOT IMPLEMENT - RegionNode(const RegionNode &); - // DO NOT IMPLEMENT - const RegionNode &operator=(const RegionNode &); + RegionNode(const RegionNode &) LLVM_DELETED_FUNCTION; + const RegionNode &operator=(const RegionNode &) LLVM_DELETED_FUNCTION; +protected: /// This is the entry basic block that starts this region node. If this is a /// BasicBlock RegionNode, then entry is just the basic block, that this /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. @@ -70,7 +70,6 @@ class RegionNode { /// RegionNode. PointerIntPair entry; -protected: /// @brief The parent Region of this RegionNode. /// @see getParent() Region* parent; @@ -145,7 +144,7 @@ inline Region* RegionNode::getNodeAs() const { /// two connections to the remaining graph. It can be used to analyze or /// optimize parts of the control flow graph. /// -/// A simple Region is connected to the remaing graph by just two +/// A simple Region is connected to the remaining graph by just two /// edges. One edge entering the Region and another one leaving the Region. /// /// An extended Region (or just Region) is a subgraph that can be @@ -202,10 +201,8 @@ inline Region* RegionNode::getNodeAs() const { /// tree, the second one creates a graphical representation using graphviz. class Region : public RegionNode { friend class RegionInfo; - // DO NOT IMPLEMENT - Region(const Region &); - // DO NOT IMPLEMENT - const Region &operator=(const Region &); + Region(const Region &) LLVM_DELETED_FUNCTION; + const Region &operator=(const Region &) LLVM_DELETED_FUNCTION; // Information necessary to manage this Region. RegionInfo* RI; @@ -257,6 +254,18 @@ public: /// @return The entry BasicBlock of the region. BasicBlock *getEntry() const { return RegionNode::getEntry(); } + /// @brief Replace the entry basic block of the region with the new basic + /// block. + /// + /// @param BB The new entry basic block of the region. + void replaceEntry(BasicBlock *BB); + + /// @brief Replace the exit basic block of the region with the new basic + /// block. + /// + /// @param BB The new exit basic block of the region. + void replaceExit(BasicBlock *BB); + /// @brief Get the exit BasicBlock of the Region. /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel /// Region. @@ -280,6 +289,33 @@ public: /// @return The depth of the region. unsigned getDepth() const; + /// @brief Check if a Region is the TopLevel region. + /// + /// The toplevel region represents the whole function. + bool isTopLevelRegion() const { return exit == NULL; } + + /// @brief Return a new (non canonical) region, that is obtained by joining + /// this region with its predecessors. + /// + /// @return A region also starting at getEntry(), but reaching to the next + /// basic block that forms with getEntry() a (non canonical) region. + /// NULL if such a basic block does not exist. + Region *getExpandedRegion() const; + + /// @brief Return the first block of this region's single entry edge, + /// if existing. + /// + /// @return The BasicBlock starting this region's single entry edge, + /// else NULL. + BasicBlock *getEnteringBlock() const; + + /// @brief Return the first block of this region's single exit edge, + /// if existing. + /// + /// @return The BasicBlock starting this region's single exit edge, + /// else NULL. + BasicBlock *getExitingBlock() const; + /// @brief Is this a simple region? /// /// A region is simple if it has exactly one exit and one entry edge. @@ -296,12 +332,16 @@ public: return RI; } + /// PrintStyle - Print region in difference ways. + enum PrintStyle { PrintNone, PrintBB, PrintRN }; + /// @brief Print the region. /// /// @param OS The output stream the Region is printed to. /// @param printTree Print also the tree of subregions. /// @param level The indentation level used for printing. - void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const; + void print(raw_ostream& OS, bool printTree = true, unsigned level = 0, + enum PrintStyle Style = PrintNone) const; /// @brief Print the region to stderr. void dump() const; @@ -386,7 +426,9 @@ public: /// @brief Add a new subregion to this Region. /// /// @param SubRegion The new subregion that will be added. - void addSubRegion(Region *SubRegion); + /// @param moveChildren Move the children of this region, that are also + /// contained in SubRegion into SubRegion. + void addSubRegion(Region *SubRegion, bool moveChildren = false); /// @brief Remove a subregion from this Region. /// @@ -397,7 +439,7 @@ public: /// @brief Move all direct child nodes of this Region to another Region. /// - /// @param To The Region the child nodes will be transfered to. + /// @param To The Region the child nodes will be transferred to. void transferChildrenTo(Region *To); /// @brief Verify if the region is a correct region. @@ -429,23 +471,62 @@ public: /// @name BasicBlock Iterators /// - /// These iterators iterate over all BasicBlock RegionNodes that are - /// contained in this Region. The iterator also iterates over BasicBlocks - /// that are elements of a subregion of this Region. It is therefore called a - /// flat iterator. + /// These iterators iterate over all BasicBlocks that are contained in this + /// Region. The iterator also iterates over BasicBlocks that are elements of + /// a subregion of this Region. It is therefore called a flat iterator. //@{ - typedef df_iterator, false, - GraphTraits > > block_iterator; - - typedef df_iterator, - false, GraphTraits > > - const_block_iterator; + template + class block_iterator_wrapper + : public df_iterator::type*> { + typedef df_iterator::type*> + super; + public: + typedef block_iterator_wrapper Self; + typedef typename super::pointer pointer; + + // Construct the begin iterator. + block_iterator_wrapper(pointer Entry, pointer Exit) : super(df_begin(Entry)) + { + // Mark the exit of the region as visited, so that the children of the + // exit and the exit itself, i.e. the block outside the region will never + // be visited. + super::Visited.insert(Exit); + } + + // Construct the end iterator. + block_iterator_wrapper() : super(df_end((BasicBlock *)0)) {} + + /*implicit*/ block_iterator_wrapper(super I) : super(I) {} + + // FIXME: Even a const_iterator returns a non-const BasicBlock pointer. + // This was introduced for backwards compatibility, but should + // be removed as soon as all users are fixed. + BasicBlock *operator*() const { + return const_cast(super::operator*()); + } + }; + + typedef block_iterator_wrapper block_iterator; + typedef block_iterator_wrapper const_block_iterator; + + block_iterator block_begin() { + return block_iterator(getEntry(), getExit()); + } - block_iterator block_begin(); - block_iterator block_end(); + block_iterator block_end() { + return block_iterator(); + } - const_block_iterator block_begin() const; - const_block_iterator block_end() const; + const_block_iterator block_begin() const { + return const_block_iterator(getEntry(), getExit()); + } + const_block_iterator block_end() const { + return const_block_iterator(); + } //@} /// @name Element Iterators @@ -480,10 +561,8 @@ class RegionInfo : public FunctionPass { typedef DenseMap BBtoRegionMap; typedef SmallPtrSet RegionSet; - // DO NOT IMPLEMENT - RegionInfo(const RegionInfo &); - // DO NOT IMPLEMENT - const RegionInfo &operator=(const RegionInfo &); + RegionInfo(const RegionInfo &) LLVM_DELETED_FUNCTION; + const RegionInfo &operator=(const RegionInfo &) LLVM_DELETED_FUNCTION; DominatorTree *DT; PostDominatorTree *PDT; @@ -565,6 +644,12 @@ public: /// region containing BB. Region *getRegionFor(BasicBlock *BB) const; + /// @brief Set the smallest region that surrounds a basic block. + /// + /// @param BB The basic block surrounded by a region. + /// @param R The smallest region that surrounds BB. + void setRegionFor(BasicBlock *BB, Region *R); + /// @brief A shortcut for getRegionFor(). /// /// @param BB The basic block. @@ -572,6 +657,12 @@ public: /// region containing BB. Region *operator[](BasicBlock *BB) const; + /// @brief Return the exit of the maximal refined region, that starts at a + /// BasicBlock. + /// + /// @param BB The BasicBlock the refined region starts. + BasicBlock *getMaxRegionExit(BasicBlock *BB) const; + /// @brief Find the smallest region that contains two regions. /// /// @param A The first region. @@ -604,6 +695,12 @@ public: return TopLevelRegion; } + /// @brief Update RegionInfo after a basic block was split. + /// + /// @param NewBB The basic block that was created before OldBB. + /// @param OldBB The old basic block. + void splitBlock(BasicBlock* NewBB, BasicBlock *OldBB); + /// @brief Clear the Node Cache for all Regions. /// /// @see Region::clearNodeCache() @@ -617,7 +714,7 @@ inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) { if (Node.isSubRegion()) return OS << Node.getNodeAs()->getNameStr(); else - return OS << Node.getNodeAs()->getNameStr(); + return OS << Node.getNodeAs()->getName(); } } // End llvm namespace #endif