1 //===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Calculate a program structure tree built out of single entry single exit
10 // regions.
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
14 // Koehler - 2009".
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.
23 //
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.
33 //
34 //===----------------------------------------------------------------------===//
35 
36 #ifndef LLVM_ANALYSIS_REGIONINFO_H
37 #define LLVM_ANALYSIS_REGIONINFO_H
38 
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"
50 #include <algorithm>
51 #include <cassert>
52 #include <map>
53 #include <memory>
54 #include <set>
55 #include <string>
56 #include <type_traits>
57 #include <vector>
58 
59 namespace llvm {
60 
61 class DominanceFrontier;
62 class Loop;
63 class LoopInfo;
64 class PostDominatorTree;
65 class Region;
66 template <class RegionTr> class RegionBase;
67 class RegionInfo;
68 template <class RegionTr> class RegionInfoBase;
69 class RegionNode;
70 
71 // Class to be specialized for different users of RegionInfo
72 // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to
73 // pass around an unreasonable number of template parameters.
74 template <class FuncT_>
75 struct RegionTraits {
76   // FuncT
77   // BlockT
78   // RegionT
79   // RegionNodeT
80   // RegionInfoT
81   using BrokenT = typename FuncT_::UnknownRegionTypeError;
82 };
83 
84 template <>
85 struct RegionTraits<Function> {
86   using FuncT = Function;
87   using BlockT = BasicBlock;
88   using RegionT = Region;
89   using RegionNodeT = RegionNode;
90   using RegionInfoT = RegionInfo;
91   using DomTreeT = DominatorTree;
92   using DomTreeNodeT = DomTreeNode;
93   using DomFrontierT = DominanceFrontier;
94   using PostDomTreeT = PostDominatorTree;
95   using InstT = Instruction;
96   using LoopT = Loop;
97   using LoopInfoT = LoopInfo;
98 
99   static unsigned getNumSuccessors(BasicBlock *BB) {
100     return BB->getTerminator()->getNumSuccessors();
101   }
102 };
103 
104 /// Marker class to iterate over the elements of a Region in flat mode.
105 ///
106 /// The class is used to either iterate in Flat mode or by not using it to not
107 /// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
108 /// and the iteration returns every BasicBlock.  If the Flat mode is not
109 /// selected for SubRegions just one RegionNode containing the subregion is
110 /// returned.
111 template <class GraphType>
112 class FlatIt {};
113 
114 /// A RegionNode represents a subregion or a BasicBlock that is part of a
115 /// Region.
116 template <class Tr>
117 class RegionNodeBase {
118   friend class RegionBase<Tr>;
119 
120 public:
121   using BlockT = typename Tr::BlockT;
122   using RegionT = typename Tr::RegionT;
123 
124 private:
125   /// This is the entry basic block that starts this region node.  If this is a
126   /// BasicBlock RegionNode, then entry is just the basic block, that this
127   /// RegionNode represents.  Otherwise it is the entry of this (Sub)RegionNode.
128   ///
129   /// In the BBtoRegionNode map of the parent of this node, BB will always map
130   /// to this node no matter which kind of node this one is.
131   ///
132   /// The node can hold either a Region or a BasicBlock.
133   /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
134   /// RegionNode.
135   PointerIntPair<BlockT *, 1, bool> entry;
136 
137   /// The parent Region of this RegionNode.
138   /// @see getParent()
139   RegionT *parent;
140 
141 protected:
142   /// Create a RegionNode.
143   ///
144   /// @param Parent      The parent of this RegionNode.
145   /// @param Entry       The entry BasicBlock of the RegionNode.  If this
146   ///                    RegionNode represents a BasicBlock, this is the
147   ///                    BasicBlock itself.  If it represents a subregion, this
148   ///                    is the entry BasicBlock of the subregion.
149   /// @param isSubRegion If this RegionNode represents a SubRegion.
150   inline RegionNodeBase(RegionT *Parent, BlockT *Entry,
151                         bool isSubRegion = false)
152       : entry(Entry, isSubRegion), parent(Parent) {}
153 
154 public:
155   RegionNodeBase(const RegionNodeBase &) = delete;
156   RegionNodeBase &operator=(const RegionNodeBase &) = delete;
157 
158   /// Get the parent Region of this RegionNode.
159   ///
160   /// The parent Region is the Region this RegionNode belongs to. If for
161   /// example a BasicBlock is element of two Regions, there exist two
162   /// RegionNodes for this BasicBlock. Each with the getParent() function
163   /// pointing to the Region this RegionNode belongs to.
164   ///
165   /// @return Get the parent Region of this RegionNode.
166   inline RegionT *getParent() const { return parent; }
167 
168   /// Get the entry BasicBlock of this RegionNode.
169   ///
170   /// If this RegionNode represents a BasicBlock this is just the BasicBlock
171   /// itself, otherwise we return the entry BasicBlock of the Subregion
172   ///
173   /// @return The entry BasicBlock of this RegionNode.
174   inline BlockT *getEntry() const { return entry.getPointer(); }
175 
176   /// Get the content of this RegionNode.
177   ///
178   /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
179   /// check the type of the content with the isSubRegion() function call.
180   ///
181   /// @return The content of this RegionNode.
182   template <class T> inline T *getNodeAs() const;
183 
184   /// Is this RegionNode a subregion?
185   ///
186   /// @return True if it contains a subregion. False if it contains a
187   ///         BasicBlock.
188   inline bool isSubRegion() const { return entry.getInt(); }
189 };
190 
191 //===----------------------------------------------------------------------===//
192 /// A single entry single exit Region.
193 ///
194 /// A Region is a connected subgraph of a control flow graph that has exactly
195 /// two connections to the remaining graph. It can be used to analyze or
196 /// optimize parts of the control flow graph.
197 ///
198 /// A <em> simple Region </em> is connected to the remaining graph by just two
199 /// edges. One edge entering the Region and another one leaving the Region.
200 ///
201 /// An <em> extended Region </em> (or just Region) is a subgraph that can be
202 /// transform into a simple Region. The transformation is done by adding
203 /// BasicBlocks that merge several entry or exit edges so that after the merge
204 /// just one entry and one exit edge exists.
205 ///
206 /// The \e Entry of a Region is the first BasicBlock that is passed after
207 /// entering the Region. It is an element of the Region. The entry BasicBlock
208 /// dominates all BasicBlocks in the Region.
209 ///
210 /// The \e Exit of a Region is the first BasicBlock that is passed after
211 /// leaving the Region. It is not an element of the Region. The exit BasicBlock,
212 /// postdominates all BasicBlocks in the Region.
213 ///
214 /// A <em> canonical Region </em> cannot be constructed by combining smaller
215 /// Regions.
216 ///
217 /// Region A is the \e parent of Region B, if B is completely contained in A.
218 ///
219 /// Two canonical Regions either do not intersect at all or one is
220 /// the parent of the other.
221 ///
222 /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
223 /// Regions in the control flow graph and E is the \e parent relation of these
224 /// Regions.
225 ///
226 /// Example:
227 ///
228 /// \verbatim
229 /// A simple control flow graph, that contains two regions.
230 ///
231 ///        1
232 ///       / |
233 ///      2   |
234 ///     / \   3
235 ///    4   5  |
236 ///    |   |  |
237 ///    6   7  8
238 ///     \  | /
239 ///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
240 ///        9        Region B: 2 -> 9 {2,4,5,6,7}
241 /// \endverbatim
242 ///
243 /// You can obtain more examples by either calling
244 ///
245 /// <tt> "opt -regions -analyze anyprogram.ll" </tt>
246 /// or
247 /// <tt> "opt -view-regions-only anyprogram.ll" </tt>
248 ///
249 /// on any LLVM file you are interested in.
250 ///
251 /// The first call returns a textual representation of the program structure
252 /// tree, the second one creates a graphical representation using graphviz.
253 template <class Tr>
254 class RegionBase : public RegionNodeBase<Tr> {
255   friend class RegionInfoBase<Tr>;
256 
257   using FuncT = typename Tr::FuncT;
258   using BlockT = typename Tr::BlockT;
259   using RegionInfoT = typename Tr::RegionInfoT;
260   using RegionT = typename Tr::RegionT;
261   using RegionNodeT = typename Tr::RegionNodeT;
262   using DomTreeT = typename Tr::DomTreeT;
263   using LoopT = typename Tr::LoopT;
264   using LoopInfoT = typename Tr::LoopInfoT;
265   using InstT = typename Tr::InstT;
266 
267   using BlockTraits = GraphTraits<BlockT *>;
268   using InvBlockTraits = GraphTraits<Inverse<BlockT *>>;
269   using SuccIterTy = typename BlockTraits::ChildIteratorType;
270   using PredIterTy = typename InvBlockTraits::ChildIteratorType;
271 
272   // Information necessary to manage this Region.
273   RegionInfoT *RI;
274   DomTreeT *DT;
275 
276   // The exit BasicBlock of this region.
277   // (The entry BasicBlock is part of RegionNode)
278   BlockT *exit;
279 
280   using RegionSet = std::vector<std::unique_ptr<RegionT>>;
281 
282   // The subregions of this region.
283   RegionSet children;
284 
285   using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>;
286 
287   // Save the BasicBlock RegionNodes that are element of this Region.
288   mutable BBNodeMapT BBNodeMap;
289 
290   /// Check if a BB is in this Region. This check also works
291   /// if the region is incorrectly built. (EXPENSIVE!)
292   void verifyBBInRegion(BlockT *BB) const;
293 
294   /// Walk over all the BBs of the region starting from BB and
295   /// verify that all reachable basic blocks are elements of the region.
296   /// (EXPENSIVE!)
297   void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const;
298 
299   /// Verify if the region and its children are valid regions (EXPENSIVE!)
300   void verifyRegionNest() const;
301 
302 public:
303   /// Create a new region.
304   ///
305   /// @param Entry  The entry basic block of the region.
306   /// @param Exit   The exit basic block of the region.
307   /// @param RI     The region info object that is managing this region.
308   /// @param DT     The dominator tree of the current function.
309   /// @param Parent The surrounding region or NULL if this is a top level
310   ///               region.
311   RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT,
312              RegionT *Parent = nullptr);
313 
314   RegionBase(const RegionBase &) = delete;
315   RegionBase &operator=(const RegionBase &) = delete;
316 
317   /// Delete the Region and all its subregions.
318   ~RegionBase();
319 
320   /// Get the entry BasicBlock of the Region.
321   /// @return The entry BasicBlock of the region.
322   BlockT *getEntry() const {
323     return RegionNodeBase<Tr>::getEntry();
324   }
325 
326   /// Replace the entry basic block of the region with the new basic
327   ///        block.
328   ///
329   /// @param BB  The new entry basic block of the region.
330   void replaceEntry(BlockT *BB);
331 
332   /// Replace the exit basic block of the region with the new basic
333   ///        block.
334   ///
335   /// @param BB  The new exit basic block of the region.
336   void replaceExit(BlockT *BB);
337 
338   /// Recursively replace the entry basic block of the region.
339   ///
340   /// This function replaces the entry basic block with a new basic block. It
341   /// also updates all child regions that have the same entry basic block as
342   /// this region.
343   ///
344   /// @param NewEntry The new entry basic block.
345   void replaceEntryRecursive(BlockT *NewEntry);
346 
347   /// Recursively replace the exit basic block of the region.
348   ///
349   /// This function replaces the exit basic block with a new basic block. It
350   /// also updates all child regions that have the same exit basic block as
351   /// this region.
352   ///
353   /// @param NewExit The new exit basic block.
354   void replaceExitRecursive(BlockT *NewExit);
355 
356   /// Get the exit BasicBlock of the Region.
357   /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
358   ///         Region.
359   BlockT *getExit() const { return exit; }
360 
361   /// Get the parent of the Region.
362   /// @return The parent of the Region or NULL if this is a top level
363   ///         Region.
364   RegionT *getParent() const {
365     return RegionNodeBase<Tr>::getParent();
366   }
367 
368   /// Get the RegionNode representing the current Region.
369   /// @return The RegionNode representing the current Region.
370   RegionNodeT *getNode() const {
371     return const_cast<RegionNodeT *>(
372         reinterpret_cast<const RegionNodeT *>(this));
373   }
374 
375   /// Get the nesting level of this Region.
376   ///
377   /// An toplevel Region has depth 0.
378   ///
379   /// @return The depth of the region.
380   unsigned getDepth() const;
381 
382   /// Check if a Region is the TopLevel region.
383   ///
384   /// The toplevel region represents the whole function.
385   bool isTopLevelRegion() const { return exit == nullptr; }
386 
387   /// Return a new (non-canonical) region, that is obtained by joining
388   ///        this region with its predecessors.
389   ///
390   /// @return A region also starting at getEntry(), but reaching to the next
391   ///         basic block that forms with getEntry() a (non-canonical) region.
392   ///         NULL if such a basic block does not exist.
393   RegionT *getExpandedRegion() const;
394 
395   /// Return the first block of this region's single entry edge,
396   ///        if existing.
397   ///
398   /// @return The BasicBlock starting this region's single entry edge,
399   ///         else NULL.
400   BlockT *getEnteringBlock() const;
401 
402   /// Return the first block of this region's single exit edge,
403   ///        if existing.
404   ///
405   /// @return The BasicBlock starting this region's single exit edge,
406   ///         else NULL.
407   BlockT *getExitingBlock() const;
408 
409   /// Collect all blocks of this region's single exit edge, if existing.
410   ///
411   /// @return True if this region contains all the predecessors of the exit.
412   bool getExitingBlocks(SmallVectorImpl<BlockT *> &Exitings) const;
413 
414   /// Is this a simple region?
415   ///
416   /// A region is simple if it has exactly one exit and one entry edge.
417   ///
418   /// @return True if the Region is simple.
419   bool isSimple() const;
420 
421   /// Returns the name of the Region.
422   /// @return The Name of the Region.
423   std::string getNameStr() const;
424 
425   /// Return the RegionInfo object, that belongs to this Region.
426   RegionInfoT *getRegionInfo() const { return RI; }
427 
428   /// PrintStyle - Print region in difference ways.
429   enum PrintStyle { PrintNone, PrintBB, PrintRN };
430 
431   /// Print the region.
432   ///
433   /// @param OS The output stream the Region is printed to.
434   /// @param printTree Print also the tree of subregions.
435   /// @param level The indentation level used for printing.
436   void print(raw_ostream &OS, bool printTree = true, unsigned level = 0,
437              PrintStyle Style = PrintNone) const;
438 
439 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
440   /// Print the region to stderr.
441   void dump() const;
442 #endif
443 
444   /// Check if the region contains a BasicBlock.
445   ///
446   /// @param BB The BasicBlock that might be contained in this Region.
447   /// @return True if the block is contained in the region otherwise false.
448   bool contains(const BlockT *BB) const;
449 
450   /// Check if the region contains another region.
451   ///
452   /// @param SubRegion The region that might be contained in this Region.
453   /// @return True if SubRegion is contained in the region otherwise false.
454   bool contains(const RegionT *SubRegion) const {
455     // Toplevel Region.
456     if (!getExit())
457       return true;
458 
459     return contains(SubRegion->getEntry()) &&
460            (contains(SubRegion->getExit()) ||
461             SubRegion->getExit() == getExit());
462   }
463 
464   /// Check if the region contains an Instruction.
465   ///
466   /// @param Inst The Instruction that might be contained in this region.
467   /// @return True if the Instruction is contained in the region otherwise
468   /// false.
469   bool contains(const InstT *Inst) const { return contains(Inst->getParent()); }
470 
471   /// Check if the region contains a loop.
472   ///
473   /// @param L The loop that might be contained in this region.
474   /// @return True if the loop is contained in the region otherwise false.
475   ///         In case a NULL pointer is passed to this function the result
476   ///         is false, except for the region that describes the whole function.
477   ///         In that case true is returned.
478   bool contains(const LoopT *L) const;
479 
480   /// Get the outermost loop in the region that contains a loop.
481   ///
482   /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
483   /// and is itself contained in the region.
484   ///
485   /// @param L The loop the lookup is started.
486   /// @return The outermost loop in the region, NULL if such a loop does not
487   ///         exist or if the region describes the whole function.
488   LoopT *outermostLoopInRegion(LoopT *L) const;
489 
490   /// Get the outermost loop in the region that contains a basic block.
491   ///
492   /// Find for a basic block BB the outermost loop L that contains BB and is
493   /// itself contained in the region.
494   ///
495   /// @param LI A pointer to a LoopInfo analysis.
496   /// @param BB The basic block surrounded by the loop.
497   /// @return The outermost loop in the region, NULL if such a loop does not
498   ///         exist or if the region describes the whole function.
499   LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const;
500 
501   /// Get the subregion that starts at a BasicBlock
502   ///
503   /// @param BB The BasicBlock the subregion should start.
504   /// @return The Subregion if available, otherwise NULL.
505   RegionT *getSubRegionNode(BlockT *BB) const;
506 
507   /// Get the RegionNode for a BasicBlock
508   ///
509   /// @param BB The BasicBlock at which the RegionNode should start.
510   /// @return If available, the RegionNode that represents the subregion
511   ///         starting at BB. If no subregion starts at BB, the RegionNode
512   ///         representing BB.
513   RegionNodeT *getNode(BlockT *BB) const;
514 
515   /// Get the BasicBlock RegionNode for a BasicBlock
516   ///
517   /// @param BB The BasicBlock for which the RegionNode is requested.
518   /// @return The RegionNode representing the BB.
519   RegionNodeT *getBBNode(BlockT *BB) const;
520 
521   /// Add a new subregion to this Region.
522   ///
523   /// @param SubRegion The new subregion that will be added.
524   /// @param moveChildren Move the children of this region, that are also
525   ///                     contained in SubRegion into SubRegion.
526   void addSubRegion(RegionT *SubRegion, bool moveChildren = false);
527 
528   /// Remove a subregion from this Region.
529   ///
530   /// The subregion is not deleted, as it will probably be inserted into another
531   /// region.
532   /// @param SubRegion The SubRegion that will be removed.
533   RegionT *removeSubRegion(RegionT *SubRegion);
534 
535   /// Move all direct child nodes of this Region to another Region.
536   ///
537   /// @param To The Region the child nodes will be transferred to.
538   void transferChildrenTo(RegionT *To);
539 
540   /// Verify if the region is a correct region.
541   ///
542   /// Check if this is a correctly build Region. This is an expensive check, as
543   /// the complete CFG of the Region will be walked.
544   void verifyRegion() const;
545 
546   /// Clear the cache for BB RegionNodes.
547   ///
548   /// After calling this function the BasicBlock RegionNodes will be stored at
549   /// different memory locations. RegionNodes obtained before this function is
550   /// called are therefore not comparable to RegionNodes abtained afterwords.
551   void clearNodeCache();
552 
553   /// @name Subregion Iterators
554   ///
555   /// These iterators iterator over all subregions of this Region.
556   //@{
557   using iterator = typename RegionSet::iterator;
558   using const_iterator = typename RegionSet::const_iterator;
559 
560   iterator begin() { return children.begin(); }
561   iterator end() { return children.end(); }
562 
563   const_iterator begin() const { return children.begin(); }
564   const_iterator end() const { return children.end(); }
565   //@}
566 
567   /// @name BasicBlock Iterators
568   ///
569   /// These iterators iterate over all BasicBlocks that are contained in this
570   /// Region. The iterator also iterates over BasicBlocks that are elements of
571   /// a subregion of this Region. It is therefore called a flat iterator.
572   //@{
573   template <bool IsConst>
574   class block_iterator_wrapper
575       : public df_iterator<
576             std::conditional_t<IsConst, const BlockT, BlockT> *> {
577     using super =
578         df_iterator<std::conditional_t<IsConst, const BlockT, BlockT> *>;
579 
580   public:
581     using Self = block_iterator_wrapper<IsConst>;
582     using value_type = typename super::value_type;
583 
584     // Construct the begin iterator.
585     block_iterator_wrapper(value_type Entry, value_type Exit)
586         : super(df_begin(Entry)) {
587       // Mark the exit of the region as visited, so that the children of the
588       // exit and the exit itself, i.e. the block outside the region will never
589       // be visited.
590       super::Visited.insert(Exit);
591     }
592 
593     // Construct the end iterator.
594     block_iterator_wrapper() : super(df_end<value_type>((BlockT *)nullptr)) {}
595 
596     /*implicit*/ block_iterator_wrapper(super I) : super(I) {}
597 
598     // FIXME: Even a const_iterator returns a non-const BasicBlock pointer.
599     //        This was introduced for backwards compatibility, but should
600     //        be removed as soon as all users are fixed.
601     BlockT *operator*() const {
602       return const_cast<BlockT *>(super::operator*());
603     }
604   };
605 
606   using block_iterator = block_iterator_wrapper<false>;
607   using const_block_iterator = block_iterator_wrapper<true>;
608 
609   block_iterator block_begin() { return block_iterator(getEntry(), getExit()); }
610 
611   block_iterator block_end() { return block_iterator(); }
612 
613   const_block_iterator block_begin() const {
614     return const_block_iterator(getEntry(), getExit());
615   }
616   const_block_iterator block_end() const { return const_block_iterator(); }
617 
618   using block_range = iterator_range<block_iterator>;
619   using const_block_range = iterator_range<const_block_iterator>;
620 
621   /// Returns a range view of the basic blocks in the region.
622   inline block_range blocks() {
623     return block_range(block_begin(), block_end());
624   }
625 
626   /// Returns a range view of the basic blocks in the region.
627   ///
628   /// This is the 'const' version of the range view.
629   inline const_block_range blocks() const {
630     return const_block_range(block_begin(), block_end());
631   }
632   //@}
633 
634   /// @name Element Iterators
635   ///
636   /// These iterators iterate over all BasicBlock and subregion RegionNodes that
637   /// are direct children of this Region. It does not iterate over any
638   /// RegionNodes that are also element of a subregion of this Region.
639   //@{
640   using element_iterator =
641       df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false,
642                   GraphTraits<RegionNodeT *>>;
643 
644   using const_element_iterator =
645       df_iterator<const RegionNodeT *,
646                   df_iterator_default_set<const RegionNodeT *>, false,
647                   GraphTraits<const RegionNodeT *>>;
648 
649   element_iterator element_begin();
650   element_iterator element_end();
651   iterator_range<element_iterator> elements() {
652     return make_range(element_begin(), element_end());
653   }
654 
655   const_element_iterator element_begin() const;
656   const_element_iterator element_end() const;
657   iterator_range<const_element_iterator> elements() const {
658     return make_range(element_begin(), element_end());
659   }
660   //@}
661 };
662 
663 /// Print a RegionNode.
664 template <class Tr>
665 inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node);
666 
667 //===----------------------------------------------------------------------===//
668 /// Analysis that detects all canonical Regions.
669 ///
670 /// The RegionInfo pass detects all canonical regions in a function. The Regions
671 /// are connected using the parent relation. This builds a Program Structure
672 /// Tree.
673 template <class Tr>
674 class RegionInfoBase {
675   friend class RegionInfo;
676   friend class MachineRegionInfo;
677 
678   using BlockT = typename Tr::BlockT;
679   using FuncT = typename Tr::FuncT;
680   using RegionT = typename Tr::RegionT;
681   using RegionInfoT = typename Tr::RegionInfoT;
682   using DomTreeT = typename Tr::DomTreeT;
683   using DomTreeNodeT = typename Tr::DomTreeNodeT;
684   using PostDomTreeT = typename Tr::PostDomTreeT;
685   using DomFrontierT = typename Tr::DomFrontierT;
686   using BlockTraits = GraphTraits<BlockT *>;
687   using InvBlockTraits = GraphTraits<Inverse<BlockT *>>;
688   using SuccIterTy = typename BlockTraits::ChildIteratorType;
689   using PredIterTy = typename InvBlockTraits::ChildIteratorType;
690 
691   using BBtoBBMap = DenseMap<BlockT *, BlockT *>;
692   using BBtoRegionMap = DenseMap<BlockT *, RegionT *>;
693 
694   RegionInfoBase();
695 
696   RegionInfoBase(RegionInfoBase &&Arg)
697     : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)),
698       TopLevelRegion(std::move(Arg.TopLevelRegion)),
699       BBtoRegion(std::move(Arg.BBtoRegion)) {
700     Arg.wipe();
701   }
702 
703   RegionInfoBase &operator=(RegionInfoBase &&RHS) {
704     DT = std::move(RHS.DT);
705     PDT = std::move(RHS.PDT);
706     DF = std::move(RHS.DF);
707     TopLevelRegion = std::move(RHS.TopLevelRegion);
708     BBtoRegion = std::move(RHS.BBtoRegion);
709     RHS.wipe();
710     return *this;
711   }
712 
713   virtual ~RegionInfoBase();
714 
715   DomTreeT *DT;
716   PostDomTreeT *PDT;
717   DomFrontierT *DF;
718 
719   /// The top level region.
720   RegionT *TopLevelRegion = nullptr;
721 
722   /// Map every BB to the smallest region, that contains BB.
723   BBtoRegionMap BBtoRegion;
724 
725 protected:
726   /// Update refences to a RegionInfoT held by the RegionT managed here
727   ///
728   /// This is a post-move helper. Regions hold references to the owning
729   /// RegionInfo object. After a move these need to be fixed.
730   template<typename TheRegionT>
731   void updateRegionTree(RegionInfoT &RI, TheRegionT *R) {
732     if (!R)
733       return;
734     R->RI = &RI;
735     for (auto &SubR : *R)
736       updateRegionTree(RI, SubR.get());
737   }
738 
739 private:
740   /// Wipe this region tree's state without releasing any resources.
741   ///
742   /// This is essentially a post-move helper only. It leaves the object in an
743   /// assignable and destroyable state, but otherwise invalid.
744   void wipe() {
745     DT = nullptr;
746     PDT = nullptr;
747     DF = nullptr;
748     TopLevelRegion = nullptr;
749     BBtoRegion.clear();
750   }
751 
752   // Check whether the entries of BBtoRegion for the BBs of region
753   // SR are correct. Triggers an assertion if not. Calls itself recursively for
754   // subregions.
755   void verifyBBMap(const RegionT *SR) const;
756 
757   // Returns true if BB is in the dominance frontier of
758   // entry, because it was inherited from exit. In the other case there is an
759   // edge going from entry to BB without passing exit.
760   bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;
761 
762   // Check if entry and exit surround a valid region, based on
763   // dominance tree and dominance frontier.
764   bool isRegion(BlockT *entry, BlockT *exit) const;
765 
766   // Saves a shortcut pointing from entry to exit.
767   // This function may extend this shortcut if possible.
768   void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const;
769 
770   // Returns the next BB that postdominates N, while skipping
771   // all post dominators that cannot finish a canonical region.
772   DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const;
773 
774   // A region is trivial, if it contains only one BB.
775   bool isTrivialRegion(BlockT *entry, BlockT *exit) const;
776 
777   // Creates a single entry single exit region.
778   RegionT *createRegion(BlockT *entry, BlockT *exit);
779 
780   // Detect all regions starting with bb 'entry'.
781   void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut);
782 
783   // Detects regions in F.
784   void scanForRegions(FuncT &F, BBtoBBMap *ShortCut);
785 
786   // Get the top most parent with the same entry block.
787   RegionT *getTopMostParent(RegionT *region);
788 
789   // Build the region hierarchy after all region detected.
790   void buildRegionsTree(DomTreeNodeT *N, RegionT *region);
791 
792   // Update statistic about created regions.
793   virtual void updateStatistics(RegionT *R) = 0;
794 
795   // Detect all regions in function and build the region tree.
796   void calculate(FuncT &F);
797 
798 public:
799   RegionInfoBase(const RegionInfoBase &) = delete;
800   RegionInfoBase &operator=(const RegionInfoBase &) = delete;
801 
802   static bool VerifyRegionInfo;
803   static typename RegionT::PrintStyle printStyle;
804 
805   void print(raw_ostream &OS) const;
806 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
807   void dump() const;
808 #endif
809 
810   void releaseMemory();
811 
812   /// Get the smallest region that contains a BasicBlock.
813   ///
814   /// @param BB The basic block.
815   /// @return The smallest region, that contains BB or NULL, if there is no
816   /// region containing BB.
817   RegionT *getRegionFor(BlockT *BB) const;
818 
819   ///  Set the smallest region that surrounds a basic block.
820   ///
821   /// @param BB The basic block surrounded by a region.
822   /// @param R The smallest region that surrounds BB.
823   void setRegionFor(BlockT *BB, RegionT *R);
824 
825   /// A shortcut for getRegionFor().
826   ///
827   /// @param BB The basic block.
828   /// @return The smallest region, that contains BB or NULL, if there is no
829   /// region containing BB.
830   RegionT *operator[](BlockT *BB) const;
831 
832   /// Return the exit of the maximal refined region, that starts at a
833   /// BasicBlock.
834   ///
835   /// @param BB The BasicBlock the refined region starts.
836   BlockT *getMaxRegionExit(BlockT *BB) const;
837 
838   /// Find the smallest region that contains two regions.
839   ///
840   /// @param A The first region.
841   /// @param B The second region.
842   /// @return The smallest region containing A and B.
843   RegionT *getCommonRegion(RegionT *A, RegionT *B) const;
844 
845   /// Find the smallest region that contains two basic blocks.
846   ///
847   /// @param A The first basic block.
848   /// @param B The second basic block.
849   /// @return The smallest region that contains A and B.
850   RegionT *getCommonRegion(BlockT *A, BlockT *B) const {
851     return getCommonRegion(getRegionFor(A), getRegionFor(B));
852   }
853 
854   /// Find the smallest region that contains a set of regions.
855   ///
856   /// @param Regions A vector of regions.
857   /// @return The smallest region that contains all regions in Regions.
858   RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const;
859 
860   /// Find the smallest region that contains a set of basic blocks.
861   ///
862   /// @param BBs A vector of basic blocks.
863   /// @return The smallest region that contains all basic blocks in BBS.
864   RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const;
865 
866   RegionT *getTopLevelRegion() const { return TopLevelRegion; }
867 
868   /// Clear the Node Cache for all Regions.
869   ///
870   /// @see Region::clearNodeCache()
871   void clearNodeCache() {
872     if (TopLevelRegion)
873       TopLevelRegion->clearNodeCache();
874   }
875 
876   void verifyAnalysis() const;
877 };
878 
879 class RegionNode : public RegionNodeBase<RegionTraits<Function>> {
880 public:
881   inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false)
882       : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {}
883 
884   bool operator==(const Region &RN) const {
885     return this == reinterpret_cast<const RegionNode *>(&RN);
886   }
887 };
888 
889 class Region : public RegionBase<RegionTraits<Function>> {
890 public:
891   Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT,
892          Region *Parent = nullptr);
893   ~Region();
894 
895   bool operator==(const RegionNode &RN) const {
896     return &RN == reinterpret_cast<const RegionNode *>(this);
897   }
898 };
899 
900 class RegionInfo : public RegionInfoBase<RegionTraits<Function>> {
901 public:
902   using Base = RegionInfoBase<RegionTraits<Function>>;
903 
904   explicit RegionInfo();
905 
906   RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) {
907     updateRegionTree(*this, TopLevelRegion);
908   }
909 
910   RegionInfo &operator=(RegionInfo &&RHS) {
911     Base::operator=(std::move(static_cast<Base &>(RHS)));
912     updateRegionTree(*this, TopLevelRegion);
913     return *this;
914   }
915 
916   ~RegionInfo() override;
917 
918   /// Handle invalidation explicitly.
919   bool invalidate(Function &F, const PreservedAnalyses &PA,
920                   FunctionAnalysisManager::Invalidator &);
921 
922   // updateStatistics - Update statistic about created regions.
923   void updateStatistics(Region *R) final;
924 
925   void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT,
926                    DominanceFrontier *DF);
927 
928 #ifndef NDEBUG
929   /// Opens a viewer to show the GraphViz visualization of the regions.
930   ///
931   /// Useful during debugging as an alternative to dump().
932   void view();
933 
934   /// Opens a viewer to show the GraphViz visualization of this region
935   /// without instructions in the BasicBlocks.
936   ///
937   /// Useful during debugging as an alternative to dump().
938   void viewOnly();
939 #endif
940 };
941 
942 class RegionInfoPass : public FunctionPass {
943   RegionInfo RI;
944 
945 public:
946   static char ID;
947 
948   explicit RegionInfoPass();
949   ~RegionInfoPass() override;
950 
951   RegionInfo &getRegionInfo() { return RI; }
952 
953   const RegionInfo &getRegionInfo() const { return RI; }
954 
955   /// @name FunctionPass interface
956   //@{
957   bool runOnFunction(Function &F) override;
958   void releaseMemory() override;
959   void verifyAnalysis() const override;
960   void getAnalysisUsage(AnalysisUsage &AU) const override;
961   void print(raw_ostream &OS, const Module *) const override;
962   void dump() const;
963   //@}
964 };
965 
966 /// Analysis pass that exposes the \c RegionInfo for a function.
967 class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> {
968   friend AnalysisInfoMixin<RegionInfoAnalysis>;
969 
970   static AnalysisKey Key;
971 
972 public:
973   using Result = RegionInfo;
974 
975   RegionInfo run(Function &F, FunctionAnalysisManager &AM);
976 };
977 
978 /// Printer pass for the \c RegionInfo.
979 class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
980   raw_ostream &OS;
981 
982 public:
983   explicit RegionInfoPrinterPass(raw_ostream &OS);
984 
985   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
986 };
987 
988 /// Verifier pass for the \c RegionInfo.
989 struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
990   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
991 };
992 
993 template <>
994 template <>
995 inline BasicBlock *
996 RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const {
997   assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
998   return getEntry();
999 }
1000 
1001 template <>
1002 template <>
1003 inline Region *
1004 RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const {
1005   assert(isSubRegion() && "This is not a subregion RegionNode!");
1006   auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this);
1007   return reinterpret_cast<Region *>(Unconst);
1008 }
1009 
1010 template <class Tr>
1011 inline raw_ostream &operator<<(raw_ostream &OS,
1012                                const RegionNodeBase<Tr> &Node) {
1013   using BlockT = typename Tr::BlockT;
1014   using RegionT = typename Tr::RegionT;
1015 
1016   if (Node.isSubRegion())
1017     return OS << Node.template getNodeAs<RegionT>()->getNameStr();
1018   else
1019     return OS << Node.template getNodeAs<BlockT>()->getName();
1020 }
1021 
1022 extern template class RegionBase<RegionTraits<Function>>;
1023 extern template class RegionNodeBase<RegionTraits<Function>>;
1024 extern template class RegionInfoBase<RegionTraits<Function>>;
1025 
1026 } // end namespace llvm
1027 
1028 #endif // LLVM_ANALYSIS_REGIONINFO_H
1029