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/Dominators.h"
46#include "llvm/IR/PassManager.h"
47#include "llvm/Pass.h"
48#include <algorithm>
49#include <cassert>
50#include <map>
51#include <memory>
52#include <set>
53#include <string>
54#include <type_traits>
55#include <vector>
56
57namespace llvm {
58
59class BasicBlock;
60class DominanceFrontier;
61class Loop;
62class LoopInfo;
63class PostDominatorTree;
64class Region;
65template <class RegionTr> class RegionBase;
66class RegionInfo;
67template <class RegionTr> class RegionInfoBase;
68class RegionNode;
69class raw_ostream;
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.
74template <class FuncT_>
75struct RegionTraits {
76 // FuncT
77 // BlockT
78 // RegionT
79 // RegionNodeT
80 // RegionInfoT
81 using BrokenT = typename FuncT_::UnknownRegionTypeError;
82};
83
84template <>
85struct 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.
111template <class GraphType>
112class FlatIt {};
113
114/// A RegionNode represents a subregion or a BasicBlock that is part of a
115/// Region.
116template <class Tr>
117class RegionNodeBase {
118 friend class RegionBase<Tr>;
119
120public:
121 using BlockT = typename Tr::BlockT;
122 using RegionT = typename Tr::RegionT;
123
124private:
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
141protected:
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
154public:
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 -passes='print<regions>' 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.
253template <class Tr>
254class 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
302public:
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.
664template <class Tr>
665inline 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.
673template <class Tr>
674class 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
725protected:
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
739private:
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
798public:
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(BB: A), getRegionFor(BB: 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
879class RegionNode : public RegionNodeBase<RegionTraits<Function>> {
880public:
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
889class Region : public RegionBase<RegionTraits<Function>> {
890public:
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
900class RegionInfo : public RegionInfoBase<RegionTraits<Function>> {
901public:
902 using Base = RegionInfoBase<RegionTraits<Function>>;
903
904 explicit RegionInfo();
905
906 RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) {
907 updateRegionTree(RI&: *this, R: TopLevelRegion);
908 }
909
910 RegionInfo &operator=(RegionInfo &&RHS) {
911 Base::operator=(RHS: std::move(static_cast<Base &>(RHS)));
912 updateRegionTree(RI&: *this, R: 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
942class RegionInfoPass : public FunctionPass {
943 RegionInfo RI;
944
945public:
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.
967class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> {
968 friend AnalysisInfoMixin<RegionInfoAnalysis>;
969
970 static AnalysisKey Key;
971
972public:
973 using Result = RegionInfo;
974
975 RegionInfo run(Function &F, FunctionAnalysisManager &AM);
976};
977
978/// Printer pass for the \c RegionInfo.
979class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
980 raw_ostream &OS;
981
982public:
983 explicit RegionInfoPrinterPass(raw_ostream &OS);
984
985 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
986
987 static bool isRequired() { return true; }
988};
989
990/// Verifier pass for the \c RegionInfo.
991struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
992 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
993 static bool isRequired() { return true; }
994};
995
996template <>
997template <>
998inline BasicBlock *
999RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const {
1000 assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
1001 return getEntry();
1002}
1003
1004template <>
1005template <>
1006inline Region *
1007RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const {
1008 assert(isSubRegion() && "This is not a subregion RegionNode!");
1009 auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this);
1010 return reinterpret_cast<Region *>(Unconst);
1011}
1012
1013template <class Tr>
1014inline raw_ostream &operator<<(raw_ostream &OS,
1015 const RegionNodeBase<Tr> &Node) {
1016 using BlockT = typename Tr::BlockT;
1017 using RegionT = typename Tr::RegionT;
1018
1019 if (Node.isSubRegion())
1020 return OS << Node.template getNodeAs<RegionT>()->getNameStr();
1021 else
1022 return OS << Node.template getNodeAs<BlockT>()->getName();
1023}
1024
1025extern template class RegionBase<RegionTraits<Function>>;
1026extern template class RegionNodeBase<RegionTraits<Function>>;
1027extern template class RegionInfoBase<RegionTraits<Function>>;
1028
1029} // end namespace llvm
1030
1031#endif // LLVM_ANALYSIS_REGIONINFO_H
1032

source code of llvm/include/llvm/Analysis/RegionInfo.h