1 //===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Calculate a program structure tree built out of single entry single exit
11 // The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
12 // David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
13 // Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
15 // The algorithm to calculate these data structures however is completely
16 // different, as it takes advantage of existing information already available
17 // in (Post)dominace tree and dominance frontier passes. This leads to a simpler
18 // and in practice hopefully better performing algorithm. The runtime of the
19 // algorithms described in the papers above are both linear in graph size,
20 // O(V+E), whereas this algorithm is not, as the dominance frontier information
21 // itself is not, but in practice runtime seems to be in the order of magnitude
22 // of dominance tree calculation.
24 // WARNING: LLVM is generally very concerned about compile time such that
25 // the use of additional analysis passes in the default
26 // optimization sequence is avoided as much as possible.
27 // Specifically, if you do not need the RegionInfo, but dominance
28 // information could be sufficient please base your work only on
29 // the dominator tree. Most passes maintain it, such that using
30 // it has often near zero cost. In contrast RegionInfo is by
31 // default not available, is not maintained by existing
32 // transformations and there is no intention to do so.
34 //===----------------------------------------------------------------------===//
36 #ifndef LLVM_ANALYSIS_REGIONINFO_H
37 #define LLVM_ANALYSIS_REGIONINFO_H
39 #include "llvm/ADT/DenseMap.h"
40 #include "llvm/ADT/DepthFirstIterator.h"
41 #include "llvm/ADT/GraphTraits.h"
42 #include "llvm/ADT/PointerIntPair.h"
43 #include "llvm/ADT/iterator_range.h"
44 #include "llvm/Config/llvm-config.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/Dominators.h"
47 #include "llvm/IR/PassManager.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/raw_ostream.h"
56 #include <type_traits>
61 class DominanceFrontier
;
65 class PostDominatorTree
;
67 template <class RegionTr
> class RegionBase
;
69 template <class RegionTr
> class RegionInfoBase
;
72 // Class to be specialized for different users of RegionInfo
73 // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to
74 // pass around an unreasonable number of template parameters.
75 template <class FuncT_
>
82 using BrokenT
= typename
FuncT_::UnknownRegionTypeError
;
86 struct RegionTraits
<Function
> {
87 using FuncT
= Function
;
88 using BlockT
= BasicBlock
;
89 using RegionT
= Region
;
90 using RegionNodeT
= RegionNode
;
91 using RegionInfoT
= RegionInfo
;
92 using DomTreeT
= DominatorTree
;
93 using DomTreeNodeT
= DomTreeNode
;
94 using DomFrontierT
= DominanceFrontier
;
95 using PostDomTreeT
= PostDominatorTree
;
96 using InstT
= Instruction
;
98 using LoopInfoT
= LoopInfo
;
100 static unsigned getNumSuccessors(BasicBlock
*BB
) {
101 return BB
->getTerminator()->getNumSuccessors();
105 /// Marker class to iterate over the elements of a Region in flat mode.
107 /// The class is used to either iterate in Flat mode or by not using it to not
108 /// iterate in Flat mode. During a Flat mode iteration all Regions are entered
109 /// and the iteration returns every BasicBlock. If the Flat mode is not
110 /// selected for SubRegions just one RegionNode containing the subregion is
112 template <class GraphType
>
115 /// A RegionNode represents a subregion or a BasicBlock that is part of a
118 class RegionNodeBase
{
119 friend class RegionBase
<Tr
>;
122 using BlockT
= typename
Tr::BlockT
;
123 using RegionT
= typename
Tr::RegionT
;
126 /// This is the entry basic block that starts this region node. If this is a
127 /// BasicBlock RegionNode, then entry is just the basic block, that this
128 /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode.
130 /// In the BBtoRegionNode map of the parent of this node, BB will always map
131 /// to this node no matter which kind of node this one is.
133 /// The node can hold either a Region or a BasicBlock.
134 /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
136 PointerIntPair
<BlockT
*, 1, bool> entry
;
138 /// The parent Region of this RegionNode.
143 /// Create a RegionNode.
145 /// @param Parent The parent of this RegionNode.
146 /// @param Entry The entry BasicBlock of the RegionNode. If this
147 /// RegionNode represents a BasicBlock, this is the
148 /// BasicBlock itself. If it represents a subregion, this
149 /// is the entry BasicBlock of the subregion.
150 /// @param isSubRegion If this RegionNode represents a SubRegion.
151 inline RegionNodeBase(RegionT
*Parent
, BlockT
*Entry
,
152 bool isSubRegion
= false)
153 : entry(Entry
, isSubRegion
), parent(Parent
) {}
156 RegionNodeBase(const RegionNodeBase
&) = delete;
157 RegionNodeBase
&operator=(const RegionNodeBase
&) = delete;
159 /// Get the parent Region of this RegionNode.
161 /// The parent Region is the Region this RegionNode belongs to. If for
162 /// example a BasicBlock is element of two Regions, there exist two
163 /// RegionNodes for this BasicBlock. Each with the getParent() function
164 /// pointing to the Region this RegionNode belongs to.
166 /// @return Get the parent Region of this RegionNode.
167 inline RegionT
*getParent() const { return parent
; }
169 /// Get the entry BasicBlock of this RegionNode.
171 /// If this RegionNode represents a BasicBlock this is just the BasicBlock
172 /// itself, otherwise we return the entry BasicBlock of the Subregion
174 /// @return The entry BasicBlock of this RegionNode.
175 inline BlockT
*getEntry() const { return entry
.getPointer(); }
177 /// Get the content of this RegionNode.
179 /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
180 /// check the type of the content with the isSubRegion() function call.
182 /// @return The content of this RegionNode.
183 template <class T
> inline T
*getNodeAs() const;
185 /// Is this RegionNode a subregion?
187 /// @return True if it contains a subregion. False if it contains a
189 inline bool isSubRegion() const { return entry
.getInt(); }
192 //===----------------------------------------------------------------------===//
193 /// A single entry single exit Region.
195 /// A Region is a connected subgraph of a control flow graph that has exactly
196 /// two connections to the remaining graph. It can be used to analyze or
197 /// optimize parts of the control flow graph.
199 /// A <em> simple Region </em> is connected to the remaining graph by just two
200 /// edges. One edge entering the Region and another one leaving the Region.
202 /// An <em> extended Region </em> (or just Region) is a subgraph that can be
203 /// transform into a simple Region. The transformation is done by adding
204 /// BasicBlocks that merge several entry or exit edges so that after the merge
205 /// just one entry and one exit edge exists.
207 /// The \e Entry of a Region is the first BasicBlock that is passed after
208 /// entering the Region. It is an element of the Region. The entry BasicBlock
209 /// dominates all BasicBlocks in the Region.
211 /// The \e Exit of a Region is the first BasicBlock that is passed after
212 /// leaving the Region. It is not an element of the Region. The exit BasicBlock,
213 /// postdominates all BasicBlocks in the Region.
215 /// A <em> canonical Region </em> cannot be constructed by combining smaller
218 /// Region A is the \e parent of Region B, if B is completely contained in A.
220 /// Two canonical Regions either do not intersect at all or one is
221 /// the parent of the other.
223 /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
224 /// Regions in the control flow graph and E is the \e parent relation of these
230 /// A simple control flow graph, that contains two regions.
240 /// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
241 /// 9 Region B: 2 -> 9 {2,4,5,6,7}
244 /// You can obtain more examples by either calling
246 /// <tt> "opt -regions -analyze anyprogram.ll" </tt>
248 /// <tt> "opt -view-regions-only anyprogram.ll" </tt>
250 /// on any LLVM file you are interested in.
252 /// The first call returns a textual representation of the program structure
253 /// tree, the second one creates a graphical representation using graphviz.
255 class RegionBase
: public RegionNodeBase
<Tr
> {
256 friend class RegionInfoBase
<Tr
>;
258 using FuncT
= typename
Tr::FuncT
;
259 using BlockT
= typename
Tr::BlockT
;
260 using RegionInfoT
= typename
Tr::RegionInfoT
;
261 using RegionT
= typename
Tr::RegionT
;
262 using RegionNodeT
= typename
Tr::RegionNodeT
;
263 using DomTreeT
= typename
Tr::DomTreeT
;
264 using LoopT
= typename
Tr::LoopT
;
265 using LoopInfoT
= typename
Tr::LoopInfoT
;
266 using InstT
= typename
Tr::InstT
;
268 using BlockTraits
= GraphTraits
<BlockT
*>;
269 using InvBlockTraits
= GraphTraits
<Inverse
<BlockT
*>>;
270 using SuccIterTy
= typename
BlockTraits::ChildIteratorType
;
271 using PredIterTy
= typename
InvBlockTraits::ChildIteratorType
;
273 // Information necessary to manage this Region.
277 // The exit BasicBlock of this region.
278 // (The entry BasicBlock is part of RegionNode)
281 using RegionSet
= std::vector
<std::unique_ptr
<RegionT
>>;
283 // The subregions of this region.
286 using BBNodeMapT
= std::map
<BlockT
*, std::unique_ptr
<RegionNodeT
>>;
288 // Save the BasicBlock RegionNodes that are element of this Region.
289 mutable BBNodeMapT BBNodeMap
;
291 /// Check if a BB is in this Region. This check also works
292 /// if the region is incorrectly built. (EXPENSIVE!)
293 void verifyBBInRegion(BlockT
*BB
) const;
295 /// Walk over all the BBs of the region starting from BB and
296 /// verify that all reachable basic blocks are elements of the region.
298 void verifyWalk(BlockT
*BB
, std::set
<BlockT
*> *visitedBB
) const;
300 /// Verify if the region and its children are valid regions (EXPENSIVE!)
301 void verifyRegionNest() const;
304 /// Create a new region.
306 /// @param Entry The entry basic block of the region.
307 /// @param Exit The exit basic block of the region.
308 /// @param RI The region info object that is managing this region.
309 /// @param DT The dominator tree of the current function.
310 /// @param Parent The surrounding region or NULL if this is a top level
312 RegionBase(BlockT
*Entry
, BlockT
*Exit
, RegionInfoT
*RI
, DomTreeT
*DT
,
313 RegionT
*Parent
= nullptr);
315 RegionBase(const RegionBase
&) = delete;
316 RegionBase
&operator=(const RegionBase
&) = delete;
318 /// Delete the Region and all its subregions.
321 /// Get the entry BasicBlock of the Region.
322 /// @return The entry BasicBlock of the region.
323 BlockT
*getEntry() const {
324 return RegionNodeBase
<Tr
>::getEntry();
327 /// Replace the entry basic block of the region with the new basic
330 /// @param BB The new entry basic block of the region.
331 void replaceEntry(BlockT
*BB
);
333 /// Replace the exit basic block of the region with the new basic
336 /// @param BB The new exit basic block of the region.
337 void replaceExit(BlockT
*BB
);
339 /// Recursively replace the entry basic block of the region.
341 /// This function replaces the entry basic block with a new basic block. It
342 /// also updates all child regions that have the same entry basic block as
345 /// @param NewEntry The new entry basic block.
346 void replaceEntryRecursive(BlockT
*NewEntry
);
348 /// Recursively replace the exit basic block of the region.
350 /// This function replaces the exit basic block with a new basic block. It
351 /// also updates all child regions that have the same exit basic block as
354 /// @param NewExit The new exit basic block.
355 void replaceExitRecursive(BlockT
*NewExit
);
357 /// Get the exit BasicBlock of the Region.
358 /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
360 BlockT
*getExit() const { return exit
; }
362 /// Get the parent of the Region.
363 /// @return The parent of the Region or NULL if this is a top level
365 RegionT
*getParent() const {
366 return RegionNodeBase
<Tr
>::getParent();
369 /// Get the RegionNode representing the current Region.
370 /// @return The RegionNode representing the current Region.
371 RegionNodeT
*getNode() const {
372 return const_cast<RegionNodeT
*>(
373 reinterpret_cast<const RegionNodeT
*>(this));
376 /// Get the nesting level of this Region.
378 /// An toplevel Region has depth 0.
380 /// @return The depth of the region.
381 unsigned getDepth() const;
383 /// Check if a Region is the TopLevel region.
385 /// The toplevel region represents the whole function.
386 bool isTopLevelRegion() const { return exit
== nullptr; }
388 /// Return a new (non-canonical) region, that is obtained by joining
389 /// this region with its predecessors.
391 /// @return A region also starting at getEntry(), but reaching to the next
392 /// basic block that forms with getEntry() a (non-canonical) region.
393 /// NULL if such a basic block does not exist.
394 RegionT
*getExpandedRegion() const;
396 /// Return the first block of this region's single entry edge,
399 /// @return The BasicBlock starting this region's single entry edge,
401 BlockT
*getEnteringBlock() const;
403 /// Return the first block of this region's single exit edge,
406 /// @return The BasicBlock starting this region's single exit edge,
408 BlockT
*getExitingBlock() const;
410 /// Collect all blocks of this region's single exit edge, if existing.
412 /// @return True if this region contains all the predecessors of the exit.
413 bool getExitingBlocks(SmallVectorImpl
<BlockT
*> &Exitings
) const;
415 /// Is this a simple region?
417 /// A region is simple if it has exactly one exit and one entry edge.
419 /// @return True if the Region is simple.
420 bool isSimple() const;
422 /// Returns the name of the Region.
423 /// @return The Name of the Region.
424 std::string
getNameStr() const;
426 /// Return the RegionInfo object, that belongs to this Region.
427 RegionInfoT
*getRegionInfo() const { return RI
; }
429 /// PrintStyle - Print region in difference ways.
430 enum PrintStyle
{ PrintNone
, PrintBB
, PrintRN
};
432 /// Print the region.
434 /// @param OS The output stream the Region is printed to.
435 /// @param printTree Print also the tree of subregions.
436 /// @param level The indentation level used for printing.
437 void print(raw_ostream
&OS
, bool printTree
= true, unsigned level
= 0,
438 PrintStyle Style
= PrintNone
) const;
440 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
441 /// Print the region to stderr.
445 /// Check if the region contains a BasicBlock.
447 /// @param BB The BasicBlock that might be contained in this Region.
448 /// @return True if the block is contained in the region otherwise false.
449 bool contains(const BlockT
*BB
) const;
451 /// Check if the region contains another region.
453 /// @param SubRegion The region that might be contained in this Region.
454 /// @return True if SubRegion is contained in the region otherwise false.
455 bool contains(const RegionT
*SubRegion
) const {
460 return contains(SubRegion
->getEntry()) &&
461 (contains(SubRegion
->getExit()) ||
462 SubRegion
->getExit() == getExit());
465 /// Check if the region contains an Instruction.
467 /// @param Inst The Instruction that might be contained in this region.
468 /// @return True if the Instruction is contained in the region otherwise
470 bool contains(const InstT
*Inst
) const { return contains(Inst
->getParent()); }
472 /// Check if the region contains a loop.
474 /// @param L The loop that might be contained in this region.
475 /// @return True if the loop is contained in the region otherwise false.
476 /// In case a NULL pointer is passed to this function the result
477 /// is false, except for the region that describes the whole function.
478 /// In that case true is returned.
479 bool contains(const LoopT
*L
) const;
481 /// Get the outermost loop in the region that contains a loop.
483 /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
484 /// and is itself contained in the region.
486 /// @param L The loop the lookup is started.
487 /// @return The outermost loop in the region, NULL if such a loop does not
488 /// exist or if the region describes the whole function.
489 LoopT
*outermostLoopInRegion(LoopT
*L
) const;
491 /// Get the outermost loop in the region that contains a basic block.
493 /// Find for a basic block BB the outermost loop L that contains BB and is
494 /// itself contained in the region.
496 /// @param LI A pointer to a LoopInfo analysis.
497 /// @param BB The basic block surrounded by the loop.
498 /// @return The outermost loop in the region, NULL if such a loop does not
499 /// exist or if the region describes the whole function.
500 LoopT
*outermostLoopInRegion(LoopInfoT
*LI
, BlockT
*BB
) const;
502 /// Get the subregion that starts at a BasicBlock
504 /// @param BB The BasicBlock the subregion should start.
505 /// @return The Subregion if available, otherwise NULL.
506 RegionT
*getSubRegionNode(BlockT
*BB
) const;
508 /// Get the RegionNode for a BasicBlock
510 /// @param BB The BasicBlock at which the RegionNode should start.
511 /// @return If available, the RegionNode that represents the subregion
512 /// starting at BB. If no subregion starts at BB, the RegionNode
514 RegionNodeT
*getNode(BlockT
*BB
) const;
516 /// Get the BasicBlock RegionNode for a BasicBlock
518 /// @param BB The BasicBlock for which the RegionNode is requested.
519 /// @return The RegionNode representing the BB.
520 RegionNodeT
*getBBNode(BlockT
*BB
) const;
522 /// Add a new subregion to this Region.
524 /// @param SubRegion The new subregion that will be added.
525 /// @param moveChildren Move the children of this region, that are also
526 /// contained in SubRegion into SubRegion.
527 void addSubRegion(RegionT
*SubRegion
, bool moveChildren
= false);
529 /// Remove a subregion from this Region.
531 /// The subregion is not deleted, as it will probably be inserted into another
533 /// @param SubRegion The SubRegion that will be removed.
534 RegionT
*removeSubRegion(RegionT
*SubRegion
);
536 /// Move all direct child nodes of this Region to another Region.
538 /// @param To The Region the child nodes will be transferred to.
539 void transferChildrenTo(RegionT
*To
);
541 /// Verify if the region is a correct region.
543 /// Check if this is a correctly build Region. This is an expensive check, as
544 /// the complete CFG of the Region will be walked.
545 void verifyRegion() const;
547 /// Clear the cache for BB RegionNodes.
549 /// After calling this function the BasicBlock RegionNodes will be stored at
550 /// different memory locations. RegionNodes obtained before this function is
551 /// called are therefore not comparable to RegionNodes abtained afterwords.
552 void clearNodeCache();
554 /// @name Subregion Iterators
556 /// These iterators iterator over all subregions of this Region.
558 using iterator
= typename
RegionSet::iterator
;
559 using const_iterator
= typename
RegionSet::const_iterator
;
561 iterator
begin() { return children
.begin(); }
562 iterator
end() { return children
.end(); }
564 const_iterator
begin() const { return children
.begin(); }
565 const_iterator
end() const { return children
.end(); }
568 /// @name BasicBlock Iterators
570 /// These iterators iterate over all BasicBlocks that are contained in this
571 /// Region. The iterator also iterates over BasicBlocks that are elements of
572 /// a subregion of this Region. It is therefore called a flat iterator.
574 template <bool IsConst
>
575 class block_iterator_wrapper
576 : public df_iterator
<
577 typename
std::conditional
<IsConst
, const BlockT
, BlockT
>::type
*> {
580 typename
std::conditional
<IsConst
, const BlockT
, BlockT
>::type
*>;
583 using Self
= block_iterator_wrapper
<IsConst
>;
584 using value_type
= typename
super::value_type
;
586 // Construct the begin iterator.
587 block_iterator_wrapper(value_type Entry
, value_type Exit
)
588 : super(df_begin(Entry
)) {
589 // Mark the exit of the region as visited, so that the children of the
590 // exit and the exit itself, i.e. the block outside the region will never
592 super::Visited
.insert(Exit
);
595 // Construct the end iterator.
596 block_iterator_wrapper() : super(df_end
<value_type
>((BlockT
*)nullptr)) {}
598 /*implicit*/ block_iterator_wrapper(super I
) : super(I
) {}
600 // FIXME: Even a const_iterator returns a non-const BasicBlock pointer.
601 // This was introduced for backwards compatibility, but should
602 // be removed as soon as all users are fixed.
603 BlockT
*operator*() const {
604 return const_cast<BlockT
*>(super::operator*());
608 using block_iterator
= block_iterator_wrapper
<false>;
609 using const_block_iterator
= block_iterator_wrapper
<true>;
611 block_iterator
block_begin() { return block_iterator(getEntry(), getExit()); }
613 block_iterator
block_end() { return block_iterator(); }
615 const_block_iterator
block_begin() const {
616 return const_block_iterator(getEntry(), getExit());
618 const_block_iterator
block_end() const { return const_block_iterator(); }
620 using block_range
= iterator_range
<block_iterator
>;
621 using const_block_range
= iterator_range
<const_block_iterator
>;
623 /// Returns a range view of the basic blocks in the region.
624 inline block_range
blocks() {
625 return block_range(block_begin(), block_end());
628 /// Returns a range view of the basic blocks in the region.
630 /// This is the 'const' version of the range view.
631 inline const_block_range
blocks() const {
632 return const_block_range(block_begin(), block_end());
636 /// @name Element Iterators
638 /// These iterators iterate over all BasicBlock and subregion RegionNodes that
639 /// are direct children of this Region. It does not iterate over any
640 /// RegionNodes that are also element of a subregion of this Region.
642 using element_iterator
=
643 df_iterator
<RegionNodeT
*, df_iterator_default_set
<RegionNodeT
*>, false,
644 GraphTraits
<RegionNodeT
*>>;
646 using const_element_iterator
=
647 df_iterator
<const RegionNodeT
*,
648 df_iterator_default_set
<const RegionNodeT
*>, false,
649 GraphTraits
<const RegionNodeT
*>>;
651 element_iterator
element_begin();
652 element_iterator
element_end();
653 iterator_range
<element_iterator
> elements() {
654 return make_range(element_begin(), element_end());
657 const_element_iterator
element_begin() const;
658 const_element_iterator
element_end() const;
659 iterator_range
<const_element_iterator
> elements() const {
660 return make_range(element_begin(), element_end());
665 /// Print a RegionNode.
667 inline raw_ostream
&operator<<(raw_ostream
&OS
, const RegionNodeBase
<Tr
> &Node
);
669 //===----------------------------------------------------------------------===//
670 /// Analysis that detects all canonical Regions.
672 /// The RegionInfo pass detects all canonical regions in a function. The Regions
673 /// are connected using the parent relation. This builds a Program Structure
676 class RegionInfoBase
{
677 friend class RegionInfo
;
678 friend class MachineRegionInfo
;
680 using BlockT
= typename
Tr::BlockT
;
681 using FuncT
= typename
Tr::FuncT
;
682 using RegionT
= typename
Tr::RegionT
;
683 using RegionInfoT
= typename
Tr::RegionInfoT
;
684 using DomTreeT
= typename
Tr::DomTreeT
;
685 using DomTreeNodeT
= typename
Tr::DomTreeNodeT
;
686 using PostDomTreeT
= typename
Tr::PostDomTreeT
;
687 using DomFrontierT
= typename
Tr::DomFrontierT
;
688 using BlockTraits
= GraphTraits
<BlockT
*>;
689 using InvBlockTraits
= GraphTraits
<Inverse
<BlockT
*>>;
690 using SuccIterTy
= typename
BlockTraits::ChildIteratorType
;
691 using PredIterTy
= typename
InvBlockTraits::ChildIteratorType
;
693 using BBtoBBMap
= DenseMap
<BlockT
*, BlockT
*>;
694 using BBtoRegionMap
= DenseMap
<BlockT
*, RegionT
*>;
698 RegionInfoBase(RegionInfoBase
&&Arg
)
699 : DT(std::move(Arg
.DT
)), PDT(std::move(Arg
.PDT
)), DF(std::move(Arg
.DF
)),
700 TopLevelRegion(std::move(Arg
.TopLevelRegion
)),
701 BBtoRegion(std::move(Arg
.BBtoRegion
)) {
705 RegionInfoBase
&operator=(RegionInfoBase
&&RHS
) {
706 DT
= std::move(RHS
.DT
);
707 PDT
= std::move(RHS
.PDT
);
708 DF
= std::move(RHS
.DF
);
709 TopLevelRegion
= std::move(RHS
.TopLevelRegion
);
710 BBtoRegion
= std::move(RHS
.BBtoRegion
);
715 virtual ~RegionInfoBase();
721 /// The top level region.
722 RegionT
*TopLevelRegion
= nullptr;
724 /// Map every BB to the smallest region, that contains BB.
725 BBtoRegionMap BBtoRegion
;
728 /// Update refences to a RegionInfoT held by the RegionT managed here
730 /// This is a post-move helper. Regions hold references to the owning
731 /// RegionInfo object. After a move these need to be fixed.
732 template<typename TheRegionT
>
733 void updateRegionTree(RegionInfoT
&RI
, TheRegionT
*R
) {
737 for (auto &SubR
: *R
)
738 updateRegionTree(RI
, SubR
.get());
742 /// Wipe this region tree's state without releasing any resources.
744 /// This is essentially a post-move helper only. It leaves the object in an
745 /// assignable and destroyable state, but otherwise invalid.
750 TopLevelRegion
= nullptr;
754 // Check whether the entries of BBtoRegion for the BBs of region
755 // SR are correct. Triggers an assertion if not. Calls itself recursively for
757 void verifyBBMap(const RegionT
*SR
) const;
759 // Returns true if BB is in the dominance frontier of
760 // entry, because it was inherited from exit. In the other case there is an
761 // edge going from entry to BB without passing exit.
762 bool isCommonDomFrontier(BlockT
*BB
, BlockT
*entry
, BlockT
*exit
) const;
764 // Check if entry and exit surround a valid region, based on
765 // dominance tree and dominance frontier.
766 bool isRegion(BlockT
*entry
, BlockT
*exit
) const;
768 // Saves a shortcut pointing from entry to exit.
769 // This function may extend this shortcut if possible.
770 void insertShortCut(BlockT
*entry
, BlockT
*exit
, BBtoBBMap
*ShortCut
) const;
772 // Returns the next BB that postdominates N, while skipping
773 // all post dominators that cannot finish a canonical region.
774 DomTreeNodeT
*getNextPostDom(DomTreeNodeT
*N
, BBtoBBMap
*ShortCut
) const;
776 // A region is trivial, if it contains only one BB.
777 bool isTrivialRegion(BlockT
*entry
, BlockT
*exit
) const;
779 // Creates a single entry single exit region.
780 RegionT
*createRegion(BlockT
*entry
, BlockT
*exit
);
782 // Detect all regions starting with bb 'entry'.
783 void findRegionsWithEntry(BlockT
*entry
, BBtoBBMap
*ShortCut
);
785 // Detects regions in F.
786 void scanForRegions(FuncT
&F
, BBtoBBMap
*ShortCut
);
788 // Get the top most parent with the same entry block.
789 RegionT
*getTopMostParent(RegionT
*region
);
791 // Build the region hierarchy after all region detected.
792 void buildRegionsTree(DomTreeNodeT
*N
, RegionT
*region
);
794 // Update statistic about created regions.
795 virtual void updateStatistics(RegionT
*R
) = 0;
797 // Detect all regions in function and build the region tree.
798 void calculate(FuncT
&F
);
801 RegionInfoBase(const RegionInfoBase
&) = delete;
802 RegionInfoBase
&operator=(const RegionInfoBase
&) = delete;
804 static bool VerifyRegionInfo
;
805 static typename
RegionT::PrintStyle printStyle
;
807 void print(raw_ostream
&OS
) const;
808 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
812 void releaseMemory();
814 /// Get the smallest region that contains a BasicBlock.
816 /// @param BB The basic block.
817 /// @return The smallest region, that contains BB or NULL, if there is no
818 /// region containing BB.
819 RegionT
*getRegionFor(BlockT
*BB
) const;
821 /// Set the smallest region that surrounds a basic block.
823 /// @param BB The basic block surrounded by a region.
824 /// @param R The smallest region that surrounds BB.
825 void setRegionFor(BlockT
*BB
, RegionT
*R
);
827 /// A shortcut for getRegionFor().
829 /// @param BB The basic block.
830 /// @return The smallest region, that contains BB or NULL, if there is no
831 /// region containing BB.
832 RegionT
*operator[](BlockT
*BB
) const;
834 /// Return the exit of the maximal refined region, that starts at a
837 /// @param BB The BasicBlock the refined region starts.
838 BlockT
*getMaxRegionExit(BlockT
*BB
) const;
840 /// Find the smallest region that contains two regions.
842 /// @param A The first region.
843 /// @param B The second region.
844 /// @return The smallest region containing A and B.
845 RegionT
*getCommonRegion(RegionT
*A
, RegionT
*B
) const;
847 /// Find the smallest region that contains two basic blocks.
849 /// @param A The first basic block.
850 /// @param B The second basic block.
851 /// @return The smallest region that contains A and B.
852 RegionT
*getCommonRegion(BlockT
*A
, BlockT
*B
) const {
853 return getCommonRegion(getRegionFor(A
), getRegionFor(B
));
856 /// Find the smallest region that contains a set of regions.
858 /// @param Regions A vector of regions.
859 /// @return The smallest region that contains all regions in Regions.
860 RegionT
*getCommonRegion(SmallVectorImpl
<RegionT
*> &Regions
) const;
862 /// Find the smallest region that contains a set of basic blocks.
864 /// @param BBs A vector of basic blocks.
865 /// @return The smallest region that contains all basic blocks in BBS.
866 RegionT
*getCommonRegion(SmallVectorImpl
<BlockT
*> &BBs
) const;
868 RegionT
*getTopLevelRegion() const { return TopLevelRegion
; }
870 /// Clear the Node Cache for all Regions.
872 /// @see Region::clearNodeCache()
873 void clearNodeCache() {
875 TopLevelRegion
->clearNodeCache();
878 void verifyAnalysis() const;
883 class RegionNode
: public RegionNodeBase
<RegionTraits
<Function
>> {
885 inline RegionNode(Region
*Parent
, BasicBlock
*Entry
, bool isSubRegion
= false)
886 : RegionNodeBase
<RegionTraits
<Function
>>(Parent
, Entry
, isSubRegion
) {}
888 bool operator==(const Region
&RN
) const {
889 return this == reinterpret_cast<const RegionNode
*>(&RN
);
893 class Region
: public RegionBase
<RegionTraits
<Function
>> {
895 Region(BasicBlock
*Entry
, BasicBlock
*Exit
, RegionInfo
*RI
, DominatorTree
*DT
,
896 Region
*Parent
= nullptr);
899 bool operator==(const RegionNode
&RN
) const {
900 return &RN
== reinterpret_cast<const RegionNode
*>(this);
904 class RegionInfo
: public RegionInfoBase
<RegionTraits
<Function
>> {
906 using Base
= RegionInfoBase
<RegionTraits
<Function
>>;
908 explicit RegionInfo();
910 RegionInfo(RegionInfo
&&Arg
) : Base(std::move(static_cast<Base
&>(Arg
))) {
911 updateRegionTree(*this, TopLevelRegion
);
914 RegionInfo
&operator=(RegionInfo
&&RHS
) {
915 Base::operator=(std::move(static_cast<Base
&>(RHS
)));
916 updateRegionTree(*this, TopLevelRegion
);
920 ~RegionInfo() override
;
922 /// Handle invalidation explicitly.
923 bool invalidate(Function
&F
, const PreservedAnalyses
&PA
,
924 FunctionAnalysisManager::Invalidator
&);
926 // updateStatistics - Update statistic about created regions.
927 void updateStatistics(Region
*R
) final
;
929 void recalculate(Function
&F
, DominatorTree
*DT
, PostDominatorTree
*PDT
,
930 DominanceFrontier
*DF
);
933 /// Opens a viewer to show the GraphViz visualization of the regions.
935 /// Useful during debugging as an alternative to dump().
938 /// Opens a viewer to show the GraphViz visualization of this region
939 /// without instructions in the BasicBlocks.
941 /// Useful during debugging as an alternative to dump().
946 class RegionInfoPass
: public FunctionPass
{
952 explicit RegionInfoPass();
953 ~RegionInfoPass() override
;
955 RegionInfo
&getRegionInfo() { return RI
; }
957 const RegionInfo
&getRegionInfo() const { return RI
; }
959 /// @name FunctionPass interface
961 bool runOnFunction(Function
&F
) override
;
962 void releaseMemory() override
;
963 void verifyAnalysis() const override
;
964 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
965 void print(raw_ostream
&OS
, const Module
*) const override
;
970 /// Analysis pass that exposes the \c RegionInfo for a function.
971 class RegionInfoAnalysis
: public AnalysisInfoMixin
<RegionInfoAnalysis
> {
972 friend AnalysisInfoMixin
<RegionInfoAnalysis
>;
974 static AnalysisKey Key
;
977 using Result
= RegionInfo
;
979 RegionInfo
run(Function
&F
, FunctionAnalysisManager
&AM
);
982 /// Printer pass for the \c RegionInfo.
983 class RegionInfoPrinterPass
: public PassInfoMixin
<RegionInfoPrinterPass
> {
987 explicit RegionInfoPrinterPass(raw_ostream
&OS
);
989 PreservedAnalyses
run(Function
&F
, FunctionAnalysisManager
&AM
);
992 /// Verifier pass for the \c RegionInfo.
993 struct RegionInfoVerifierPass
: PassInfoMixin
<RegionInfoVerifierPass
> {
994 PreservedAnalyses
run(Function
&F
, FunctionAnalysisManager
&AM
);
1000 RegionNodeBase
<RegionTraits
<Function
>>::getNodeAs
<BasicBlock
>() const {
1001 assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
1008 RegionNodeBase
<RegionTraits
<Function
>>::getNodeAs
<Region
>() const {
1009 assert(isSubRegion() && "This is not a subregion RegionNode!");
1010 auto Unconst
= const_cast<RegionNodeBase
<RegionTraits
<Function
>> *>(this);
1011 return reinterpret_cast<Region
*>(Unconst
);
1015 inline raw_ostream
&operator<<(raw_ostream
&OS
,
1016 const RegionNodeBase
<Tr
> &Node
) {
1017 using BlockT
= typename
Tr::BlockT
;
1018 using RegionT
= typename
Tr::RegionT
;
1020 if (Node
.isSubRegion())
1021 return OS
<< Node
.template getNodeAs
<RegionT
>()->getNameStr();
1023 return OS
<< Node
.template getNodeAs
<BlockT
>()->getName();
1026 extern template class RegionBase
<RegionTraits
<Function
>>;
1027 extern template class RegionNodeBase
<RegionTraits
<Function
>>;
1028 extern template class RegionInfoBase
<RegionTraits
<Function
>>;
1030 } // end namespace llvm
1032 #endif // LLVM_ANALYSIS_REGIONINFO_H