#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
/// 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 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.
///
/// 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 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;
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