Coverage Report

Created: 2018-09-25 17:16

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