LLVM  14.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"
41 #include "llvm/ADT/GraphTraits.h"
44 #include "llvm/Config/llvm-config.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/Dominators.h"
47 #include "llvm/IR/PassManager.h"
48 #include "llvm/Pass.h"
50 #include <algorithm>
51 #include <cassert>
52 #include <map>
53 #include <memory>
54 #include <set>
55 #include <string>
56 #include <type_traits>
57 #include <vector>
58 
59 namespace llvm {
60 
61 class DominanceFrontier;
62 class Loop;
63 class LoopInfo;
64 class PostDominatorTree;
65 class Region;
66 template <class RegionTr> class RegionBase;
67 class RegionInfo;
68 template <class RegionTr> class RegionInfoBase;
69 class RegionNode;
70 
71 // Class to be specialized for different users of RegionInfo
72 // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to
73 // pass around an unreasonable number of template parameters.
74 template <class FuncT_>
75 struct RegionTraits {
76  // FuncT
77  // BlockT
78  // RegionT
79  // RegionNodeT
80  // RegionInfoT
81  using BrokenT = typename FuncT_::UnknownRegionTypeError;
82 };
83 
84 template <>
86  using FuncT = Function;
87  using BlockT = BasicBlock;
88  using RegionT = Region;
95  using InstT = Instruction;
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.
111 template <class GraphType>
112 class FlatIt {};
113 
114 /// A RegionNode represents a subregion or a BasicBlock that is part of a
115 /// Region.
116 template <class Tr>
118  friend class RegionBase<Tr>;
119 
120 public:
121  using BlockT = typename Tr::BlockT;
122  using RegionT = typename Tr::RegionT;
123 
124 private:
125  /// This is the entry basic block that starts this region node. If this is a
126  /// BasicBlock RegionNode, then entry is just the basic block, that this
127  /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode.
128  ///
129  /// In the BBtoRegionNode map of the parent of this node, BB will always map
130  /// to this node no matter which kind of node this one is.
131  ///
132  /// The node can hold either a Region or a BasicBlock.
133  /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
134  /// RegionNode.
136 
137  /// The parent Region of this RegionNode.
138  /// @see getParent()
139  RegionT *parent;
140 
141 protected:
142  /// Create a RegionNode.
143  ///
144  /// @param Parent The parent of this RegionNode.
145  /// @param Entry The entry BasicBlock of the RegionNode. If this
146  /// RegionNode represents a BasicBlock, this is the
147  /// BasicBlock itself. If it represents a subregion, this
148  /// is the entry BasicBlock of the subregion.
149  /// @param isSubRegion If this RegionNode represents a SubRegion.
150  inline RegionNodeBase(RegionT *Parent, BlockT *Entry,
151  bool isSubRegion = false)
152  : entry(Entry, isSubRegion), parent(Parent) {}
153 
154 public:
155  RegionNodeBase(const RegionNodeBase &) = delete;
156  RegionNodeBase &operator=(const RegionNodeBase &) = delete;
157 
158  /// Get the parent Region of this RegionNode.
159  ///
160  /// The parent Region is the Region this RegionNode belongs to. If for
161  /// example a BasicBlock is element of two Regions, there exist two
162  /// RegionNodes for this BasicBlock. Each with the getParent() function
163  /// pointing to the Region this RegionNode belongs to.
164  ///
165  /// @return Get the parent Region of this RegionNode.
166  inline RegionT *getParent() const { return parent; }
167 
168  /// Get the entry BasicBlock of this RegionNode.
169  ///
170  /// If this RegionNode represents a BasicBlock this is just the BasicBlock
171  /// itself, otherwise we return the entry BasicBlock of the Subregion
172  ///
173  /// @return The entry BasicBlock of this RegionNode.
174  inline BlockT *getEntry() const { return entry.getPointer(); }
175 
176  /// Get the content of this RegionNode.
177  ///
178  /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
179  /// check the type of the content with the isSubRegion() function call.
180  ///
181  /// @return The content of this RegionNode.
182  template <class T> inline T *getNodeAs() const;
183 
184  /// Is this RegionNode a subregion?
185  ///
186  /// @return True if it contains a subregion. False if it contains a
187  /// BasicBlock.
188  inline bool isSubRegion() const { return entry.getInt(); }
189 };
190 
191 //===----------------------------------------------------------------------===//
192 /// A single entry single exit Region.
193 ///
194 /// A Region is a connected subgraph of a control flow graph that has exactly
195 /// two connections to the remaining graph. It can be used to analyze or
196 /// optimize parts of the control flow graph.
197 ///
198 /// A <em> simple Region </em> is connected to the remaining graph by just two
199 /// edges. One edge entering the Region and another one leaving the Region.
200 ///
201 /// An <em> extended Region </em> (or just Region) is a subgraph that can be
202 /// transform into a simple Region. The transformation is done by adding
203 /// BasicBlocks that merge several entry or exit edges so that after the merge
204 /// just one entry and one exit edge exists.
205 ///
206 /// The \e Entry of a Region is the first BasicBlock that is passed after
207 /// entering the Region. It is an element of the Region. The entry BasicBlock
208 /// dominates all BasicBlocks in the Region.
209 ///
210 /// The \e Exit of a Region is the first BasicBlock that is passed after
211 /// leaving the Region. It is not an element of the Region. The exit BasicBlock,
212 /// postdominates all BasicBlocks in the Region.
213 ///
214 /// A <em> canonical Region </em> cannot be constructed by combining smaller
215 /// Regions.
216 ///
217 /// Region A is the \e parent of Region B, if B is completely contained in A.
218 ///
219 /// Two canonical Regions either do not intersect at all or one is
220 /// the parent of the other.
221 ///
222 /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
223 /// Regions in the control flow graph and E is the \e parent relation of these
224 /// Regions.
225 ///
226 /// Example:
227 ///
228 /// \verbatim
229 /// A simple control flow graph, that contains two regions.
230 ///
231 /// 1
232 /// / |
233 /// 2 |
234 /// / \ 3
235 /// 4 5 |
236 /// | | |
237 /// 6 7 8
238 /// \ | /
239 /// \ |/ Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
240 /// 9 Region B: 2 -> 9 {2,4,5,6,7}
241 /// \endverbatim
242 ///
243 /// You can obtain more examples by either calling
244 ///
245 /// <tt> "opt -regions -analyze anyprogram.ll" </tt>
246 /// or
247 /// <tt> "opt -view-regions-only anyprogram.ll" </tt>
248 ///
249 /// on any LLVM file you are interested in.
250 ///
251 /// The first call returns a textual representation of the program structure
252 /// tree, the second one creates a graphical representation using graphviz.
253 template <class Tr>
254 class RegionBase : public RegionNodeBase<Tr> {
255  friend class RegionInfoBase<Tr>;
256 
257  using FuncT = typename Tr::FuncT;
258  using BlockT = typename Tr::BlockT;
259  using RegionInfoT = typename Tr::RegionInfoT;
260  using RegionT = typename Tr::RegionT;
261  using RegionNodeT = typename Tr::RegionNodeT;
262  using DomTreeT = typename Tr::DomTreeT;
263  using LoopT = typename Tr::LoopT;
264  using LoopInfoT = typename Tr::LoopInfoT;
265  using InstT = typename Tr::InstT;
266 
269  using SuccIterTy = typename BlockTraits::ChildIteratorType;
270  using PredIterTy = typename InvBlockTraits::ChildIteratorType;
271 
272  // Information necessary to manage this Region.
273  RegionInfoT *RI;
274  DomTreeT *DT;
275 
276  // The exit BasicBlock of this region.
277  // (The entry BasicBlock is part of RegionNode)
278  BlockT *exit;
279 
280  using RegionSet = std::vector<std::unique_ptr<RegionT>>;
281 
282  // The subregions of this region.
283  RegionSet children;
284 
285  using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>;
286 
287  // Save the BasicBlock RegionNodes that are element of this Region.
288  mutable BBNodeMapT BBNodeMap;
289 
290  /// Check if a BB is in this Region. This check also works
291  /// if the region is incorrectly built. (EXPENSIVE!)
292  void verifyBBInRegion(BlockT *BB) const;
293 
294  /// Walk over all the BBs of the region starting from BB and
295  /// verify that all reachable basic blocks are elements of the region.
296  /// (EXPENSIVE!)
297  void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const;
298 
299  /// Verify if the region and its children are valid regions (EXPENSIVE!)
300  void verifyRegionNest() const;
301 
302 public:
303  /// Create a new region.
304  ///
305  /// @param Entry The entry basic block of the region.
306  /// @param Exit The exit basic block of the region.
307  /// @param RI The region info object that is managing this region.
308  /// @param DT The dominator tree of the current function.
309  /// @param Parent The surrounding region or NULL if this is a top level
310  /// region.
311  RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT,
312  RegionT *Parent = nullptr);
313 
314  RegionBase(const RegionBase &) = delete;
315  RegionBase &operator=(const RegionBase &) = delete;
316 
317  /// Delete the Region and all its subregions.
318  ~RegionBase();
319 
320  /// Get the entry BasicBlock of the Region.
321  /// @return The entry BasicBlock of the region.
322  BlockT *getEntry() const {
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:
582  using value_type = typename super::value_type;
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 
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 
610 
612 
615  }
617 
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 {
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 =
643 
644  using const_element_iterator =
645  df_iterator<const RegionNodeT *,
648 
652  return make_range(element_begin(), element_end());
653  }
654 
658  return make_range(element_begin(), element_end());
659  }
660  //@}
661 };
662 
663 /// Print a RegionNode.
664 template <class Tr>
665 inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node);
666 
667 //===----------------------------------------------------------------------===//
668 /// Analysis that detects all canonical Regions.
669 ///
670 /// The RegionInfo pass detects all canonical regions in a function. The Regions
671 /// are connected using the parent relation. This builds a Program Structure
672 /// Tree.
673 template <class Tr>
674 class RegionInfoBase {
675  friend class RegionInfo;
676  friend class MachineRegionInfo;
677 
678  using BlockT = typename Tr::BlockT;
679  using FuncT = typename Tr::FuncT;
680  using RegionT = typename Tr::RegionT;
681  using RegionInfoT = typename Tr::RegionInfoT;
682  using DomTreeT = typename Tr::DomTreeT;
683  using DomTreeNodeT = typename Tr::DomTreeNodeT;
684  using PostDomTreeT = typename Tr::PostDomTreeT;
685  using DomFrontierT = typename Tr::DomFrontierT;
688  using SuccIterTy = typename BlockTraits::ChildIteratorType;
689  using PredIterTy = typename InvBlockTraits::ChildIteratorType;
690 
693 
694  RegionInfoBase();
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 
725 protected:
726  /// Update refences to a RegionInfoT held by the RegionT managed here
727  ///
728  /// This is a post-move helper. Regions hold references to the owning
729  /// RegionInfo object. After a move these need to be fixed.
730  template<typename TheRegionT>
731  void updateRegionTree(RegionInfoT &RI, TheRegionT *R) {
732  if (!R)
733  return;
734  R->RI = &RI;
735  for (auto &SubR : *R)
736  updateRegionTree(RI, SubR.get());
737  }
738 
739 private:
740  /// Wipe this region tree's state without releasing any resources.
741  ///
742  /// This is essentially a post-move helper only. It leaves the object in an
743  /// assignable and destroyable state, but otherwise invalid.
744  void wipe() {
745  DT = nullptr;
746  PDT = nullptr;
747  DF = nullptr;
748  TopLevelRegion = nullptr;
749  BBtoRegion.clear();
750  }
751 
752  // Check whether the entries of BBtoRegion for the BBs of region
753  // SR are correct. Triggers an assertion if not. Calls itself recursively for
754  // subregions.
755  void verifyBBMap(const RegionT *SR) const;
756 
757  // Returns true if BB is in the dominance frontier of
758  // entry, because it was inherited from exit. In the other case there is an
759  // edge going from entry to BB without passing exit.
760  bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;
761 
762  // Check if entry and exit surround a valid region, based on
763  // dominance tree and dominance frontier.
764  bool isRegion(BlockT *entry, BlockT *exit) const;
765 
766  // Saves a shortcut pointing from entry to exit.
767  // This function may extend this shortcut if possible.
768  void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const;
769 
770  // Returns the next BB that postdominates N, while skipping
771  // all post dominators that cannot finish a canonical region.
772  DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const;
773 
774  // A region is trivial, if it contains only one BB.
775  bool isTrivialRegion(BlockT *entry, BlockT *exit) const;
776 
777  // Creates a single entry single exit region.
778  RegionT *createRegion(BlockT *entry, BlockT *exit);
779 
780  // Detect all regions starting with bb 'entry'.
781  void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut);
782 
783  // Detects regions in F.
784  void scanForRegions(FuncT &F, BBtoBBMap *ShortCut);
785 
786  // Get the top most parent with the same entry block.
787  RegionT *getTopMostParent(RegionT *region);
788 
789  // Build the region hierarchy after all region detected.
790  void buildRegionsTree(DomTreeNodeT *N, RegionT *region);
791 
792  // Update statistic about created regions.
793  virtual void updateStatistics(RegionT *R) = 0;
794 
795  // Detect all regions in function and build the region tree.
796  void calculate(FuncT &F);
797 
798 public:
799  RegionInfoBase(const RegionInfoBase &) = delete;
800  RegionInfoBase &operator=(const RegionInfoBase &) = delete;
801 
802  static bool VerifyRegionInfo;
803  static typename RegionT::PrintStyle printStyle;
804 
805  void print(raw_ostream &OS) const;
806 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
807  void dump() const;
808 #endif
809 
810  void releaseMemory();
811 
812  /// Get the smallest region that contains a BasicBlock.
813  ///
814  /// @param BB The basic block.
815  /// @return The smallest region, that contains BB or NULL, if there is no
816  /// region containing BB.
817  RegionT *getRegionFor(BlockT *BB) const;
818 
819  /// Set the smallest region that surrounds a basic block.
820  ///
821  /// @param BB The basic block surrounded by a region.
822  /// @param R The smallest region that surrounds BB.
823  void setRegionFor(BlockT *BB, RegionT *R);
824 
825  /// A shortcut for getRegionFor().
826  ///
827  /// @param BB The basic block.
828  /// @return The smallest region, that contains BB or NULL, if there is no
829  /// region containing BB.
830  RegionT *operator[](BlockT *BB) const;
831 
832  /// Return the exit of the maximal refined region, that starts at a
833  /// BasicBlock.
834  ///
835  /// @param BB The BasicBlock the refined region starts.
836  BlockT *getMaxRegionExit(BlockT *BB) const;
837 
838  /// Find the smallest region that contains two regions.
839  ///
840  /// @param A The first region.
841  /// @param B The second region.
842  /// @return The smallest region containing A and B.
843  RegionT *getCommonRegion(RegionT *A, RegionT *B) const;
844 
845  /// Find the smallest region that contains two basic blocks.
846  ///
847  /// @param A The first basic block.
848  /// @param B The second basic block.
849  /// @return The smallest region that contains A and B.
850  RegionT *getCommonRegion(BlockT *A, BlockT *B) const {
852  }
853 
854  /// Find the smallest region that contains a set of regions.
855  ///
856  /// @param Regions A vector of regions.
857  /// @return The smallest region that contains all regions in Regions.
858  RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const;
859 
860  /// Find the smallest region that contains a set of basic blocks.
861  ///
862  /// @param BBs A vector of basic blocks.
863  /// @return The smallest region that contains all basic blocks in BBS.
864  RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const;
865 
866  RegionT *getTopLevelRegion() const { return TopLevelRegion; }
867 
868  /// Clear the Node Cache for all Regions.
869  ///
870  /// @see Region::clearNodeCache()
871  void clearNodeCache() {
872  if (TopLevelRegion)
873  TopLevelRegion->clearNodeCache();
874  }
875 
876  void verifyAnalysis() const;
877 };
878 
879 class RegionNode : public RegionNodeBase<RegionTraits<Function>> {
880 public:
881  inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false)
882  : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {}
883 
884  bool operator==(const Region &RN) const {
885  return this == reinterpret_cast<const RegionNode *>(&RN);
886  }
887 };
888 
889 class Region : public RegionBase<RegionTraits<Function>> {
890 public:
891  Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT,
892  Region *Parent = nullptr);
893  ~Region();
894 
895  bool operator==(const RegionNode &RN) const {
896  return &RN == reinterpret_cast<const RegionNode *>(this);
897  }
898 };
899 
900 class RegionInfo : public RegionInfoBase<RegionTraits<Function>> {
901 public:
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 
926  DominanceFrontier *DF);
927 
928 #ifndef NDEBUG
929  /// Opens a viewer to show the GraphViz visualization of the regions.
930  ///
931  /// Useful during debugging as an alternative to dump().
932  void view();
933 
934  /// Opens a viewer to show the GraphViz visualization of this region
935  /// without instructions in the BasicBlocks.
936  ///
937  /// Useful during debugging as an alternative to dump().
938  void viewOnly();
939 #endif
940 };
941 
942 class RegionInfoPass : public FunctionPass {
943  RegionInfo RI;
944 
945 public:
946  static char ID;
947 
948  explicit RegionInfoPass();
949  ~RegionInfoPass() override;
950 
951  RegionInfo &getRegionInfo() { return RI; }
952 
953  const RegionInfo &getRegionInfo() const { return RI; }
954 
955  /// @name FunctionPass interface
956  //@{
957  bool runOnFunction(Function &F) override;
958  void releaseMemory() override;
959  void verifyAnalysis() const override;
960  void getAnalysisUsage(AnalysisUsage &AU) const override;
961  void print(raw_ostream &OS, const Module *) const override;
962  void dump() const;
963  //@}
964 };
965 
966 /// Analysis pass that exposes the \c RegionInfo for a function.
967 class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> {
969 
970  static AnalysisKey Key;
971 
972 public:
974 
976 };
977 
978 /// Printer pass for the \c RegionInfo.
979 class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
980  raw_ostream &OS;
981 
982 public:
983  explicit RegionInfoPrinterPass(raw_ostream &OS);
984 
986 };
987 
988 /// Verifier pass for the \c RegionInfo.
989 struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
991 };
992 
993 template <>
994 template <>
995 inline BasicBlock *
996 RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const {
997  assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
998  return getEntry();
999 }
1000 
1001 template <>
1002 template <>
1003 inline Region *
1004 RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const {
1005  assert(isSubRegion() && "This is not a subregion RegionNode!");
1006  auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this);
1007  return reinterpret_cast<Region *>(Unconst);
1008 }
1009 
1010 template <class Tr>
1012  const RegionNodeBase<Tr> &Node) {
1013  using BlockT = typename Tr::BlockT;
1014  using RegionT = typename Tr::RegionT;
1015 
1016  if (Node.isSubRegion())
1017  return OS << Node.template getNodeAs<RegionT>()->getNameStr();
1018  else
1019  return OS << Node.template getNodeAs<BlockT>()->getName();
1020 }
1021 
1022 extern template class RegionBase<RegionTraits<Function>>;
1023 extern template class RegionNodeBase<RegionTraits<Function>>;
1024 extern template class RegionInfoBase<RegionTraits<Function>>;
1025 
1026 } // end namespace llvm
1027 
1028 #endif // LLVM_ANALYSIS_REGIONINFO_H
llvm::RegionInfoPass::ID
static char ID
Definition: RegionInfo.h:946
llvm::RegionInfo::viewOnly
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
Definition: RegionInfo.cpp:110
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::RegionBase::begin
const_iterator begin() const
Definition: RegionInfo.h:563
llvm::RegionInfo::updateStatistics
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:87
llvm::RegionBase::getRegionInfo
RegionInfoT * getRegionInfo() const
Return the RegionInfo object, that belongs to this Region.
Definition: RegionInfo.h:426
llvm::RegionBase::getBBNode
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
Definition: RegionInfoImpl.h:359
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::RegionBase::block_iterator_wrapper::operator*
BlockT * operator*() const
Definition: RegionInfo.h:601
llvm::RegionBase::addSubRegion
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
Definition: RegionInfoImpl.h:393
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::RegionBase::end
const_iterator end() const
Definition: RegionInfo.h:564
llvm::RegionInfoBase::getTopLevelRegion
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:866
llvm::RegionBase::end
iterator end()
Definition: RegionInfo.h:561
llvm::RegionInfoVerifierPass
Verifier pass for the RegionInfo.
Definition: RegionInfo.h:989
llvm::RegionInfoPrinterPass::RegionInfoPrinterPass
RegionInfoPrinterPass(raw_ostream &OS)
Definition: RegionInfo.cpp:197
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::RegionInfo::recalculate
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:95
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::RegionBase::block_end
block_iterator block_end()
Definition: RegionInfo.h:611
Pass.h
llvm::RegionBase
A single entry single exit Region.
Definition: RegionInfo.h:66
llvm::RegionInfoPass::releaseMemory
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:134
llvm::DomTreeNode
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:81
llvm::RegionBase::~RegionBase
~RegionBase()
Delete the Region and all its subregions.
Definition: RegionInfoImpl.h:50
llvm::FlatIt
Marker class to iterate over the elements of a Region in flat mode.
Definition: RegionInfo.h:112
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:223
llvm::RegionInfoPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: RegionInfo.cpp:138
llvm::AMDGPU::HSAMD::AddressSpaceQualifier::Region
@ Region
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::RegionInfoBase::operator[]
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
Definition: RegionInfoImpl.h:827
llvm::RegionInfoPass::dump
void dump() const
Definition: RegionInfo.cpp:154
llvm::RegionBase::transferChildrenTo
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
Definition: RegionInfoImpl.h:384
llvm::RegionInfoPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: RegionInfo.cpp:123
DenseMap.h
llvm::RegionBase::replaceExitRecursive
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
Definition: RegionInfoImpl.h:86
llvm::RegionBase::elements
iterator_range< const_element_iterator > elements() const
Definition: RegionInfo.h:657
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::RegionBase::removeSubRegion
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
Definition: RegionInfoImpl.h:436
llvm::RegionBase::outermostLoopInRegion
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
Definition: RegionInfoImpl.h:143
llvm::RegionInfoPrinterPass
Printer pass for the RegionInfo.
Definition: RegionInfo.h:979
llvm::RegionBase::block_begin
const_block_iterator block_begin() const
Definition: RegionInfo.h:613
llvm::RegionInfoPass::getRegionInfo
const RegionInfo & getRegionInfo() const
Definition: RegionInfo.h:953
llvm::RegionInfoPass::getRegionInfo
RegionInfo & getRegionInfo()
Definition: RegionInfo.h:951
DepthFirstIterator.h
llvm::RegionBase::block_iterator_wrapper
Definition: RegionInfo.h:574
llvm::RegionBase< RegionTraits< Function > >::const_block_iterator
block_iterator_wrapper< true > const_block_iterator
Definition: RegionInfo.h:607
llvm::RegionBase< RegionTraits< Function > >::iterator
typename RegionSet::iterator iterator
Definition: RegionInfo.h:557
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
PointerIntPair.h
llvm::RegionBase::replaceEntry
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:57
llvm::RegionTraits< Function >::getNumSuccessors
static unsigned getNumSuccessors(BasicBlock *BB)
Definition: RegionInfo.h:99
GraphTraits.h
llvm::RegionBase::block_iterator_wrapper::value_type
typename super::value_type value_type
Definition: RegionInfo.h:582
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::RegionBase::block_iterator_wrapper::block_iterator_wrapper
block_iterator_wrapper(value_type Entry, value_type Exit)
Definition: RegionInfo.h:585
llvm::RegionBase::element_iterator
df_iterator< RegionNodeT *, df_iterator_default_set< RegionNodeT * >, false, GraphTraits< RegionNodeT * > > element_iterator
Definition: RegionInfo.h:642
llvm::RegionBase::RegionBase
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.
llvm::RegionInfoAnalysis
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
llvm::RegionInfoBase::VerifyRegionInfo
static bool VerifyRegionInfo
Definition: RegionInfo.h:802
llvm::RegionBase::operator=
RegionBase & operator=(const RegionBase &)=delete
llvm::RegionBase::isTopLevelRegion
bool isTopLevelRegion() const
Check if a Region is the TopLevel region.
Definition: RegionInfo.h:385
llvm::RegionInfoBase::dump
void dump() const
Definition: RegionInfoImpl.h:792
llvm::RegionBase< RegionTraits< Function > >::PrintStyle
PrintStyle
PrintStyle - Print region in difference ways.
Definition: RegionInfo.h:429
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::RegionInfo::operator=
RegionInfo & operator=(RegionInfo &&RHS)
Definition: RegionInfo.h:910
llvm::RegionBase::element_end
element_iterator element_end()
Definition: RegionInfoImpl.h:319
llvm::RegionBase::blocks
const_block_range blocks() const
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:629
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::RegionBase::verifyRegion
void verifyRegion() const
Verify if the region is a correct region.
Definition: RegionInfoImpl.h:294
llvm::RegionNodeBase::operator=
RegionNodeBase & operator=(const RegionNodeBase &)=delete
llvm::Instruction
Definition: Instruction.h:45
llvm::RegionBase::const_block_range
iterator_range< const_block_iterator > const_block_range
Definition: RegionInfo.h:619
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::RegionInfoBase::clearNodeCache
void clearNodeCache()
Clear the Node Cache for all Regions.
Definition: RegionInfo.h:871
llvm::df_iterator< std::conditional_t< IsConst, const BlockT, BlockT > * >::operator*
const NodeRef & operator*() const
Definition: DepthFirstIterator.h:168
llvm::RegionInfoPass::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: RegionInfo.cpp:149
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::RegionInfoBase
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:68
llvm::RegionBase::PrintNone
@ PrintNone
Definition: RegionInfo.h:429
DF
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
llvm::RegionInfoPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:200
llvm::RegionNode
Definition: RegionInfo.h:879
llvm::RegionBase::blocks
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:622
llvm::RegionInfoBase::printStyle
static RegionT::PrintStyle printStyle
Definition: RegionInfo.h:803
llvm::RegionInfoBase::getRegionFor
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
Definition: RegionInfoImpl.h:817
llvm::RegionInfo::RegionInfo
RegionInfo(RegionInfo &&Arg)
Definition: RegionInfo.h:906
llvm::df_iterator_storage< df_iterator_default_set< typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * >::NodeRef >, false >::Visited
df_iterator_default_set< typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * >::NodeRef > Visited
Definition: DepthFirstIterator.h:52
BasicBlock.h
llvm::RegionNodeBase::getNodeAs
T * getNodeAs() const
Get the content of this RegionNode.
llvm::RegionNode::operator==
bool operator==(const Region &RN) const
Definition: RegionInfo.h:884
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::df_iterator< std::conditional_t< IsConst, const BlockT, BlockT > * >::value_type
typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * > ::NodeRef value_type
Definition: DepthFirstIterator.h:88
llvm::RegionBase::clearNodeCache
void clearNodeCache()
Clear the cache for BB RegionNodes.
Definition: RegionInfoImpl.h:532
llvm::RegionBase::PrintRN
@ PrintRN
Definition: RegionInfo.h:429
llvm::RegionInfoBase::setRegionFor
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
Definition: RegionInfoImpl.h:822
llvm::RegionBase::element_begin
element_iterator element_begin()
Definition: RegionInfoImpl.h:314
llvm::RegionBase::contains
bool contains(const RegionT *SubRegion) const
Check if the region contains another region.
Definition: RegionInfo.h:454
llvm::HexStyle::Style
Style
Definition: MCInstPrinter.h:32
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:218
llvm::RegionBase::getSubRegionNode
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
Definition: RegionInfoImpl.h:338
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
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:1609
llvm::RegionInfoAnalysis::run
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:187
llvm::RegionNodeBase< RegionTraits< Function > >::RegionT
typename RegionTraits< Function > ::RegionT RegionT
Definition: RegionInfo.h:122
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
iterator_range.h
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::RegionInfoBase::print
void print(raw_ostream &OS) const
Definition: RegionInfoImpl.h:784
llvm::RegionBase::contains
bool contains(const InstT *Inst) const
Check if the region contains an Instruction.
Definition: RegionInfo.h:469
llvm::df_iterator_default_set::insert
std::pair< iterator, bool > insert(NodeRef N)
Definition: DepthFirstIterator.h:73
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::RegionNodeBase::RegionNodeBase
RegionNodeBase(RegionT *Parent, BlockT *Entry, bool isSubRegion=false)
Create a RegionNode.
Definition: RegionInfo.h:150
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::RegionNodeBase::isSubRegion
bool isSubRegion() const
Is this RegionNode a subregion?
Definition: RegionInfo.h:188
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::RegionInfoBase::getCommonRegion
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
Definition: RegionInfoImpl.h:873
llvm::RegionBase::print
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
Definition: RegionInfoImpl.h:490
A
* A
Definition: README_ALTIVEC.txt:89
llvm::RegionBase::block_end
const_block_iterator block_end() const
Definition: RegionInfo.h:616
llvm::RegionBase< RegionTraits< Function > >::const_iterator
typename RegionSet::const_iterator const_iterator
Definition: RegionInfo.h:558
llvm::RegionBase::begin
iterator begin()
Definition: RegionInfo.h:560
llvm::RegionBase::getExpandedRegion
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
Definition: RegionInfoImpl.h:459
llvm::RegionBase::const_element_iterator
df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > const_element_iterator
Definition: RegionInfo.h:647
llvm::RegionInfo
Definition: RegionInfo.h:900
Node
Definition: ItaniumDemangle.h:235
llvm::RegionBase::getEnteringBlock
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
Definition: RegionInfoImpl.h:163
llvm::DomTreeNodeBase< BasicBlock >
llvm::RegionBase::dump
void dump() const
Print the region to stderr.
Definition: RegionInfoImpl.h:526
llvm::RegionInfo::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: RegionInfo.cpp:78
llvm::RegionInfo::view
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:108
llvm::RegionBase< RegionTraits< Function > >::block_iterator
block_iterator_wrapper< false > block_iterator
Definition: RegionInfo.h:606
llvm::RegionBase::getDepth
unsigned getDepth() const
Get the nesting level of this Region.
Definition: RegionInfoImpl.h:449
llvm::RegionInfoBase::getCommonRegion
RegionT * getCommonRegion(BlockT *A, BlockT *B) const
Find the smallest region that contains two basic blocks.
Definition: RegionInfo.h:850
llvm::RegionInfo::RegionInfo
RegionInfo()
llvm::RegionBase::getNode
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:370
std
Definition: BitVector.h:838
llvm::RegionInfoBase::verifyAnalysis
void verifyAnalysis() const
Definition: RegionInfoImpl.h:804
llvm::RegionNode::RegionNode
RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion=false)
Definition: RegionInfo.h:881
llvm::RegionBase::PrintBB
@ PrintBB
Definition: RegionInfo.h:429
llvm::RegionTraits
Definition: RegionInfo.h:75
llvm::RegionBase::getExitingBlocks
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
Definition: RegionInfoImpl.h:181
PassManager.h
llvm::RegionBase::getNameStr
std::string getNameStr() const
Returns the name of the Region.
Definition: RegionInfoImpl.h:230
llvm::RegionBase::replaceEntryRecursive
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
Definition: RegionInfoImpl.h:68
llvm::RegionInfo::~RegionInfo
~RegionInfo() override
llvm::RegionBase::block_iterator_wrapper::block_iterator_wrapper
block_iterator_wrapper()
Definition: RegionInfo.h:594
llvm::RegionBase::block_iterator_wrapper::block_iterator_wrapper
block_iterator_wrapper(super I)
Definition: RegionInfo.h:596
llvm::RegionBase::contains
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Definition: RegionInfoImpl.h:104
llvm::MachineRegionInfo
Definition: MachineRegionInfo.h:73
llvm::Region::Region
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:61
llvm::RegionBase::block_range
iterator_range< block_iterator > block_range
Definition: RegionInfo.h:618
llvm::RegionBase::isSimple
bool isSimple() const
Is this a simple region?
Definition: RegionInfoImpl.h:225
llvm::RegionInfoPass::~RegionInfoPass
~RegionInfoPass() override
llvm::RegionInfoBase::getMaxRegionExit
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
Definition: RegionInfoImpl.h:833
llvm::RegionNodeBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of this RegionNode.
Definition: RegionInfo.h:174
llvm::PointerIntPair< BlockT *, 1, bool >
llvm::RegionInfoBase::releaseMemory
void releaseMemory()
Definition: RegionInfoImpl.h:796
llvm::DominanceFrontier
Definition: DominanceFrontier.h:141
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
Dominators.h
N
#define N
llvm::RegionBase::block_begin
block_iterator block_begin()
Definition: RegionInfo.h:609
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::RegionNodeBase
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:117
llvm::SmallVectorImpl< BlockT * >
llvm::RegionNodeBase::getParent
RegionT * getParent() const
Get the parent Region of this RegionNode.
Definition: RegionInfo.h:166
llvm::RegionInfoPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegionInfo.cpp:142
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::RegionNodeBase< RegionTraits< Function > >::BlockT
typename RegionTraits< Function > ::BlockT BlockT
Definition: RegionInfo.h:121
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::RegionTraits::BrokenT
typename FuncT_::UnknownRegionTypeError BrokenT
Definition: RegionInfo.h:81
llvm::Region
Definition: RegionInfo.h:889
llvm::RegionBase::getExitingBlock
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
Definition: RegionInfoImpl.h:204
raw_ostream.h
llvm::Region::operator==
bool operator==(const RegionNode &RN) const
Definition: RegionInfo.h:895
llvm::RegionInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:208
llvm::Region::~Region
~Region()
llvm::RegionBase::getExit
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339
llvm::RegionBase::elements
iterator_range< element_iterator > elements()
Definition: RegionInfo.h:651
llvm::RegionBase::replaceExit
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:62
llvm::RegionInfoPass::RegionInfoPass
RegionInfoPass()
Definition: RegionInfo.cpp:117
llvm::RegionInfoBase::updateRegionTree
void updateRegionTree(RegionInfoT &RI, TheRegionT *R)
Update refences to a RegionInfoT held by the RegionT managed here.
Definition: RegionInfo.h:731
llvm::RegionBase::getParent
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:364