diff options
32 files changed, 2707 insertions, 0 deletions
diff --git a/docs/Passes.html b/docs/Passes.html index fb3bc9474b..12a936ad8d 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -120,6 +120,7 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <tr><td><a href="#print-used-types">-print-used-types</a></td><td>Find Used Types</td></tr> <tr><td><a href="#profile-estimator">-profile-estimator</a></td><td>Estimate profiling information</td></tr> <tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr> +<tr><td><a href="#regions">-regions</a></td><td>Detect single entry single exit regions in a function</td></tr> <tr><td><a href="#profile-verifier">-profile-verifier</a></td><td>Verify profiling information</td></tr> <tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr> <tr><td><a href="#scev-aa">-scev-aa</a></td><td>ScalarEvolution-based Alias Analysis</td></tr> @@ -771,6 +772,17 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if ! <div class="doc_text"> <p>Pass that checks profiling information for plausibility.</p> </div> +<div class="doc_subsection"> + <a name="regions">-regions: Detect single entry single exit regions in a function</a> +</div> +<div class="doc_text"> + <p> + The <code>RegionInfo</code> 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. + </p> +</div> <!-------------------------------------------------------------------------- --> <div class="doc_subsection"> diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index ce3f7a6677..38bba77f5c 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 0000000000..c4ac1eb29c --- /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 0000000000..ced5b528cb --- /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 0000000000..758748aad9 --- /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 876703b903..4f3a019053 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 559f0040c2..f653f97e4e 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> diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index d9b670dea5..587f41332a 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -38,6 +38,8 @@ add_llvm_library(LLVMAnalysis ProfileInfoLoader.cpp ProfileInfoLoaderPass.cpp ProfileVerifierPass.cpp + RegionInfo.cpp + RegionPrinter.cpp ScalarEvolution.cpp ScalarEvolutionAliasAnalysis.cpp ScalarEvolutionExpander.cpp diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp new file mode 100644 index 0000000000..589cc471de --- /dev/null +++ b/lib/Analysis/RegionInfo.cpp @@ -0,0 +1,637 @@ +//===- RegionInfo.cpp - SESE region detection analysis --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// Detects single entry single exit regions in the control flow graph. +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/RegionInfo.h" +#include "llvm/Analysis/RegionIterator.h" + +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" + +#define DEBUG_TYPE "region" +#include "llvm/Support/Debug.h" + +#include <set> +#include <algorithm> + +using namespace llvm; + +// Always verify if expensive checking is enabled. +#ifdef XDEBUG +bool VerifyRegionInfo = true; +#else +bool VerifyRegionInfo = false; +#endif + +static cl::opt<bool,true> +VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo), + cl::desc("Verify region info (time consuming)")); + +STATISTIC(numRegions, "The # of regions"); +STATISTIC(numSimpleRegions, "The # of simple regions"); + +//===----------------------------------------------------------------------===// +/// PrintStyle - Print region in difference ways. +enum PrintStyle { PrintNone, PrintBB, PrintRN }; + +cl::opt<enum PrintStyle> printStyle("print-region-style", cl::Hidden, + cl::desc("style of printing regions"), + cl::values( + clEnumValN(PrintNone, "none", "print no details"), + clEnumValN(PrintBB, "bb", "print regions in detail with block_iterator"), + clEnumValN(PrintRN, "rn", "print regions in detail with element_iterator"), + clEnumValEnd)); +//===----------------------------------------------------------------------===// +/// Region Implementation +Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo, + DominatorTree *dt, Region *Parent) + : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} + +Region::~Region() { + // Only clean the cache for this Region. Caches of child Regions will be + // cleaned when the child Regions are deleted. + BBNodeMap.clear(); + + for (iterator I = begin(), E = end(); I != E; ++I) + delete *I; +} + +bool Region::contains(const BasicBlock *B) const { + BasicBlock *BB = const_cast<BasicBlock*>(B); + + assert(DT->getNode(BB) && "BB not part of the dominance tree"); + + BasicBlock *entry = getEntry(), *exit = getExit(); + + // Toplevel region. + if (!exit) + return true; + + return (DT->dominates(entry, BB) + && !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); +} + +bool Region::isSimple() const { + bool isSimple = true; + bool found = false; + + BasicBlock *entry = getEntry(), *exit = getExit(); + + // TopLevelRegion + if (!exit) + return false; + + for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE; + ++PI) + if (!contains(*PI)) { + if (found) { + isSimple = false; + break; + } + found = true; + } + + found = false; + + for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE; + ++PI) + if (contains(*PI)) { + if (found) { + isSimple = false; + break; + } + found = true; + } + + return isSimple; +} + +void Region::verifyBBInRegion(BasicBlock *BB) const { + if (!contains(BB)) + llvm_unreachable("Broken region found!"); + + BasicBlock *entry = getEntry(), *exit = getExit(); + + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) + if (!contains(*SI) && exit != *SI) + llvm_unreachable("Broken region found!"); + + if (entry != BB) + for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI) + if (!contains(*SI)) + llvm_unreachable("Broken region found!"); +} + +void Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const { + BasicBlock *exit = getExit(); + + visited->insert(BB); + + verifyBBInRegion(BB); + + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) + if (*SI != exit && visited->find(*SI) == visited->end()) + verifyWalk(*SI, visited); +} + +void Region::verifyRegion() const { + // Only do verification when user wants to, otherwise this expensive + // check will be invoked by PassManager. + if (!VerifyRegionInfo) return; + + std::set<BasicBlock*> visited; + verifyWalk(getEntry(), &visited); +} + +void Region::verifyRegionNest() const { + for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI) + (*RI)->verifyRegionNest(); + + verifyRegion(); +} + +Region::block_iterator Region::block_begin() { + return GraphTraits<FlatIt<Region*> >::nodes_begin(this); +} + +Region::block_iterator Region::block_end() { + return GraphTraits<FlatIt<Region*> >::nodes_end(this); +} + +Region::const_block_iterator Region::block_begin() const { + return GraphTraits<FlatIt<const Region*> >::nodes_begin(this); +} + +Region::const_block_iterator Region::block_end() const { + return GraphTraits<FlatIt<const Region*> >::nodes_end(this); +} + +Region::element_iterator Region::element_begin() { + return GraphTraits<Region*>::nodes_begin(this); +} + +Region::element_iterator Region::element_end() { + return GraphTraits<Region*>::nodes_end(this); +} + +Region::const_element_iterator Region::element_begin() const { + return GraphTraits<const Region*>::nodes_begin(this); +} + +Region::const_element_iterator Region::element_end() const { + return GraphTraits<const Region*>::nodes_end(this); +} + +Region* Region::getSubRegionNode(BasicBlock *BB) const { + Region *R = RI->getRegionFor(BB); + + if (!R || R == this) + return 0; + + // If we pass the BB out of this region, that means our code is broken. + assert(contains(R) && "BB not in current region!"); + + while (contains(R->getParent()) && R->getParent() != this) + R = R->getParent(); + + if (R->getEntry() != BB) + return 0; + + return R; +} + +RegionNode* Region::getBBNode(BasicBlock *BB) const { + assert(contains(BB) && "Can get BB node out of this region!"); + + BBNodeMapT::const_iterator at = BBNodeMap.find(BB); + + if (at != BBNodeMap.end()) + return at->second; + + RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB); + BBNodeMap.insert(std::make_pair(BB, NewNode)); + return NewNode; +} + +RegionNode* Region::getNode(BasicBlock *BB) const { + assert(contains(BB) && "Can get BB node out of this region!"); + if (Region* Child = getSubRegionNode(BB)) + return Child->getNode(); + + return getBBNode(BB); +} + +void Region::transferChildrenTo(Region *To) { + for (iterator I = begin(), E = end(); I != E; ++I) { + (*I)->parent = To; + To->children.push_back(*I); + } + children.clear(); +} + +void Region::addSubRegion(Region *SubRegion) { + assert(SubRegion->parent == 0 && "SubRegion already has a parent!"); + SubRegion->parent = this; + // Set up the region node. + assert(std::find(children.begin(), children.end(), SubRegion) == children.end() + && "Node already exist!"); + children.push_back(SubRegion); +} + + +Region *Region::removeSubRegion(Region *Child) { + assert(Child->parent == this && "Child is not a child of this region!"); + Child->parent = 0; + RegionSet::iterator I = std::find(children.begin(), children.end(), Child); + assert(I != children.end() && "Region does not exit. Unable to remove."); + children.erase(children.begin()+(I-begin())); + return Child; +} + +unsigned Region::getDepth() const { + unsigned Depth = 0; + + for (Region *R = parent; R != 0; R = R->parent) + ++Depth; + + return Depth; +} + +void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { + if (print_tree) + OS.indent(level*2) << "[" << level << "] " << getNameStr(); + else + OS.indent(level*2) << getNameStr(); + + OS << "\n"; + + + if (printStyle != PrintNone) { + OS.indent(level*2) << "{\n"; + OS.indent(level*2 + 2); + + if (printStyle == PrintBB) { + for (const_block_iterator I = block_begin(), E = block_end(); I!=E; ++I) + OS << **I << ", "; // TODO: remove the last "," + } else if (printStyle == PrintRN) { + for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) + OS << **I << ", "; // TODO: remove the last ", + } + + OS << "\n"; + } + + if (print_tree) + for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) + (*RI)->print(OS, print_tree, level+1); + + if (printStyle != PrintNone) + OS.indent(level*2) << "} \n"; +} + +void Region::dump() const { + print(dbgs(), true, getDepth()); +} + +void Region::clearNodeCache() { + BBNodeMap.clear(); + for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI) + (*RI)->clearNodeCache(); +} + +//===----------------------------------------------------------------------===// +// RegionInfo implementation +// + +bool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry, + BasicBlock *exit) const { + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) + if (DT->dominates(entry, *PI) && !DT->dominates(exit, *PI)) + return false; + + return true; +} + +bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const { + assert(entry && exit && "entry and exit must not be null!"); + typedef DominanceFrontier::DomSetType DST; + + DST *entrySuccs = &(*DF->find(entry)).second; + + // Exit is the header of a loop that contains the entry. In this case, + // the dominance frontier must only contain the exit. + if (!DT->dominates(entry, exit)) { + for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); + SI != SE; ++SI) + if (*SI != exit && *SI != entry) + return false; + + return true; + } + + DST *exitSuccs = &(*DF->find(exit)).second; + + // Do not allow edges leaving the region. + for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); + SI != SE; ++SI) { + if (*SI == exit || *SI == entry) + continue; + if (exitSuccs->find(*SI) == exitSuccs->end()) + return false; + if (!isCommonDomFrontier(*SI, entry, exit)) + return false; + } + + // Do not allow edges pointing into the region. + for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); + SI != SE; ++SI) + if (DT->dominates(entry, *SI) && *SI != entry && *SI != exit) + return false; + + + return true; +} + +void RegionInfo::insertShortCut(BasicBlock *entry, BasicBlock *exit, + BBtoBBMap *ShortCut) const { + assert(entry && exit && "entry and exit must not be null!"); + + BBtoBBMap::iterator e = ShortCut->find(exit); + + if (e == ShortCut->end()) + // No further region at exit available. + (*ShortCut)[entry] = exit; + else { + // We found a region e that starts at exit. Therefore (entry, e->second) + // is also a region, that is larger than (entry, exit). Insert the + // larger one. + BasicBlock *BB = e->second; + (*ShortCut)[entry] = BB; + } +} + +DomTreeNode* RegionInfo::getNextPostDom(DomTreeNode* N, + BBtoBBMap *ShortCut) const { + BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); + + if (e == ShortCut->end()) + return N->getIDom(); + + return PDT->getNode(e->second)->getIDom(); +} + +bool RegionInfo::isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const { + assert(entry && exit && "entry and exit must not be null!"); + + unsigned num_successors = succ_end(entry) - succ_begin(entry); + + if (num_successors <= 1 && exit == *(succ_begin(entry))) + return true; + + return false; +} + +void RegionInfo::updateStatistics(Region *R) { + ++numRegions; + + // TODO: Slow. Should only be enabled if -stats is used. + if (R->isSimple()) ++numSimpleRegions; +} + +Region *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) { + assert(entry && exit && "entry and exit must not be null!"); + + if (isTrivialRegion(entry, exit)) + return 0; + + Region *region = new Region(entry, exit, this, DT); + BBtoRegion.insert(std::make_pair(entry, region)); + + #ifdef XDEBUG + region->verifyRegion(); + #else + DEBUG(region->verifyRegion()); + #endif + + updateStatistics(region); + return region; +} + +void RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) { + assert(entry); + + DomTreeNode *N = PDT->getNode(entry); + + if (!N) + return; + + Region *lastRegion= 0; + BasicBlock *lastExit = entry; + + // As only a BasicBlock that postdominates entry can finish a region, walk the + // post dominance tree upwards. + while ((N = getNextPostDom(N, ShortCut))) { + BasicBlock *exit = N->getBlock(); + + if (!exit) + break; + + if (isRegion(entry, exit)) { + Region *newRegion = createRegion(entry, exit); + + if (lastRegion) + newRegion->addSubRegion(lastRegion); + + lastRegion = newRegion; + lastExit = exit; + } + + // This can never be a region, so stop the search. + if (!DT->dominates(entry, exit)) + break; + } + + // Tried to create regions from entry to lastExit. Next time take a + // shortcut from entry to lastExit. + if (lastExit != entry) + insertShortCut(entry, lastExit, ShortCut); +} + +void RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) { + BasicBlock *entry = &(F.getEntryBlock()); + DomTreeNode *N = DT->getNode(entry); + + // Iterate over the dominance tree in post order to start with the small + // regions from the bottom of the dominance tree. If the small regions are + // detected first, detection of bigger regions is faster, as we can jump + // over the small regions. + for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE; + ++FI) { + findRegionsWithEntry((*FI)->getBlock(), ShortCut); + } +} + +Region *RegionInfo::getTopMostParent(Region *region) { + while (region->parent) + region = region->getParent(); + + return region; +} + +void RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) { + BasicBlock *BB = N->getBlock(); + + // Passed region exit + while (BB == region->getExit()) + region = region->getParent(); + + BBtoRegionMap::iterator it = BBtoRegion.find(BB); + + // This basic block is a start block of a region. It is already in the + // BBtoRegion relation. Only the child basic blocks have to be updated. + if (it != BBtoRegion.end()) { + Region *newRegion = it->second;; + region->addSubRegion(getTopMostParent(newRegion)); + region = newRegion; + } else { + BBtoRegion[BB] = region; + } + + for (DomTreeNode::iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) + buildRegionsTree(*CI, region); +} + +void RegionInfo::releaseMemory() { + BBtoRegion.clear(); + if (TopLevelRegion) + delete TopLevelRegion; + TopLevelRegion = 0; +} + +RegionInfo::RegionInfo() : FunctionPass(&ID) { + TopLevelRegion = 0; +} + +RegionInfo::~RegionInfo() { + releaseMemory(); +} + +void RegionInfo::Calculate(Function &F) { + // ShortCut a function where for every BB the exit of the largest region + // starting with BB is stored. These regions can be threated as single BBS. + // This improves performance on linear CFGs. + BBtoBBMap ShortCut; + + scanForRegions(F, &ShortCut); + BasicBlock *BB = &F.getEntryBlock(); + buildRegionsTree(DT->getNode(BB), TopLevelRegion); +} + +bool RegionInfo::runOnFunction(Function &F) { + releaseMemory(); + + DT = &getAnalysis<DominatorTree>(); + PDT = &getAnalysis<PostDominatorTree>(); + DF = &getAnalysis<DominanceFrontier>(); + + TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0); + updateStatistics(TopLevelRegion); + + Calculate(F); + + return false; +} + +void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequiredTransitive<DominatorTree>(); + AU.addRequired<PostDominatorTree>(); + AU.addRequired<DominanceFrontier>(); +} + +void RegionInfo::print(raw_ostream &OS, const Module *) const { + OS << "Region tree:\n"; + TopLevelRegion->print(OS, true, 0); + OS << "End region tree\n"; +} + +void RegionInfo::verifyAnalysis() const { + // Only do verification when user wants to, otherwise this expensive check + // will be invoked by PMDataManager::verifyPreservedAnalysis when + // a regionpass (marked PreservedAll) finish. + if (!VerifyRegionInfo) return; + + TopLevelRegion->verifyRegionNest(); +} + +// Region pass manager support. +Region *RegionInfo::getRegionFor(BasicBlock *BB) const { + BBtoRegionMap::const_iterator I= + BBtoRegion.find(BB); + return I != BBtoRegion.end() ? I->second : 0; +} + +Region *RegionInfo::operator[](BasicBlock *BB) const { + return getRegionFor(BB); +} + +Region* +RegionInfo::getCommonRegion(Region *A, Region *B) const { + assert (A && B && "One of the Regions is NULL"); + + if (A->contains(B)) return A; + + while (!B->contains(A)) + B = B->getParent(); + + return B; +} + +Region* +RegionInfo::getCommonRegion(SmallVectorImpl<Region*> &Regions) const { + Region* ret = Regions.back(); + Regions.pop_back(); + + for (SmallVectorImpl<Region*>::const_iterator I = Regions.begin(), + E = Regions.end(); I != E; ++I) + ret = getCommonRegion(ret, *I); + + return ret; +} + +Region* +RegionInfo::getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const { + Region* ret = getRegionFor(BBs.back()); + BBs.pop_back(); + + for (SmallVectorImpl<BasicBlock*>::const_iterator I = BBs.begin(), + E = BBs.end(); I != E; ++I) + ret = getCommonRegion(ret, getRegionFor(*I)); + + return ret; +} + +char RegionInfo::ID = 0; +INITIALIZE_PASS(RegionInfo, "regions", + "Detect single entry single exit regions", true, true); + +// Create methods available outside of this file, to use them +// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by +// the link time optimization. + +namespace llvm { + FunctionPass *createRegionInfoPass() { + return new RegionInfo(); + } +} + diff --git a/lib/Analysis/RegionPrinter.cpp b/lib/Analysis/RegionPrinter.cpp new file mode 100644 index 0000000000..c657143da7 --- /dev/null +++ b/lib/Analysis/RegionPrinter.cpp @@ -0,0 +1,182 @@ +//===- RegionPrinter.cpp - Print regions tree pass ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// Print out the region tree of a function using dotty/graphviz. +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/RegionInfo.h" +#include "llvm/Analysis/RegionIterator.h" +#include "llvm/Analysis/RegionPrinter.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/DOTGraphTraitsPass.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +//===----------------------------------------------------------------------===// +/// onlySimpleRegion - Show only the simple regions in the RegionViewer. +static cl::opt<bool> +onlySimpleRegions("only-simple-regions", + cl::desc("Show only simple regions in the graphviz viewer"), + cl::Hidden, + cl::init(false)); + +namespace llvm { +template<> +struct DOTGraphTraits<RegionNode*> : public DefaultDOTGraphTraits { + + DOTGraphTraits (bool isSimple=false) + : DefaultDOTGraphTraits(isSimple) {} + + std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) { + + if (!Node->isSubRegion()) { + BasicBlock *BB = Node->getNodeAs<BasicBlock>(); + + if (isSimple()) + return DOTGraphTraits<const Function*> + ::getSimpleNodeLabel(BB, BB->getParent()); + else + return DOTGraphTraits<const Function*> + ::getCompleteNodeLabel(BB, BB->getParent()); + } + + return "Not implemented"; + } +}; + +template<> +struct DOTGraphTraits<RegionInfo*> : public DOTGraphTraits<RegionNode*> { + + DOTGraphTraits (bool isSimple=false) + : DOTGraphTraits<RegionNode*>(isSimple) {} + + static std::string getGraphName(RegionInfo *DT) { + return "Region Graph"; + } + + std::string getNodeLabel(RegionNode *Node, RegionInfo *G) { + return DOTGraphTraits<RegionNode*>::getNodeLabel(Node, + G->getTopLevelRegion()); + } + + // Print the cluster of the subregions. This groups the single basic blocks + // and adds a different background color for each group. + static void printRegionCluster(const Region *R, GraphWriter<RegionInfo*> &GW, + unsigned depth = 0) { + raw_ostream &O = GW.getOStream(); + O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void*>(R) + << " {\n"; + O.indent(2 * (depth + 1)) << "label = \"\";\n"; + + if (!onlySimpleRegions || R->isSimple()) { + O.indent(2 * (depth + 1)) << "style = filled;\n"; + O.indent(2 * (depth + 1)) << "color = " + << ((R->getDepth() * 2 % 12) + 1) << "\n"; + + } else { + O.indent(2 * (depth + 1)) << "style = solid;\n"; + O.indent(2 * (depth + 1)) << "color = " + << ((R->getDepth() * 2 % 12) + 2) << "\n"; + } + + for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI) + printRegionCluster(*RI, GW, depth + 1); + + RegionInfo *RI = R->getRegionInfo(); + + for (Region::const_block_iterator BI = R->block_begin(), + BE = R->block_end(); BI != BE; ++BI) { + BasicBlock *BB = (*BI)->getNodeAs<BasicBlock>(); + if (RI->getRegionFor(BB) == R) + O.indent(2 * (depth + 1)) << "Node" + << static_cast<const void*>(RI->getTopLevelRegion()->getBBNode(BB)) + << ";\n"; + } + + O.indent(2 * depth) << "}\n"; + } + + static void addCustomGraphFeatures(const RegionInfo* RI, + GraphWriter<RegionInfo*> &GW) { + raw_ostream &O = GW.getOStream(); + O << "\tcolorscheme = \"paired12\"\n"; + printRegionCluster(RI->getTopLevelRegion(), GW, 4); + } +}; +} //end namespace llvm + +namespace { + +struct RegionViewer + : public DOTGraphTraitsViewer<RegionInfo, false> { + static char ID; + RegionViewer() : DOTGraphTraitsViewer<RegionInfo, false>("reg", &ID){} +}; + +char RegionViewer::ID = 0; +INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function", + true, true); + +struct RegionOnlyViewer + : public DOTGraphTraitsViewer<RegionInfo, true> { + static char ID; + RegionOnlyViewer() : DOTGraphTraitsViewer<RegionInfo, true>("regonly", &ID){} +}; + +char RegionOnlyViewer::ID = 0; +INITIALIZE_PASS(RegionOnlyViewer, "view-regions-only", + "View regions of function (with no function bodies)", + true, true); + +struct RegionPrinter + : public DOTGraphTraitsPrinter<RegionInfo, false> { + static char ID; + RegionPrinter() : + DOTGraphTraitsPrinter<RegionInfo, false>("reg", &ID) {} +}; +} //end anonymous namespace + +char RegionPrinter::ID = 0; +INITIALIZE_PASS(RegionPrinter, "dot-regions", + "Print regions of function to 'dot' file", true, true); + +struct RegionOnlyPrinter + : public DOTGraphTraitsPrinter<RegionInfo, true> { + static char ID; + RegionOnlyPrinter() : + DOTGraphTraitsPrinter<RegionInfo, true>("reg", &ID) {} +}; + +char RegionOnlyPrinter::ID = 0; +INITIALIZE_PASS(RegionOnlyPrinter, "dot-regions-only", + "Print regions of function to 'dot' file " + "(with no function bodies)", + true, true); + +FunctionPass* llvm::createRegionViewerPass() { + return new RegionViewer(); +} + +FunctionPass* llvm::createRegionOnlyViewerPass() { + return new RegionOnlyViewer(); +} + +FunctionPass* llvm::createRegionPrinterPass() { + return new RegionPrinter(); +} + +FunctionPass* llvm::createRegionOnlyPrinterPass() { + return new RegionOnlyPrinter(); +} + diff --git a/test/Analysis/RegionInfo/block_sort.ll b/test/Analysis/RegionInfo/block_sort.ll new file mode 100644 index 0000000000..faec45a911 --- /dev/null +++ b/test/Analysis/RegionInfo/block_sort.ll @@ -0,0 +1,42 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats -analyze < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @BZ2_blockSort() nounwind { +start: + br label %while + +while: + br label %while.body134.i.i + +while.body134.i.i: + br i1 1, label %end, label %w + +w: + br label %if.end140.i.i + +if.end140.i.i: + br i1 1, label %while.end186.i.i, label %if.end183.i.i + +if.end183.i.i: + br label %while.body134.i.i + +while.end186.i.i: + br label %while + +end: + ret void +} +; CHECK-NOT: => +; CHECK: [0] start => <Function Return> +; CHECK: [1] while => end + +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: start, while, while.body134.i.i, end, w, if.end140.i.i, while.end186.i.i, if.end183.i.i, +; BBIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i, + +; RNIT: start, while => end, end, +; RNIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i, diff --git a/test/Analysis/RegionInfo/cond_loop.ll b/test/Analysis/RegionInfo/cond_loop.ll new file mode 100644 index 0000000000..2ce57c3c5f --- /dev/null +++ b/test/Analysis/RegionInfo/cond_loop.ll @@ -0,0 +1,33 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +5: + br label %"0" + +0: + br label %"1" +1: + br i1 1, label %"2", label %"3" +2: + ret void +3: + br i1 1, label %"1", label %"4" +4: + br label %"0" +} + +; CHECK-NOT: => +; CHECK: [0] 5 => <Function Return> +; CHECK: [1] 0 => 2 + +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 5, 0, 1, 2, 3, 4, +; BBIT: 0, 1, 3, 4, + +; RNIT: 5, 0 => 2, 2, +; RNIT: 0, 1, 3, 4, diff --git a/test/Analysis/RegionInfo/condition_complicated.ll b/test/Analysis/RegionInfo/condition_complicated.ll new file mode 100644 index 0000000000..7ca5c7c7b5 --- /dev/null +++ b/test/Analysis/RegionInfo/condition_complicated.ll @@ -0,0 +1,60 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc zeroext i8 @handle_compress() nounwind { +end165: + br i1 1, label %false239, label %true181 + +true181: + br i1 1, label %then187, label %else232 + +then187: + br label %end265 + +else232: + br i1 1, label %false239, label %then245 + +false239: + br i1 1, label %then245, label %else259 + +then245: + br i1 1, label %then251, label %end253 + +then251: + br label %end253 + +end253: + br label %end265 + +else259: + br label %end265 + +end265: + br i1 1, label %then291, label %end298 + +then291: + br label %end298 + +end298: + ret i8 1 +} + +; CHECK-NOT: => +; CHECK: [0] end165 => <Function Return> +; CHECK-NEXT: [1] end165 => end265 +; CHECK-NEXT: [2] then245 => end253 +; CHECK-NEXT: [1] end265 => end298 + +; STAT: 4 region - The # of regions + +; BBIT: end165, false239, then245, then251, end253, end265, then291, end298, else259, true181, then187, else232, +; BBIT: end165, false239, then245, then251, end253, else259, true181, then187, else232, +; BBIT: then245, then251, +; BBIT: end265, then291, + +; RNIT: end165 => end265, end265 => end298, end298, +; RNIT: end165, false239, then245 => end253, end253, else259, true181, then187, else232, +; RNIT: then245, then251, +; RNIT: end265, then291, diff --git a/test/Analysis/RegionInfo/condition_complicated_2.ll b/test/Analysis/RegionInfo/condition_complicated_2.ll new file mode 100644 index 0000000000..5fa940a61e --- /dev/null +++ b/test/Analysis/RegionInfo/condition_complicated_2.ll @@ -0,0 +1,44 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc void @compress() nounwind { +end33: + br i1 1, label %end124, label %lor.lhs.false95 + +lor.lhs.false95: + br i1 1, label %then107, label %end172 + +then107: + br i1 1, label %end124, label %then113 + +then113: + br label %end124 + +end124: + br label %exit + +end172: + br label %exit + + +exit: + unreachable + + +} +; CHECK-NOT: => +; CHECK: [0] end33 => <Function Return> +; CHECK-NEXT: [1] end33 => exit +; CHECK-NEXT: [2] then107 => end124 + +; STAT: 3 region - The # of regions + +; BBIT: end33, end124, exit, lor.lhs.false95, then107, then113, end172, +; BBIT: end33, end124, lor.lhs.false95, then107, then113, end172, +; BBIT: then107, then113, + +; RNIT: end33 => exit, exit, +; RNIT: end33, end124, lor.lhs.false95, then107 => end124, end172, +; RNIT: then107, then113, diff --git a/test/Analysis/RegionInfo/condition_forward_edge.ll b/test/Analysis/RegionInfo/condition_forward_edge.ll new file mode 100644 index 0000000000..098c9b6b46 --- /dev/null +++ b/test/Analysis/RegionInfo/condition_forward_edge.ll @@ -0,0 +1,26 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"1" +1: + br i1 1, label %"2", label %"3" +2: + br label %"3" +3: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK: [1] 1 => 3 + +; STAT: 2 region - The # of regions + +; BBIT: 0, 1, 2, 3, +; BBIT: 1, 2, + +; RNIT: 0, 1 => 3, 3, +; RNIT: 1, 2, diff --git a/test/Analysis/RegionInfo/condition_same_exit.ll b/test/Analysis/RegionInfo/condition_same_exit.ll new file mode 100644 index 0000000000..1b88596c0f --- /dev/null +++ b/test/Analysis/RegionInfo/condition_same_exit.ll @@ -0,0 +1,31 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br i1 1, label %"1", label %"4" + +1: + br i1 1, label %"2", label %"3" +2: + br label %"4" +3: + br label %"4" +4: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 0 => 4 +; CHECK-NEXT: [2] 1 => 4 +; STAT: 3 region - The # of regions + +; BBIT: 0, 1, 2, 4, 3, +; BBIT: 0, 1, 2, 3, +; BBIT: 1, 2, 3, + +; RNIT: 0 => 4, 4, +; RNIT: 0, 1 => 4, +; RNIT: 1, 2, 3, diff --git a/test/Analysis/RegionInfo/condition_simple.ll b/test/Analysis/RegionInfo/condition_simple.ll new file mode 100644 index 0000000000..19b154b647 --- /dev/null +++ b/test/Analysis/RegionInfo/condition_simple.ll @@ -0,0 +1,28 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"1" +1: + br i1 1, label %"2", label %"3" +2: + br label %"4" +3: + br label %"4" +4: + ret void +} + +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 1 => 4 +; STAT: 2 region - The # of regions + +; BBIT: 0, 1, 2, 4, 3, +; BBIT: 1, 2, 3, + +; RNIT: 0, 1 => 4, 4, +; RNIT: 1, 2, 3, diff --git a/test/Analysis/RegionInfo/dg.exp b/test/Analysis/RegionInfo/dg.exp new file mode 100644 index 0000000000..f2005891a5 --- /dev/null +++ b/test/Analysis/RegionInfo/dg.exp @@ -0,0 +1,3 @@ +load_lib llvm.exp + +RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]] diff --git a/test/Analysis/RegionInfo/exit_in_condition.ll b/test/Analysis/RegionInfo/exit_in_condition.ll new file mode 100644 index 0000000000..3b152d2f56 --- /dev/null +++ b/test/Analysis/RegionInfo/exit_in_condition.ll @@ -0,0 +1,38 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc zeroext i8 @handle_compress() nounwind { +entry: + br label %outer + +outer: + br label %body + +body: + br i1 1, label %body.i, label %if.end + +body.i: + br i1 1, label %end, label %if.end + +if.end: + br label %if.then64 + +if.then64: + br label %outer + +end: + ret i8 1 +} +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK-NEXT: [1] outer => end +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: entry, outer, body, body.i, end, if.end, if.then64, +; BBIT: outer, body, body.i, if.end, if.then64, + +; RNIT: entry, outer => end, end, +; RNIT: outer, body, body.i, if.end, if.then64, diff --git a/test/Analysis/RegionInfo/infinite_loop.ll b/test/Analysis/RegionInfo/infinite_loop.ll new file mode 100644 index 0000000000..59cead4926 --- /dev/null +++ b/test/Analysis/RegionInfo/infinite_loop.ll @@ -0,0 +1,20 @@ +; RUN: opt -regions -analyze < %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s + +define void @normal_condition() nounwind { +0: + br label %"1" +1: + br i1 1, label %"2", label %"3" +2: + br label %"2" +3: + br label %"4" +4: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK: [1] 1 => 4 +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions diff --git a/test/Analysis/RegionInfo/infinite_loop_2.ll b/test/Analysis/RegionInfo/infinite_loop_2.ll new file mode 100644 index 0000000000..80c69b7ab2 --- /dev/null +++ b/test/Analysis/RegionInfo/infinite_loop_2.ll @@ -0,0 +1,36 @@ +; RUN: opt -regions -analyze < %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"1" +1: + br i1 1, label %"2", label %"3" +2: + br label %"5" +5: + br i1 1, label %"11", label %"12" +11: + br label %"6" +12: + br label %"6" +6: + br label %"2" +3: + br label %"4" +4: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK: [1] 1 => 3 +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4, +; BBIT: 1, 2, 5, 11, 6, 12, + +; RNIT: 0, 1 => 3, 3, 4, +; RNIT: 1, 2, 5, 11, 6, 12, diff --git a/test/Analysis/RegionInfo/infinite_loop_3.ll b/test/Analysis/RegionInfo/infinite_loop_3.ll new file mode 100644 index 0000000000..74ceafb849 --- /dev/null +++ b/test/Analysis/RegionInfo/infinite_loop_3.ll @@ -0,0 +1,52 @@ +; RUN: opt -regions -analyze < %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s + +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"7" +7: + br i1 1, label %"1", label %"8" +1: + br i1 1, label %"2", label %"3" +2: + br label %"5" +5: + br i1 1, label %"11", label %"12" +11: + br label %"6" +12: + br label %"6" +6: + br label %"2" +8: + br label %"9" +9: + br i1 1, label %"13", label %"14" +13: + br label %"10" +14: + br label %"10" +10: + br label %"8" +3: + br label %"4" +4: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 1 => 3 +; CHECK-NEXT: [1] 7 => 1 +; STAT: 3 region - The # of regions +; STAT: 2 region - The # of simple regions + +; BBIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14, +; BBIT: 7, 8, 9, 13, 10, 14, +; BBIT: 1, 2, 5, 11, 6, 12, + +; RNIT: 0, 7 => 1, 1 => 3, 3, 4, +; RNIT: 7, 8, 9, 13, 10, 14, +; RNIT: 1, 2, 5, 11, 6, 12, diff --git a/test/Analysis/RegionInfo/infinite_loop_4.ll b/test/Analysis/RegionInfo/infinite_loop_4.ll new file mode 100644 index 0000000000..fd56af1d3b --- /dev/null +++ b/test/Analysis/RegionInfo/infinite_loop_4.ll @@ -0,0 +1,48 @@ +; RUN: opt -regions -analyze < %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"7" +7: + br i1 1, label %"1", label %"8" +1: + br i1 1, label %"2", label %"3" +2: + br label %"5" +5: + br i1 1, label %"11", label %"12" +11: + br label %"6" +12: + br label %"6" +6: + br i1 1, label %"2", label %"10" +8: + br label %"9" +9: + br i1 1, label %"13", label %"14" +13: + br label %"10" +14: + br label %"10" +10: + br label %"8" +3: + br label %"4" +4: + ret void +} +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 7 => 3 +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4, +; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, + +; RNIT: 0, 7 => 3, 3, 4, +; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, diff --git a/test/Analysis/RegionInfo/loop_with_condition.ll b/test/Analysis/RegionInfo/loop_with_condition.ll new file mode 100644 index 0000000000..d1d68982ee --- /dev/null +++ b/test/Analysis/RegionInfo/loop_with_condition.ll @@ -0,0 +1,46 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s + +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition() nounwind { +0: + br label %"1" +1: + br i1 1, label %"6", label %"2" +2: + br i1 1, label %"3", label %"4" +3: + br label %"5" +4: + br label %"5" +5: + br label %"8" +8: + br i1 1, label %"7", label %"9" +9: + br label %"2" +7: + br label %"6" +6: + ret void +} + +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 1 => 6 +; CHECK-NEXT: [2] 2 => 7 +; CHECK-NEXT: [3] 2 => 5 +; STAT: 4 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 0, 1, 6, 2, 3, 5, 8, 7, 9, 4, +; BBIT: 1, 2, 3, 5, 8, 7, 9, 4, +; BBIT: 2, 3, 5, 8, 9, 4, +; BBIT: 2, 3, 4, + +; RNIT: 0, 1 => 6, 6, +; RNIT: 1, 2 => 7, 7, +; RNIT: 2 => 5, 5, 8, 9, +; RNIT: 2, 3, 4, diff --git a/test/Analysis/RegionInfo/loops_1.ll b/test/Analysis/RegionInfo/loops_1.ll new file mode 100644 index 0000000000..d4bf3cc501 --- /dev/null +++ b/test/Analysis/RegionInfo/loops_1.ll @@ -0,0 +1,40 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc zeroext i8 @loops_1() nounwind { +entry: + br i1 1, label %outer , label %a + +a: + br label %body + +outer: + br label %body + +body: + br i1 1, label %land, label %if + +land: + br i1 1, label %exit, label %end + +exit: + br i1 1, label %if, label %end + +if: + br label %outer + +end: + ret i8 1 +} +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK-NEXT: [1] entry => end +; STAT: 2 region - The # of regions + +; BBIT: entry, outer, body, land, exit, if, end, a, +; BBIT: entry, outer, body, land, exit, if, a, + +; RNIT: entry => end, end, +; RNIT: entry, outer, body, land, exit, if, a, diff --git a/test/Analysis/RegionInfo/loops_2.ll b/test/Analysis/RegionInfo/loops_2.ll new file mode 100644 index 0000000000..07aa7c3110 --- /dev/null +++ b/test/Analysis/RegionInfo/loops_2.ll @@ -0,0 +1,49 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @meread_() nounwind { +entry: + br label %bb23 + +bb23: + br label %bb.i + +bb.i: ; preds = %bb.i, %bb54 + br label %pflini_.exit + +pflini_.exit: ; preds = %bb.i + br label %bb58thread-split + +bb58thread-split: ; preds = %bb64, %bb61, %pflini_.exit + br label %bb58 + +bb58: ; preds = %bb60, %bb58thread-split + br i1 1, label %bb59, label %bb23 + +bb59: ; preds = %bb58 + switch i32 1, label %bb60 [ + i32 1, label %l98 + ] + +bb60: ; preds = %bb59 + br i1 1, label %bb61, label %bb58 + +bb61: ; preds = %bb60 + br label %bb58thread-split + +l98: ; preds = %bb69, %bb59 + ret void +} +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK: [1] bb23 => l98 +; STAT: 2 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: entry, bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61, l98, +; BBIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61, + +; RNIT: entry, bb23 => l98, l98, +; RNIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61, diff --git a/test/Analysis/RegionInfo/mix_1.ll b/test/Analysis/RegionInfo/mix_1.ll new file mode 100644 index 0000000000..829c157c2c --- /dev/null +++ b/test/Analysis/RegionInfo/mix_1.ll @@ -0,0 +1,69 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s + +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @a_linear_impl_fig_1() nounwind { +0: + + br i1 1, label %"1", label %"15" +1: + switch i32 0, label %"2" [ i32 0, label %"3" + i32 1, label %"7"] +2: + br label %"4" +3: + br label %"5" +4: + br label %"6" +5: + br label %"6" +6: + br label %"7" +7: + br label %"15" +15: + br label %"8" +8: + br label %"16" +16: + br label %"9" +9: + br i1 1, label %"10", label %"11" +11: + br i1 1, label %"13", label %"12" +13: + br label %"14" +12: + br label %"14" +14: + br label %"8" +10: + br label %"17" +17: + br label %"18" +18: + ret void +} + +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 0 => 15 +; CHECK-NEXT: [2] 1 => 7 +; CHECK-NEXT: [1] 8 => 10 +; CHECK-NEXT: [2] 11 => 14 +; STAT: 5 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 0, 1, 2, 4, 6, 7, 15, 8, 16, 9, 10, 17, 18, 11, 13, 14, 12, 3, 5, +; BBIT: 0, 1, 2, 4, 6, 7, 3, 5, +; BBIT: 1, 2, 4, 6, 3, 5, +; BBIT: 8, 16, 9, 11, 13, 14, 12, +; BBIT: 11, 13, 12, + +; RNIT: 0 => 15, 15, 8 => 10, 10, 17, 18, +; RNIT: 0, 1 => 7, 7, +; RNIT: 1, 2, 4, 6, 3, 5, +; RNIT: 8, 16, 9, 11 => 14, 14, +; RNIT: 11, 13, 12, diff --git a/test/Analysis/RegionInfo/multiple_exiting_edge.ll b/test/Analysis/RegionInfo/multiple_exiting_edge.ll new file mode 100644 index 0000000000..7bc0e4607d --- /dev/null +++ b/test/Analysis/RegionInfo/multiple_exiting_edge.ll @@ -0,0 +1,38 @@ +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @normal_condition_0() nounwind { +bb38: ; preds = %bb34, %bb34, %bb37 + switch i32 undef, label %bb42 [ + i32 67, label %bb42 + i32 90, label %bb41 + ] +bb41: ; preds = %bb38 + br label %bb42 +bb42: ; preds = %bb38, %bb38, %bb41 + ret void +} + +; BBIT: bb38, bb42, bb41, +; BBIT: bb38, bb41, + +; RNIT: bb38 => bb42, bb42, +; RNIT: bb38, bb41, + +define void @normal_condition_1() nounwind { +bb38: ; preds = %bb34, %bb34, %bb37 + switch i32 undef, label %bb41 [ + i32 67, label %bb42 + i32 90, label %bb42 + ] +bb41: ; preds = %bb38 + br label %bb42 +bb42: ; preds = %bb38, %bb38, %bb41 + ret void +} + +; BBIT: bb38, bb41, bb42, +; BBIT: bb38, bb41, + +; RNIT: bb38 => bb42, bb42, +; RNIT: bb38, bb41, diff --git a/test/Analysis/RegionInfo/nested_loops.ll b/test/Analysis/RegionInfo/nested_loops.ll new file mode 100644 index 0000000000..9d8c4558f0 --- /dev/null +++ b/test/Analysis/RegionInfo/nested_loops.ll @@ -0,0 +1,33 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s + +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc zeroext i8 @handle_compress() nounwind { +entry: + br label %outer + +outer: + br label %body + +body: + br i1 1, label %exit172, label %end + +exit172: + br i1 1, label %end, label %outer + +end: + ret i8 1 +} +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK-NEXT: [1] outer => end + +; STAT: 2 region - The # of regions + +; BBIT: entry, outer, body, exit172, end, +; BBIT: outer, body, exit172, + +; RNIT: entry, outer => end, end, +; RNIT: outer, body, exit172, diff --git a/test/Analysis/RegionInfo/next.ll b/test/Analysis/RegionInfo/next.ll new file mode 100644 index 0000000000..d986387099 --- /dev/null +++ b/test/Analysis/RegionInfo/next.ll @@ -0,0 +1,49 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @MAIN__() nounwind { +entry: + br label %__label_002001.outer + +__label_002001.outer: ; preds = %bb236, %bb92 + br label %__label_002001 + +__label_002001: ; preds = %bb229, %__label_002001.outer + br i1 1, label %bb93, label %__label_000020 + +bb93: ; preds = %__label_002001 + br i1 1, label %__label_000020, label %bb197 + +bb197: ; preds = %bb193 + br i1 1, label %bb229, label %bb224 + +bb224: ; preds = %bb223, %bb227 + br i1 1, label %bb229, label %bb224 + +bb229: ; preds = %bb227, %bb223 + br i1 1, label %__label_002001, label %__label_002001.outer + +__label_000020: ; preds = %__label_002001, %bb194 + ret void +} + +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK-NEXT: [1] __label_002001.outer => __label_000020 +; CHECK-NEXT; [2] bb197 => bb229 +; CHECK-NEXT; [3] bb224 => bb229 + +; STAT: 4 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: entry, __label_002001.outer, __label_002001, bb93, __label_000020, bb197, bb229, bb224, +; BBIT: __label_002001.outer, __label_002001, bb93, bb197, bb229, bb224, +; BBIT: bb197, bb224, +; BBIT: bb224, + +; RNIT: entry, __label_002001.outer => __label_000020, __label_000020, +; RNIT: __label_002001.outer, __label_002001, bb93, bb197 => bb229, bb229, +; RNIT: bb197, bb224 => bb229, +; RNIT: bb224, diff --git a/test/Analysis/RegionInfo/paper.ll b/test/Analysis/RegionInfo/paper.ll new file mode 100644 index 0000000000..00b544bc69 --- /dev/null +++ b/test/Analysis/RegionInfo/paper.ll @@ -0,0 +1,55 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define void @a_linear_impl_fig_1() nounwind { +0: + br label %"1" +1: + br label %"2" +2: + br label %"3" +3: + br i1 1, label %"13", label %"4" +4: + br i1 1, label %"5", label %"1" +5: + br i1 1, label %"8", label %"6" +6: + br i1 1, label %"7", label %"4" +7: + ret void +8: + br i1 1, label %"9", label %"1" +9: + br label %"10" +10: + br i1 1, label %"12", label %"11" +11: + br i1 1, label %"9", label %"8" +13: + br i1 1, label %"2", label %"1" +12: + switch i32 0, label %"1" [ i32 0, label %"9" + i32 1, label %"8"] +} + +; CHECK-NOT: => +; CHECK: [0] 0 => <Function Return> +; CHECK-NEXT: [1] 1 => 7 +; CHECK-NEXT: [2] 1 => 4 +; CHECK-NEXT: [2] 8 => 1 + +; STAT: 4 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: 0, 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6, 7, +; BBIT: 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6, +; BBIT: 1, 2, 3, 13, +; BBIT: 8, 9, 10, 12, 11, + +; RNIT: 0, 1 => 7, 7, +; RNIT: 1 => 4, 4, 5, 8 => 1, 6, +; RNIT: 1, 2, 3, 13, +; RNIT: 8, 9, 10, 12, 11, diff --git a/test/Analysis/RegionInfo/two_loops_same_header.ll b/test/Analysis/RegionInfo/two_loops_same_header.ll new file mode 100644 index 0000000000..a97182b81a --- /dev/null +++ b/test/Analysis/RegionInfo/two_loops_same_header.ll @@ -0,0 +1,46 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s +; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s +; RUN: opt -regions -print-region-style=bb -analyze < %s |& FileCheck -check-prefix=BBIT %s +; RUN: opt -regions -print-region-style=rn -analyze < %s |& FileCheck -check-prefix=RNIT %s + +define internal fastcc zeroext i8 @handle_compress() nounwind { +entry: + br label %outer + +outer: + br label %body + +body: + br i1 1, label %else, label %true77 + +true77: + br i1 1, label %then83, label %else + +then83: + br label %outer + +else: + br label %else106 + +else106: + br i1 1, label %end, label %outer + +end: + ret i8 1 +} + +; CHECK-NOT: => +; CHECK: [0] entry => <Function Return> +; CHECK-NEXT: [1] outer => end +; CHECK-NEXT: [2] outer => else + +; STAT: 3 region - The # of regions +; STAT: 1 region - The # of simple regions + +; BBIT: entry, outer, body, else, else106, end, true77, then83, +; BBIT: outer, body, else, else106, true77, then83, +; BBIT: outer, body, true77, then83, + +; RNIT: entry, outer => end, end, +; RNIT: outer => else, else, else106, +; RNIT: outer, body, true77, then83, |