diff options
author | Tobias Grosser <grosser@fim.uni-passau.de> | 2010-07-22 07:46:31 +0000 |
---|---|---|
committer | Tobias Grosser <grosser@fim.uni-passau.de> | 2010-07-22 07:46:31 +0000 |
commit | f96b0063674e6bf72da5429bd49097e33c2325c7 (patch) | |
tree | 6122b17b693e49a1fb9de1cabf099bb67d82414a /include | |
parent | 8a89a6ae9c3fb524cda60768e094ba481ac17be1 (diff) | |
download | external_llvm-f96b0063674e6bf72da5429bd49097e33c2325c7.zip external_llvm-f96b0063674e6bf72da5429bd49097e33c2325c7.tar.gz external_llvm-f96b0063674e6bf72da5429bd49097e33c2325c7.tar.bz2 |
Add new RegionInfo pass.
The RegionInfo pass detects single entry single exit regions in a function,
where a region is defined as any subgraph that is connected to the remaining
graph at only two spots.
Furthermore an hierarchical region tree is built.
Use it by calling "opt -regions analyze" or "opt -view-regions".
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109089 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/Analysis/Passes.h | 7 | ||||
-rw-r--r-- | include/llvm/Analysis/RegionInfo.h | 601 | ||||
-rw-r--r-- | include/llvm/Analysis/RegionIterator.h | 342 | ||||
-rw-r--r-- | include/llvm/Analysis/RegionPrinter.h | 26 | ||||
-rw-r--r-- | include/llvm/LinkAllPasses.h | 6 | ||||
-rw-r--r-- | include/llvm/Support/GraphWriter.h | 6 |
6 files changed, 988 insertions, 0 deletions
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index ce3f7a6..38bba77 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -154,6 +154,13 @@ namespace llvm { // print debug info intrinsics in human readable form FunctionPass *createDbgInfoPrinterPass(); + //===--------------------------------------------------------------------===// + // + // createRegionInfoPass - This pass finds all single entry single exit regions + // in a function and builds the region hierarchy. + // + FunctionPass *createRegionInfoPass(); + // Print module-level debug info metadata in human-readable form. ModulePass *createModuleDebugInfoPrinterPass(); } diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h new file mode 100644 index 0000000..c4ac1eb --- /dev/null +++ b/include/llvm/Analysis/RegionInfo.h @@ -0,0 +1,601 @@ +//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Calculate a program structure tree built out of single entry single exit +// regions. +// The basic ideas are taken from "The Program Structure Tree - Richard Johnson, +// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The +// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana +// Koehler - 2009". +// The algorithm to calculate these data structures however is completely +// different, as it takes advantage of existing information already available +// in (Post)dominace tree and dominance frontier passes. This leads to a simpler +// and in practice hopefully better performing algorithm. The runtime of the +// algorithms described in the papers above are both linear in graph size, +// O(V+E), whereas this algorithm is not, as the dominance frontier information +// itself is not, but in practice runtime seems to be in the order of magnitude +// of dominance tree calculation. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_REGION_INFO_H +#define LLVM_ANALYSIS_REGION_INFO_H + +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/Support/Allocator.h" + +namespace llvm { + +class Region; +class RegionInfo; +class raw_ostream; + +/// @brief Marker class to iterate over the elements of a Region in flat mode. +/// +/// The class is used to either iterate in Flat mode or by not using it to not +/// iterate in Flat mode. During a Flat mode iteration all Regions are entered +/// and the iteration returns every BasicBlock. If the Flat mode is not +/// selected for SubRegions just one RegionNode containing the subregion is +/// returned. +template <class GraphType> +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 &); + + /// 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. + /// + /// In the BBtoRegionNode map of the parent of this node, BB will always map + /// to this node no matter which kind of node this one is. + /// + /// The node can hold either a Region or a BasicBlock. + /// Use one bit to save, if this RegionNode is a subregion or BasicBlock + /// RegionNode. + PointerIntPair<BasicBlock*, 1, bool> entry; + +protected: + /// @brief The parent Region of this RegionNode. + /// @see getParent() + Region* parent; + +public: + /// @brief Create a RegionNode. + /// + /// @param Parent The parent of this RegionNode. + /// @param Entry The entry BasicBlock of the RegionNode. If this + /// RegionNode represents a BasicBlock, this is the + /// BasicBlock itself. If it represents a subregion, this + /// is the entry BasicBlock of the subregion. + /// @param isSubRegion If this RegionNode represents a SubRegion. + inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0) + : entry(Entry, isSubRegion), parent(Parent) {} + + /// @brief Get the parent Region of this RegionNode. + /// + /// The parent Region is the Region this RegionNode belongs to. If for + /// example a BasicBlock is element of two Regions, there exist two + /// RegionNodes for this BasicBlock. Each with the getParent() function + /// pointing to the Region this RegionNode belongs to. + /// + /// @return Get the parent Region of this RegionNode. + inline Region* getParent() const { return parent; } + + /// @brief Get the entry BasicBlock of this RegionNode. + /// + /// If this RegionNode represents a BasicBlock this is just the BasicBlock + /// itself, otherwise we return the entry BasicBlock of the Subregion + /// + /// @return The entry BasicBlock of this RegionNode. + inline BasicBlock* getEntry() const { return entry.getPointer(); } + + /// @brief Get the content of this RegionNode. + /// + /// This can be either a BasicBlock or a subregion. Before calling getNodeAs() + /// check the type of the content with the isSubRegion() function call. + /// + /// @return The content of this RegionNode. + template<class T> + inline T* getNodeAs() const; + + /// @brief Is this RegionNode a subregion? + /// + /// @return True if it contains a subregion. False if it contains a + /// BasicBlock. + inline bool isSubRegion() const { + return entry.getInt(); + } +}; + +/// Print a RegionNode. +inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node); + +template<> +inline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const { + assert(!isSubRegion() && "This is not a BasicBlock RegionNode!"); + return getEntry(); +} + +template<> +inline Region* RegionNode::getNodeAs<Region>() const { + assert(isSubRegion() && "This is not a subregion RegionNode!"); + return reinterpret_cast<Region*>(const_cast<RegionNode*>(this)); +} + +//===----------------------------------------------------------------------===// +/// @brief A single entry single exit Region. +/// +/// A Region is a connected subgraph of a control flow graph that has exactly +/// 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 +/// 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 +/// transform into a simple Region. The transformation is done by adding +/// BasicBlocks that merge several entry or exit edges so that after the merge +/// just one entry and one exit edge exists. +/// +/// The \e Entry of a Region is the first BasicBlock that is passed after +/// entering the Region. It is an element of the Region. The entry BasicBlock +/// dominates all BasicBlocks in the Region. +/// +/// The \e Exit of a Region is the first BasicBlock that is passed after +/// leaving the Region. It is not an element of the Region. The exit BasicBlock, +/// postdominates all BasicBlocks in the Region. +/// +/// A <em> canonical Region </em> cannot be constructed by combining smaller +/// Regions. +/// +/// Region A is the \e parent of Region B, if B is completely contained in A. +/// +/// Two canonical Regions either do not intersect at all or one is +/// the parent of the other. +/// +/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of +/// Regions in the control flow graph and E is the \e parent relation of these +/// Regions. +/// +/// Example: +/// +/// \verbatim +/// A simple control flow graph, that contains two regions. +/// +/// 1 +/// / | +/// 2 | +/// / \ 3 +/// 4 5 | +/// | | | +/// 6 7 8 +/// \ | / +/// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8} +/// 9 Region B: 2 -> 9 {2,4,5,6,7} +/// \endverbatim +/// +/// You can obtain more examples by either calling +/// +/// <tt> "opt -regions -analyze anyprogram.ll" </tt> +/// or +/// <tt> "opt -view-regions-only anyprogram.ll" </tt> +/// +/// on any LLVM file you are interested in. +/// +/// The first call returns a textual representation of the program structure +/// 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 &); + + // Information necessary to manage this Region. + RegionInfo* RI; + DominatorTree *DT; + + // The exit BasicBlock of this region. + // (The entry BasicBlock is part of RegionNode) + BasicBlock *exit; + + typedef std::vector<Region*> RegionSet; + + // The subregions of this region. + RegionSet children; + + typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT; + + // Save the BasicBlock RegionNodes that are element of this Region. + mutable BBNodeMapT BBNodeMap; + + /// verifyBBInRegion - Check if a BB is in this Region. This check also works + /// if the region is incorrectly built. (EXPENSIVE!) + void verifyBBInRegion(BasicBlock* BB) const; + + /// verifyWalk - Walk over all the BBs of the region starting from BB and + /// verify that all reachable basic blocks are elements of the region. + /// (EXPENSIVE!) + void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const; + + /// verifyRegionNest - Verify if the region and its children are valid + /// regions (EXPENSIVE!) + void verifyRegionNest() const; + +public: + /// @brief Create a new region. + /// + /// @param Entry The entry basic block of the region. + /// @param Exit The exit basic block of the region. + /// @param RI The region info object that is managing this region. + /// @param DT The dominator tree of the current function. + /// @param Parent The surrounding region or NULL if this is a top level + /// region. + Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI, + DominatorTree *DT, Region *Parent = 0); + + /// Delete the Region and all its subregions. + ~Region(); + + /// @brief Get the entry BasicBlock of the Region. + /// @return The entry BasicBlock of the region. + BasicBlock *getEntry() const { return RegionNode::getEntry(); } + + /// @brief Get the exit BasicBlock of the Region. + /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel + /// Region. + BasicBlock *getExit() const { return exit; } + + /// @brief Get the parent of the Region. + /// @return The parent of the Region or NULL if this is a top level + /// Region. + Region *getParent() const { return RegionNode::getParent(); } + + /// @brief Get the RegionNode representing the current Region. + /// @return The RegionNode representing the current Region. + RegionNode* getNode() const { + return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this)); + } + + /// @brief Get the nesting level of this Region. + /// + /// An toplevel Region has depth 0. + /// + /// @return The depth of the region. + unsigned getDepth() const; + + /// @brief Is this a simple region? + /// + /// A region is simple if it has exactly one exit and one entry edge. + /// + /// @return True if the Region is simple. + bool isSimple() const; + + /// @brief Returns the name of the Region. + /// @return The Name of the Region. + std::string getNameStr() const { + std::string exitName; + + if (getExit()) + exitName = getExit()->getNameStr(); + else + exitName = "<Function Return>"; + + return getEntry()->getNameStr() + " => " + exitName; + } + + /// @brief Return the RegionInfo object, that belongs to this Region. + RegionInfo *getRegionInfo() const { + return RI; + } + + /// @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; + + /// @brief Print the region to stderr. + void dump() const; + + /// @brief Check if the region contains a BasicBlock. + /// + /// @param BB The BasicBlock that might be contained in this Region. + /// @return True if the block is contained in the region otherwise false. + bool contains(const BasicBlock *BB) const; + + /// @brief Check if the region contains another region. + /// + /// @param SubRegion The region that might be contained in this Region. + /// @return True if SubRegion is contained in the region otherwise false. + bool contains(const Region *SubRegion) const { + // Toplevel Region. + if (!getExit()) + return true; + + return contains(SubRegion->getEntry()) + && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit()); + } + + /// @brief Check if the region contains an Instruction. + /// + /// @param Inst The Instruction that might be contained in this region. + /// @return True if the Instruction is contained in the region otherwise false. + bool contains(const Instruction *Inst) const { + return contains(Inst->getParent()); + } + + /// @brief Get the subregion that starts at a BasicBlock + /// + /// @param BB The BasicBlock the subregion should start. + /// @return The Subregion if available, otherwise NULL. + Region* getSubRegionNode(BasicBlock *BB) const; + + /// @brief Get the RegionNode for a BasicBlock + /// + /// @param BB The BasicBlock at which the RegionNode should start. + /// @return If available, the RegionNode that represents the subregion + /// starting at BB. If no subregion starts at BB, the RegionNode + /// representing BB. + RegionNode* getNode(BasicBlock *BB) const; + + /// @brief Get the BasicBlock RegionNode for a BasicBlock + /// + /// @param BB The BasicBlock for which the RegionNode is requested. + /// @return The RegionNode representing the BB. + RegionNode* getBBNode(BasicBlock *BB) const; + + /// @brief Add a new subregion to this Region. + /// + /// @param SubRegion The new subregion that will be added. + void addSubRegion(Region *SubRegion); + + /// @brief Remove a subregion from this Region. + /// + /// The subregion is not deleted, as it will probably be inserted into another + /// region. + /// @param SubRegion The SubRegion that will be removed. + Region *removeSubRegion(Region *SubRegion); + + /// @brief Move all direct child nodes of this Region to another Region. + /// + /// @param To The Region the child nodes will be transfered to. + void transferChildrenTo(Region *To); + + /// @brief Verify if the region is a correct region. + /// + /// Check if this is a correctly build Region. This is an expensive check, as + /// the complete CFG of the Region will be walked. + void verifyRegion() const; + + /// @brief Clear the cache for BB RegionNodes. + /// + /// After calling this function the BasicBlock RegionNodes will be stored at + /// different memory locations. RegionNodes obtained before this function is + /// called are therefore not comparable to RegionNodes abtained afterwords. + void clearNodeCache(); + + /// @name Subregion Iterators + /// + /// These iterators iterator over all subregions of this Region. + //@{ + typedef RegionSet::iterator iterator; + typedef RegionSet::const_iterator const_iterator; + + iterator begin() { return children.begin(); } + iterator end() { return children.end(); } + + const_iterator begin() const { return children.begin(); } + const_iterator end() const { return children.end(); } + //@} + + /// @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. + //@{ + 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; + + block_iterator block_begin(); + block_iterator block_end(); + + const_block_iterator block_begin() const; + const_block_iterator block_end() const; + //@} + + /// @name Element Iterators + /// + /// These iterators iterate over all BasicBlock and subregion RegionNodes that + /// are direct children of this Region. It does not iterate over any + /// RegionNodes that are also element of a subregion of this Region. + //@{ + typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, + GraphTraits<RegionNode*> > element_iterator; + + typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, + false, GraphTraits<const RegionNode*> > + const_element_iterator; + + element_iterator element_begin(); + element_iterator element_end(); + + const_element_iterator element_begin() const; + const_element_iterator element_end() const; + //@} +}; + +//===----------------------------------------------------------------------===// +/// @brief Analysis that detects all canonical Regions. +/// +/// The RegionInfo pass detects all canonical regions in a function. The Regions +/// are connected using the parent relation. This builds a Program Structure +/// Tree. +class RegionInfo : public FunctionPass { + typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap; + typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap; + typedef SmallPtrSet<Region*, 4> RegionSet; + + // DO NOT IMPLEMENT + RegionInfo(const RegionInfo &); + // DO NOT IMPLEMENT + const RegionInfo &operator=(const RegionInfo &); + + DominatorTree *DT; + PostDominatorTree *PDT; + DominanceFrontier *DF; + + /// The top level region. + Region *TopLevelRegion; + + /// Map every BB to the smallest region, that contains BB. + BBtoRegionMap BBtoRegion; + + // isCommonDomFrontier - Returns true if BB is in the dominance frontier of + // entry, because it was inherited from exit. In the other case there is an + // edge going from entry to BB without passing exit. + bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry, + BasicBlock* exit) const; + + // isRegion - Check if entry and exit surround a valid region, based on + // dominance tree and dominance frontier. + bool isRegion(BasicBlock* entry, BasicBlock* exit) const; + + // insertShortCut - Saves a shortcut pointing from entry to exit. + // This function may extend this shortcut if possible. + void insertShortCut(BasicBlock* entry, BasicBlock* exit, + BBtoBBMap* ShortCut) const; + + // getNextPostDom - Returns the next BB that postdominates N, while skipping + // all post dominators that cannot finish a canonical region. + DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const; + + // isTrivialRegion - A region is trivial, if it contains only one BB. + bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const; + + // createRegion - Creates a single entry single exit region. + Region *createRegion(BasicBlock *entry, BasicBlock *exit); + + // findRegionsWithEntry - Detect all regions starting with bb 'entry'. + void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut); + + // scanForRegions - Detects regions in F. + void scanForRegions(Function &F, BBtoBBMap *ShortCut); + + // getTopMostParent - Get the top most parent with the same entry block. + Region *getTopMostParent(Region *region); + + // buildRegionsTree - build the region hierarchy after all region detected. + void buildRegionsTree(DomTreeNode *N, Region *region); + + // Calculate - detecte all regions in function and build the region tree. + void Calculate(Function& F); + + void releaseMemory(); + + // updateStatistics - Update statistic about created regions. + void updateStatistics(Region *R); + + // isSimple - Check if a region is a simple region with exactly one entry + // edge and exactly one exit edge. + bool isSimple(Region* R) const; + +public: + static char ID; + explicit RegionInfo(); + + ~RegionInfo(); + + /// @name FunctionPass interface + //@{ + virtual bool runOnFunction(Function &F); + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void print(raw_ostream &OS, const Module *) const; + virtual void verifyAnalysis() const; + //@} + + /// @brief Get the smallest region that contains a BasicBlock. + /// + /// @param BB The basic block. + /// @return The smallest region, that contains BB or NULL, if there is no + /// region containing BB. + Region *getRegionFor(BasicBlock *BB) const; + + /// @brief A shortcut for getRegionFor(). + /// + /// @param BB The basic block. + /// @return The smallest region, that contains BB or NULL, if there is no + /// region containing BB. + Region *operator[](BasicBlock *BB) const; + + /// @brief Find the smallest region that contains two regions. + /// + /// @param A The first region. + /// @param B The second region. + /// @return The smallest region containing A and B. + Region *getCommonRegion(Region* A, Region *B) const; + + /// @brief Find the smallest region that contains two basic blocks. + /// + /// @param A The first basic block. + /// @param B The second basic block. + /// @return The smallest region that contains A and B. + Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const { + return getCommonRegion(getRegionFor(A), getRegionFor(B)); + } + + /// @brief Find the smallest region that contains a set of regions. + /// + /// @param Regions A vector of regions. + /// @return The smallest region that contains all regions in Regions. + Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const; + + /// @brief Find the smallest region that contains a set of basic blocks. + /// + /// @param BBs A vector of basic blocks. + /// @return The smallest region that contains all basic blocks in BBS. + Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const; + + Region *getTopLevelRegion() const { + return TopLevelRegion; + } + + /// @brief Clear the Node Cache for all Regions. + /// + /// @see Region::clearNodeCache() + void clearNodeCache() { + if (TopLevelRegion) + TopLevelRegion->clearNodeCache(); + } +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) { + if (Node.isSubRegion()) + return OS << Node.getNodeAs<Region>()->getNameStr(); + else + return OS << Node.getNodeAs<BasicBlock>()->getNameStr(); +} +} // End llvm namespace +#endif + diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h new file mode 100644 index 0000000..ced5b52 --- /dev/null +++ b/include/llvm/Analysis/RegionIterator.h @@ -0,0 +1,342 @@ +//===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// This file defines the iterators to iterate over the elements of a Region. +//===----------------------------------------------------------------------===// +#ifndef LLVM_ANALYSIS_REGION_ITERATOR_H +#define LLVM_ANALYSIS_REGION_ITERATOR_H + +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/Analysis/RegionInfo.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/raw_ostream.h" + +namespace llvm { +//===----------------------------------------------------------------------===// +/// @brief Hierachical RegionNode successor iterator. +/// +/// This iterator iterates over all successors of a RegionNode. +/// +/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of +/// the parent Region. Furthermore for BasicBlocks that start a subregion, a +/// RegionNode representing the subregion is returned. +/// +/// For a subregion RegionNode there is just one successor. The RegionNode +/// representing the exit of the subregion. +template<class NodeType> +class RNSuccIterator : public std::iterator<std::forward_iterator_tag, + NodeType, ptrdiff_t> +{ + typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; + // The iterator works in two modes, bb mode or region mode. + enum ItMode{ + // In BB mode it returns all successors of this BasicBlock as its + // successors. + ItBB, + // In region mode there is only one successor, thats the regionnode mapping + // to the exit block of the regionnode + ItRgBegin, // At the beginning of the regionnode successor. + ItRgEnd // At the end of the regionnode successor. + }; + + // Use two bit to represent the mode iterator. + PointerIntPair<NodeType*, 2, enum ItMode> Node; + + // The block successor iterator. + succ_iterator BItor; + + // advanceRegionSucc - A region node has only one successor. It reaches end + // once we advance it. + void advanceRegionSucc() { + assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); + Node.setInt(ItRgEnd); + } + + NodeType* getNode() const{ return Node.getPointer(); } + + // isRegionMode - Is the current iterator in region mode? + bool isRegionMode() const { return Node.getInt() != ItBB; } + + // Get the immediate successor. This function may return a Basic Block + // RegionNode or a subregion RegionNode. + RegionNode* getISucc(BasicBlock* BB) const { + RegionNode *succ; + succ = getNode()->getParent()->getNode(BB); + assert(succ && "BB not in Region or entered subregion!"); + return succ; + } + + // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. + inline BasicBlock* getRegionSucc() const { + assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); + return getNode()->template getNodeAs<Region>()->getExit(); + } + + // isExit - Is this the exit BB of the Region? + inline bool isExit(BasicBlock* BB) const { + return getNode()->getParent()->getExit() == BB; + } +public: + typedef RNSuccIterator<NodeType> Self; + + typedef typename super::pointer pointer; + + /// @brief Create begin iterator of a RegionNode. + inline RNSuccIterator(NodeType* node) + : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), + BItor(succ_begin(node->getEntry())) { + + + // Skip the exit block + if (!isRegionMode()) + while (succ_end(node->getEntry()) != BItor && isExit(*BItor)) + ++BItor; + + if (isRegionMode() && isExit(getRegionSucc())) + advanceRegionSucc(); + } + + /// @brief Create an end iterator. + inline RNSuccIterator(NodeType* node, bool) + : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), + BItor(succ_end(node->getEntry())) {} + + inline bool operator==(const Self& x) const { + assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); + if (isRegionMode()) + return Node.getInt() == x.Node.getInt(); + else + return BItor == x.BItor; + } + + inline bool operator!=(const Self& x) const { return !operator==(x); } + + inline pointer operator*() const { + BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor; + assert(!isExit(BB) && "Iterator out of range!"); + return getISucc(BB); + } + + inline Self& operator++() { + if(isRegionMode()) { + // The Region only has 1 successor. + advanceRegionSucc(); + } else { + // Skip the exit. + do + ++BItor; + while (BItor != succ_end(getNode()->getEntry()) + && isExit(*BItor)); + } + return *this; + } + + inline Self operator++(int) { + Self tmp = *this; + ++*this; + return tmp; + } + + inline const Self &operator=(const Self &I) { + if (this != &I) { + assert(getNode()->getParent() == I.getNode()->getParent() + && "Cannot assign iterators of two different regions!"); + Node = I.Node; + BItor = I.BItor; + } + return *this; + } +}; + + +//===----------------------------------------------------------------------===// +/// @brief Flat RegionNode iterator. +/// +/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that +/// are contained in the Region and its subregions. This is close to a virtual +/// control flow graph of the Region. +template<class NodeType> +class RNSuccIterator<FlatIt<NodeType> > + : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> +{ + typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; + NodeType* Node; + succ_iterator Itor; + +public: + typedef RNSuccIterator<FlatIt<NodeType> > Self; + typedef typename super::pointer pointer; + + /// @brief Create the iterator from a RegionNode. + /// + /// Note that the incoming node must be a bb node, otherwise it will trigger + /// an assertion when we try to get a BasicBlock. + inline RNSuccIterator(NodeType* node) : Node(node), + Itor(succ_begin(node->getEntry())) { + assert(!Node->isSubRegion() + && "Subregion node not allowed in flat iterating mode!"); + assert(Node->getParent() && "A BB node must have a parent!"); + + // Skip the exit block of the iterating region. + while (succ_end(Node->getEntry()) != Itor + && Node->getParent()->getExit() == *Itor) + ++Itor; + } + /// @brief Create an end iterator + inline RNSuccIterator(NodeType* node, bool) : Node(node), + Itor(succ_end(node->getEntry())) { + assert(!Node->isSubRegion() + && "Subregion node not allowed in flat iterating mode!"); + } + + inline bool operator==(const Self& x) const { + assert(Node->getParent() == x.Node->getParent() + && "Cannot compare iterators of different regions!"); + + return Itor == x.Itor && Node == x.Node; + } + + inline bool operator!=(const Self& x) const { return !operator==(x); } + + inline pointer operator*() const { + BasicBlock* BB = *Itor; + + // Get the iterating region. + Region* Parent = Node->getParent(); + + // The only case that the successor reaches out of the region is it reaches + // the exit of the region. + assert(Parent->getExit() != BB && "iterator out of range!"); + + return Parent->getBBNode(BB); + } + + inline Self& operator++() { + // Skip the exit block of the iterating region. + do + ++Itor; + while (Itor != succ_end(Node->getEntry()) + && Node->getParent()->getExit() == *Itor); + + return *this; + } + + inline Self operator++(int) { + Self tmp = *this; + ++*this; + return tmp; + } + + inline const Self &operator=(const Self &I) { + if (this != &I) { + assert(Node->getParent() == I.Node->getParent() + && "Cannot assign iterators to two different regions!"); + Node = I.Node; + Itor = I.Itor; + } + return *this; + } +}; + +template<class NodeType> +inline RNSuccIterator<NodeType> succ_begin(NodeType* Node) { + return RNSuccIterator<NodeType>(Node); +} + +template<class NodeType> +inline RNSuccIterator<NodeType> succ_end(NodeType* Node) { + return RNSuccIterator<NodeType>(Node, true); +} + +//===--------------------------------------------------------------------===// +// RegionNode GraphTraits specialization so the bbs in the region can be +// iterate by generic graph iterators. +// +// NodeT can either be region node or const region node, otherwise child_begin +// and child_end fail. + +#define RegionNodeGraphTraits(NodeT) \ + template<> struct GraphTraits<NodeT*> { \ + typedef NodeT NodeType; \ + typedef RNSuccIterator<NodeType> ChildIteratorType; \ + static NodeType *getEntryNode(NodeType* N) { return N; } \ + static inline ChildIteratorType child_begin(NodeType *N) { \ + return RNSuccIterator<NodeType>(N); \ + } \ + static inline ChildIteratorType child_end(NodeType *N) { \ + return RNSuccIterator<NodeType>(N, true); \ + } \ +}; \ +template<> struct GraphTraits<FlatIt<NodeT*> > { \ + typedef NodeT NodeType; \ + typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \ + static NodeType *getEntryNode(NodeType* N) { return N; } \ + static inline ChildIteratorType child_begin(NodeType *N) { \ + return RNSuccIterator<FlatIt<NodeType> >(N); \ + } \ + static inline ChildIteratorType child_end(NodeType *N) { \ + return RNSuccIterator<FlatIt<NodeType> >(N, true); \ + } \ +} + +#define RegionGraphTraits(RegionT, NodeT) \ +template<> struct GraphTraits<RegionT*> \ + : public GraphTraits<NodeT*> { \ + typedef df_iterator<NodeType*> nodes_iterator; \ + static NodeType *getEntryNode(RegionT* R) { \ + return R->getNode(R->getEntry()); \ + } \ + static nodes_iterator nodes_begin(RegionT* R) { \ + return nodes_iterator::begin(getEntryNode(R)); \ + } \ + static nodes_iterator nodes_end(RegionT* R) { \ + return nodes_iterator::end(getEntryNode(R)); \ + } \ +}; \ +template<> struct GraphTraits<FlatIt<RegionT*> > \ + : public GraphTraits<FlatIt<NodeT*> > { \ + typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \ + GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \ + static NodeType *getEntryNode(RegionT* R) { \ + return R->getBBNode(R->getEntry()); \ + } \ + static nodes_iterator nodes_begin(RegionT* R) { \ + return nodes_iterator::begin(getEntryNode(R)); \ + } \ + static nodes_iterator nodes_end(RegionT* R) { \ + return nodes_iterator::end(getEntryNode(R)); \ + } \ +} + +RegionNodeGraphTraits(RegionNode); +RegionNodeGraphTraits(const RegionNode); + +RegionGraphTraits(Region, RegionNode); +RegionGraphTraits(const Region, const RegionNode); + +template <> struct GraphTraits<RegionInfo*> + : public GraphTraits<FlatIt<RegionNode*> > { + typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, + GraphTraits<FlatIt<NodeType*> > > nodes_iterator; + + static NodeType *getEntryNode(RegionInfo *RI) { + return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion()); + } + static nodes_iterator nodes_begin(RegionInfo* RI) { + return nodes_iterator::begin(getEntryNode(RI)); + } + static nodes_iterator nodes_end(RegionInfo *RI) { + return nodes_iterator::end(getEntryNode(RI)); + } +}; + +} // End namespace llvm + +#endif diff --git a/include/llvm/Analysis/RegionPrinter.h b/include/llvm/Analysis/RegionPrinter.h new file mode 100644 index 0000000..758748a --- /dev/null +++ b/include/llvm/Analysis/RegionPrinter.h @@ -0,0 +1,26 @@ +//===-- RegionPrinter.h - Region printer external interface -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines external functions that can be called to explicitly +// instantiate the region printer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_REGIONPRINTER_H +#define LLVM_ANALYSIS_REGIONPRINTER_H + +namespace llvm { + class FunctionPass; + FunctionPass *createRegionViewerPass(); + FunctionPass *createRegionOnlyViewerPass(); + FunctionPass *createRegionPrinterPass(); + FunctionPass *createRegionOnlyPrinterPass(); +} // End llvm namespace + +#endif diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 876703b..4f3a019 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -22,6 +22,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/PointerTracking.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/RegionPrinter.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/Lint.h" #include "llvm/Assembly/PrintModulePass.h" @@ -106,6 +107,11 @@ namespace { (void) llvm::createPostDomOnlyViewerPass(); (void) llvm::createPostDomViewerPass(); (void) llvm::createReassociatePass(); + (void) llvm::createRegionInfoPass(); + (void) llvm::createRegionOnlyPrinterPass(); + (void) llvm::createRegionOnlyViewerPass(); + (void) llvm::createRegionPrinterPass(); + (void) llvm::createRegionViewerPass(); (void) llvm::createSCCPPass(); (void) llvm::createScalarReplAggregatesPass(); (void) llvm::createSimplifyLibCallsPass(); diff --git a/include/llvm/Support/GraphWriter.h b/include/llvm/Support/GraphWriter.h index 559f004..f653f97 100644 --- a/include/llvm/Support/GraphWriter.h +++ b/include/llvm/Support/GraphWriter.h @@ -271,6 +271,12 @@ public: O << "[" << Attrs << "]"; O << ";\n"; } + + /// getOStream - Get the raw output stream into the graph file. Useful to + /// write fancy things using addCustomGraphFeatures(). + raw_ostream &getOStream() { + return O; + } }; template<typename GraphType> |