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