#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 <map>
namespace llvm {
/// @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.
/// RegionNode.
PointerIntPair<BasicBlock*, 1, bool> entry;
-protected:
/// @brief The parent Region of this RegionNode.
/// @see getParent()
Region* parent;
/// two connections to the remaining graph. It can be used to analyze or
/// optimize parts of the control flow graph.
///
-/// A <em> simple Region </em> is connected to the remaing graph by just two
+/// A <em> simple Region </em> is connected to the remaining graph by just two
/// edges. One edge entering the Region and another one leaving the Region.
///
/// An <em> extended Region </em> (or just Region) is a subgraph that can be
/// 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;
/// @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.
/// @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.
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;
/// @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.
///
/// @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.
/// @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<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
- GraphTraits<FlatIt<RegionNode*> > > block_iterator;
-
- typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
- false, GraphTraits<FlatIt<const RegionNode*> > >
- const_block_iterator;
+ template <bool IsConst>
+ class block_iterator_wrapper
+ : public df_iterator<typename conditional<IsConst,
+ const BasicBlock,
+ BasicBlock>::type*> {
+ typedef df_iterator<typename conditional<IsConst,
+ const BasicBlock,
+ BasicBlock>::type*>
+ super;
+ public:
+ typedef block_iterator_wrapper<IsConst> 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<pointer>((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<BasicBlock*>(super::operator*());
+ }
+ };
+
+ typedef block_iterator_wrapper<false> block_iterator;
+ typedef block_iterator_wrapper<true> 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
typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
typedef SmallPtrSet<Region*, 4> 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;
/// 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.
/// 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.
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()
if (Node.isSubRegion())
return OS << Node.getNodeAs<Region>()->getNameStr();
else
- return OS << Node.getNodeAs<BasicBlock>()->getNameStr();
+ return OS << Node.getNodeAs<BasicBlock>()->getName();
}
} // End llvm namespace
#endif
projects / oota-llvm.git / blobdiff