Lines Matching full:region
1 //===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===//
38 class Region;
44 /// @brief Marker class to iterate over the elements of a Region in flat mode.
55 /// Region.
61 /// This is the entry basic block that starts this region node. If this is a
68 /// The node can hold either a Region or a BasicBlock.
73 /// @brief The parent Region of this RegionNode.
75 Region* parent;
86 inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0)
89 /// @brief Get the parent Region of this RegionNode.
91 /// The parent Region is the Region this RegionNode belongs to. If for
94 /// pointing to the Region this RegionNode belongs to.
96 /// @return Get the parent Region of this RegionNode.
97 inline Region* getParent() const { return parent; }
135 inline Region* RegionNode::getNodeAs<Region>() const {
137 return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
141 /// @brief A single entry single exit Region.
143 /// A Region is a connected subgraph of a control flow graph that has exactly
147 /// A <em> simple Region </em> is connected to the remaining graph by just two
148 /// edges. One edge entering the Region and another one leaving the Region.
150 /// An <em> extended Region </em> (or just Region) is a subgraph that can be
151 /// transform into a simple Region. The transformation is done by adding
155 /// The \e Entry of a Region is the first BasicBlock that is passed after
156 /// entering the Region. It is an element of the Region. The entry BasicBlock
157 /// dominates all BasicBlocks in the Region.
159 /// The \e Exit of a Region is the first BasicBlock that is passed after
160 /// leaving the Region. It is not an element of the Region. The exit BasicBlock,
161 /// postdominates all BasicBlocks in the Region.
163 /// A <em> canonical Region </em> cannot be constructed by combining smaller
166 /// Region A is the \e parent of Region B, if B is completely contained in A.
188 /// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
189 /// 9 Region B: 2 -> 9 {2,4,5,6,7}
202 class Region : public RegionNode {
204 Region(const Region &) LLVM_DELETED_FUNCTION;
205 const Region &operator=(const Region &) LLVM_DELETED_FUNCTION;
207 // Information necessary to manage this Region.
211 // The exit BasicBlock of this region.
215 typedef std::vector<Region*> RegionSet;
217 // The subregions of this region.
222 // Save the BasicBlock RegionNodes that are element of this Region.
225 /// verifyBBInRegion - Check if a BB is in this Region. This check also works
226 /// if the region is incorrectly built. (EXPENSIVE!)
229 /// verifyWalk - Walk over all the BBs of the region starting from BB and
230 /// verify that all reachable basic blocks are elements of the region.
234 /// verifyRegionNest - Verify if the region and its children are valid
239 /// @brief Create a new region.
241 /// @param Entry The entry basic block of the region.
242 /// @param Exit The exit basic block of the region.
243 /// @param RI The region info object that is managing this region.
245 /// @param Parent The surrounding region or NULL if this is a top level
246 /// region.
247 Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI,
248 DominatorTree *DT, Region *Parent = 0);
250 /// Delete the Region and all its subregions.
251 ~Region();
253 /// @brief Get the entry BasicBlock of the Region.
254 /// @return The entry BasicBlock of the region.
257 /// @brief Replace the entry basic block of the region with the new basic
260 /// @param BB The new entry basic block of the region.
263 /// @brief Replace the exit basic block of the region with the new basic
266 /// @param BB The new exit basic block of the region.
269 /// @brief Get the exit BasicBlock of the Region.
270 /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
271 /// Region.
274 /// @brief Get the parent of the Region.
275 /// @return The parent of the Region or NULL if this is a top level
276 /// Region.
277 Region *getParent() const { return RegionNode::getParent(); }
279 /// @brief Get the RegionNode representing the current Region.
280 /// @return The RegionNode representing the current Region.
285 /// @brief Get the nesting level of this Region.
287 /// An toplevel Region has depth 0.
289 /// @return The depth of the region.
292 /// @brief Check if a Region is the TopLevel region.
294 /// The toplevel region represents the whole function.
297 /// @brief Return a new (non canonical) region, that is obtained by joining
298 /// this region with its predecessors.
300 /// @return A region also starting at getEntry(), but reaching to the next
301 /// basic block that forms with getEntry() a (non canonical) region.
303 Region *getExpandedRegion() const;
305 /// @brief Return the first block of this region's single entry edge,
308 /// @return The BasicBlock starting this region's single entry edge,
312 /// @brief Return the first block of this region's single exit edge,
315 /// @return The BasicBlock starting this region's single exit edge,
319 /// @brief Is this a simple region?
321 /// A region is simple if it has exactly one exit and one entry edge.
323 /// @return True if the Region is simple.
326 /// @brief Returns the name of the Region.
327 /// @return The Name of the Region.
330 /// @brief Return the RegionInfo object, that belongs to this Region.
335 /// PrintStyle - Print region in difference ways.
338 /// @brief Print the region.
340 /// @param OS The output stream the Region is printed to.
346 /// @brief Print the region to stderr.
349 /// @brief Check if the region contains a BasicBlock.
351 /// @param BB The BasicBlock that might be contained in this Region.
352 /// @return True if the block is contained in the region otherwise false.
355 /// @brief Check if the region contains another region.
357 /// @param SubRegion The region that might be contained in this Region.
358 /// @return True if SubRegion is contained in the region otherwise false.
359 bool contains(const Region *SubRegion) const {
360 // Toplevel Region.
368 /// @brief Check if the region contains an Instruction.
370 /// @param Inst The Instruction that might be contained in this region.
371 /// @return True if the Instruction is contained in the region otherwise false.
376 /// @brief Check if the region contains a loop.
378 /// @param L The loop that might be contained in this region.
379 /// @return True if the loop is contained in the region otherwise false.
381 /// is false, except for the region that describes the whole function.
385 /// @brief Get the outermost loop in the region that contains a loop.
388 /// and is itself contained in the region.
391 /// @return The outermost loop in the region, NULL if such a loop does not
392 /// exist or if the region describes the whole function.
395 /// @brief Get the outermost loop in the region that contains a basic block.
398 /// itself contained in the region.
402 /// @return The outermost loop in the region, NULL if such a loop does not
403 /// exist or if the region describes the whole function.
410 Region* getSubRegionNode(BasicBlock *BB) const;
426 /// @brief Add a new subregion to this Region.
429 /// @param moveChildren Move the children of this region
431 void addSubRegion(Region *SubRegion, bool moveChildren = false);
433 /// @brief Remove a subregion from this Region.
436 /// region.
438 Region *removeSubRegion(Region *SubRegion);
440 /// @brief Move all direct child nodes of this Region to another Region.
442 /// @param To The Region the child nodes will be transferred to.
443 void transferChildrenTo(Region *To);
445 /// @brief Verify if the region is a correct region.
447 /// Check if this is a correctly build Region. This is an expensive check, as
448 /// the complete CFG of the Region will be walked.
460 /// These iterators iterator over all subregions of this Region.
475 /// Region. The iterator also iterates over BasicBlocks that are elements of
476 /// a subregion of this Region. It is therefore called a flat iterator.
494 // Mark the exit of the region as visited, so that the children of the
495 // exit and the exit itself, i.e. the block outside the region will never
535 /// are direct children of this Region. It does not iterate over any
536 /// RegionNodes that are also element of a subregion of this Region.
561 typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
562 typedef SmallPtrSet<Region*, 4> RegionSet;
571 /// The top level region.
572 Region *TopLevelRegion;
574 /// Map every BB to the smallest region, that contains BB.
583 // isRegion - Check if entry and exit surround a valid region, based on
593 // all post dominators that cannot finish a canonical region.
596 // isTrivialRegion - A region is trivial, if it contains only one BB.
599 // createRegion - Creates a single entry single exit region.
600 Region *createRegion(BasicBlock *entry, BasicBlock *exit);
609 Region *getTopMostParent(Region *region);
611 // buildRegionsTree - build the region hierarchy after all region detected.
612 void buildRegionsTree(DomTreeNode *N, Region *region);
614 // Calculate - detecte all regions in function and build the region tree.
620 void updateStatistics(Region *R);
622 // isSimple - Check if a region is a simple region with exactly one entry
624 bool isSimple(Region* R) const;
640 /// @brief Get the smallest region that contains a BasicBlock.
643 /// @return The smallest region, that contains BB or NULL, if there is no
644 /// region containing BB.
645 Region *getRegionFor(BasicBlock *BB) const;
647 /// @brief Set the smallest region that surrounds a basic block.
649 /// @param BB The basic block surrounded by a region.
650 /// @param R The smallest region that surrounds BB.
651 void setRegionFor(BasicBlock *BB, Region *R);
656 /// @return The smallest region, that contains BB or NULL, if there is no
657 /// region containing BB.
658 Region *operator[](BasicBlock *BB) const;
660 /// @brief Return the exit of the maximal refined region, that starts at a
663 /// @param BB The BasicBlock the refined region starts.
666 /// @brief Find the smallest region that contains two regions.
668 /// @param A The first region.
669 /// @param B The second region.
670 /// @return The smallest region containing A and B.
671 Region *getCommonRegion(Region* A, Region *B) const;
673 /// @brief Find the smallest region that contains two basic blocks.
677 /// @return The smallest region that contains A and B.
678 Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const {
682 /// @brief Find the smallest region that contains a set of regions.
685 /// @return The smallest region that contains all regions in Regions.
686 Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const;
688 /// @brief Find the smallest region that contains a set of basic blocks.
691 /// @return The smallest region that contains all basic blocks in BBS.
692 Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const;
694 Region *getTopLevelRegion() const {
706 /// @see Region::clearNodeCache()
715 return OS << Node.getNodeAs<Region>()->getNameStr();
