LLVM 19.0.0git
RegionInfo.h
Go to the documentation of this file.
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"
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_>
76 // FuncT
77 // BlockT
78 // RegionT
79 // RegionNodeT
80 // RegionInfoT
81 using BrokenT = typename FuncT_::UnknownRegionTypeError;
82};
83
84template <>
86 using FuncT = Function;
88 using RegionT = Region;
96 using LoopT = Loop;
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>
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.
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:
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
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 {
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 {
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.
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>
575 : public df_iterator<
576 std::conditional_t<IsConst, const BlockT, BlockT> *> {
577 using super =
579
580 public:
583
584 // Construct the begin iterator.
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
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
608
610
612
615 }
617
620
621 /// Returns a range view of the basic blocks in the region.
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 {
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 //@{
643
645 df_iterator<const RegionNodeT *,
648
653 }
654
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>
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;
688 using SuccIterTy = typename BlockTraits::ChildIteratorType;
689 using PredIterTy = typename InvBlockTraits::ChildIteratorType;
690
693
695
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:
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 {
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()
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);
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:
903
904 explicit RegionInfo();
905
906 RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) {
907 updateRegionTree(*this, TopLevelRegion);
908 }
909
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,
921
922 // updateStatistics - Update statistic about created regions.
923 void updateStatistics(Region *R) final;
924
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
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> {
969
970 static AnalysisKey Key;
971
972public:
974
976};
977
978/// Printer pass for the \c RegionInfo.
979class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
980 raw_ostream &OS;
981
982public:
984
986
987 static bool isRequired() { return true; }
988};
989
990/// Verifier pass for the \c RegionInfo.
991struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
993 static bool isRequired() { return true; }
994};
995
996template <>
997template <>
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>
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
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
convergence region
raw_pwrite_stream & OS
Value * RHS
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
Represent the analysis usage information of a pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Marker class to iterate over the elements of a Region in flat mode.
Definition: RegionInfo.h:112
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
PointerIntPair - This class implements a pair of a pointer and small integer.
IntType getInt() const
PointerTy getPointer() const
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
typename super::value_type value_type
Definition: RegionInfo.h:582
block_iterator_wrapper(value_type Entry, value_type Exit)
Definition: RegionInfo.h:585
A single entry single exit Region.
Definition: RegionInfo.h:254
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
void clearNodeCache()
Clear the cache for BB RegionNodes.
std::string getNameStr() const
Returns the name of the Region.
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:622
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
iterator begin()
Definition: RegionInfo.h:560
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
block_iterator_wrapper< true > const_block_iterator
Definition: RegionInfo.h:607
block_iterator block_begin()
Definition: RegionInfo.h:609
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:370
iterator_range< element_iterator > elements()
Definition: RegionInfo.h:651
block_iterator_wrapper< false > block_iterator
Definition: RegionInfo.h:606
const_iterator end() const
Definition: RegionInfo.h:564
const_block_iterator block_end() const
Definition: RegionInfo.h:616
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
unsigned getDepth() const
Get the nesting level of this Region.
const_block_iterator block_begin() const
Definition: RegionInfo.h:613
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
void dump() const
Print the region to stderr.
block_iterator block_end()
Definition: RegionInfo.h:611
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
element_iterator element_begin()
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
void verifyRegion() const
Verify if the region is a correct region.
RegionBase & operator=(const RegionBase &)=delete
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:364
RegionInfoT * getRegionInfo() const
Return the RegionInfo object, that belongs to this Region.
Definition: RegionInfo.h:426
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
RegionBase(const RegionBase &)=delete
const_iterator begin() const
Definition: RegionInfo.h:563
iterator end()
Definition: RegionInfo.h:561
bool contains(const InstT *Inst) const
Check if the region contains an Instruction.
Definition: RegionInfo.h:469
typename RegionSet::iterator iterator
Definition: RegionInfo.h:557
element_iterator element_end()
df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > const_element_iterator
Definition: RegionInfo.h:647
bool isSimple() const
Is this a simple region?
bool isTopLevelRegion() const
Check if a Region is the TopLevel region.
Definition: RegionInfo.h:385
bool contains(const RegionT *SubRegion) const
Check if the region contains another region.
Definition: RegionInfo.h:454
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
~RegionBase()
Delete the Region and all its subregions.
iterator_range< const_block_iterator > const_block_range
Definition: RegionInfo.h:619
iterator_range< const_element_iterator > elements() const
Definition: RegionInfo.h:657
PrintStyle
PrintStyle - Print region in difference ways.
Definition: RegionInfo.h:429
const_block_range blocks() const
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:629
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
typename RegionSet::const_iterator const_iterator
Definition: RegionInfo.h:558
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
iterator_range< block_iterator > block_range
Definition: RegionInfo.h:618
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:188
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:674
RegionT * getCommonRegion(BlockT *A, BlockT *B) const
Find the smallest region that contains two basic blocks.
Definition: RegionInfo.h:850
void updateRegionTree(RegionInfoT &RI, TheRegionT *R)
Update refences to a RegionInfoT held by the RegionT managed here.
Definition: RegionInfo.h:731
void clearNodeCache()
Clear the Node Cache for all Regions.
Definition: RegionInfo.h:871
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
static bool VerifyRegionInfo
Definition: RegionInfo.h:802
void print(raw_ostream &OS) const
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:866
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
static RegionT::PrintStyle printStyle
Definition: RegionInfo.h:803
RegionInfoBase & operator=(const RegionInfoBase &)=delete
void verifyAnalysis() const
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
RegionInfoBase(const RegionInfoBase &)=delete
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: RegionInfo.cpp:135
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: RegionInfo.cpp:124
~RegionInfoPass() override
RegionInfo & getRegionInfo()
Definition: RegionInfo.h:951
const RegionInfo & getRegionInfo() const
Definition: RegionInfo.h:953
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: RegionInfo.cpp:139
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: RegionInfo.cpp:150
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegionInfo.cpp:143
Printer pass for the RegionInfo.
Definition: RegionInfo.h:979
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:201
RegionInfo(RegionInfo &&Arg)
Definition: RegionInfo.h:906
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:109
~RegionInfo() override
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
Definition: RegionInfo.cpp:111
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:96
RegionInfo & operator=(RegionInfo &&RHS)
Definition: RegionInfo.h:910
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:88
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: RegionInfo.cpp:79
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:117
typename Tr::RegionT RegionT
Definition: RegionInfo.h:122
RegionNodeBase & operator=(const RegionNodeBase &)=delete
RegionNodeBase(RegionT *Parent, BlockT *Entry, bool isSubRegion=false)
Create a RegionNode.
Definition: RegionInfo.h:150
bool isSubRegion() const
Is this RegionNode a subregion?
Definition: RegionInfo.h:188
RegionT * getParent() const
Get the parent Region of this RegionNode.
Definition: RegionInfo.h:166
T * getNodeAs() const
Get the content of this RegionNode.
RegionNodeBase(const RegionNodeBase &)=delete
typename Tr::BlockT BlockT
Definition: RegionInfo.h:121
BlockT * getEntry() const
Get the entry BasicBlock of this RegionNode.
Definition: RegionInfo.h:174
RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion=false)
Definition: RegionInfo.h:881
bool operator==(const Region &RN) const
Definition: RegionInfo.h:884
bool operator==(const RegionNode &RN) const
Definition: RegionInfo.h:895
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
df_iterator< T > df_begin(const T &G)
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:92
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
df_iterator< T > df_end(const T &G)
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:114
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91
Verifier pass for the RegionInfo.
Definition: RegionInfo.h:991
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:209
static unsigned getNumSuccessors(BasicBlock *BB)
Definition: RegionInfo.h:99
typename FuncT_::UnknownRegionTypeError BrokenT
Definition: RegionInfo.h:81