Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- 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
// This file defines the LoopInfo class that is used to identify natural loops
11
// and determine the loop depth of various nodes of the CFG.  A natural loop
12
// has exactly one entry-point, which is called the header. Note that natural
13
// loops may actually be several loops that share the same header node.
14
//
15
// This analysis calculates the nesting structure of loops in a function.  For
16
// each natural loop identified, this analysis identifies natural loops
17
// contained entirely within the loop and the basic blocks the make up the loop.
18
//
19
// It can calculate on the fly various bits of information, for example:
20
//
21
//  * whether there is a preheader for the loop
22
//  * the number of back edges to the header
23
//  * whether or not a particular block branches out of the loop
24
//  * the successor blocks of the loop
25
//  * the loop depth
26
//  * etc...
27
//
28
// Note that this analysis specifically identifies *Loops* not cycles or SCCs
29
// in the CFG.  There can be strongly connected components in the CFG which
30
// this analysis will not recognize and that will not be represented by a Loop
31
// instance.  In particular, a Loop might be inside such a non-loop SCC, or a
32
// non-loop SCC might contain a sub-SCC which is a Loop.
33
//
34
//===----------------------------------------------------------------------===//
35
36
#ifndef LLVM_ANALYSIS_LOOPINFO_H
37
#define LLVM_ANALYSIS_LOOPINFO_H
38
39
#include "llvm/ADT/DenseMap.h"
40
#include "llvm/ADT/DenseSet.h"
41
#include "llvm/ADT/GraphTraits.h"
42
#include "llvm/ADT/SmallPtrSet.h"
43
#include "llvm/ADT/SmallVector.h"
44
#include "llvm/IR/CFG.h"
45
#include "llvm/IR/Instruction.h"
46
#include "llvm/IR/Instructions.h"
47
#include "llvm/IR/PassManager.h"
48
#include "llvm/Pass.h"
49
#include "llvm/Support/Allocator.h"
50
#include <algorithm>
51
#include <utility>
52
53
namespace llvm {
54
55
class DominatorTree;
56
class LoopInfo;
57
class Loop;
58
class MDNode;
59
class PHINode;
60
class raw_ostream;
61
template <class N, bool IsPostDom> class DominatorTreeBase;
62
template <class N, class M> class LoopInfoBase;
63
template <class N, class M> class LoopBase;
64
65
//===----------------------------------------------------------------------===//
66
/// Instances of this class are used to represent loops that are detected in the
67
/// flow graph.
68
///
69
template <class BlockT, class LoopT> class LoopBase {
70
  LoopT *ParentLoop;
71
  // Loops contained entirely within this one.
72
  std::vector<LoopT *> SubLoops;
73
74
  // The list of blocks in this loop. First entry is the header node.
75
  std::vector<BlockT *> Blocks;
76
77
  SmallPtrSet<const BlockT *, 8> DenseBlockSet;
78
79
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
80
  /// Indicator that this loop is no longer a valid loop.
81
  bool IsInvalid = false;
82
#endif
83
84
  LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
85
  const LoopBase<BlockT, LoopT> &
86
  operator=(const LoopBase<BlockT, LoopT> &) = delete;
87
88
public:
89
  /// Return the nesting level of this loop.  An outer-most loop has depth 1,
90
  /// for consistency with loop depth values used for basic blocks, where depth
91
  /// 0 is used for blocks not inside any loops.
92
3.09M
  unsigned getLoopDepth() const {
93
3.09M
    assert(!isInvalid() && "Loop not in a valid state!");
94
3.09M
    unsigned D = 1;
95
4.04M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
3.09M
         
CurLoop = CurLoop->ParentLoop951k
)
97
951k
      ++D;
98
3.09M
    return D;
99
3.09M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth() const
Line
Count
Source
92
1.76M
  unsigned getLoopDepth() const {
93
1.76M
    assert(!isInvalid() && "Loop not in a valid state!");
94
1.76M
    unsigned D = 1;
95
2.16M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
1.76M
         
CurLoop = CurLoop->ParentLoop390k
)
97
390k
      ++D;
98
1.76M
    return D;
99
1.76M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth() const
Line
Count
Source
92
1.32M
  unsigned getLoopDepth() const {
93
1.32M
    assert(!isInvalid() && "Loop not in a valid state!");
94
1.32M
    unsigned D = 1;
95
1.88M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
1.32M
         
CurLoop = CurLoop->ParentLoop560k
)
97
560k
      ++D;
98
1.32M
    return D;
99
1.32M
  }
100
156M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getHeader() const
Line
Count
Source
100
141M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getHeader() const
Line
Count
Source
100
15.0M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getHeader() const
Line
Count
Source
100
69
  BlockT *getHeader() const { return getBlocks().front(); }
101
42.9M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getParentLoop() const
Line
Count
Source
101
6.50M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getParentLoop() const
Line
Count
Source
101
36.4M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getParentLoop() const
Line
Count
Source
101
61
  LoopT *getParentLoop() const { return ParentLoop; }
102
103
  /// This is a raw interface for bypassing addChildLoop.
104
1.08M
  void setParentLoop(LoopT *L) {
105
1.08M
    assert(!isInvalid() && "Loop not in a valid state!");
106
1.08M
    ParentLoop = L;
107
1.08M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::setParentLoop(llvm::Loop*)
Line
Count
Source
104
867k
  void setParentLoop(LoopT *L) {
105
867k
    assert(!isInvalid() && "Loop not in a valid state!");
106
867k
    ParentLoop = L;
107
867k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::setParentLoop(llvm::MachineLoop*)
Line
Count
Source
104
221k
  void setParentLoop(LoopT *L) {
105
221k
    assert(!isInvalid() && "Loop not in a valid state!");
106
221k
    ParentLoop = L;
107
221k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::setParentLoop(llvm::VPLoop*)
Line
Count
Source
104
2
  void setParentLoop(LoopT *L) {
105
2
    assert(!isInvalid() && "Loop not in a valid state!");
106
2
    ParentLoop = L;
107
2
  }
108
109
  /// Return true if the specified loop is contained within in this loop.
110
29.3M
  bool contains(const LoopT *L) const {
111
29.3M
    assert(!isInvalid() && "Loop not in a valid state!");
112
29.3M
    if (L == this)
113
19.3M
      return true;
114
9.93M
    if (!L)
115
2.24M
      return false;
116
7.69M
    return contains(L->getParentLoop());
117
7.69M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::Loop const*) const
Line
Count
Source
110
28.0M
  bool contains(const LoopT *L) const {
111
28.0M
    assert(!isInvalid() && "Loop not in a valid state!");
112
28.0M
    if (L == this)
113
18.6M
      return true;
114
9.38M
    if (!L)
115
2.01M
      return false;
116
7.37M
    return contains(L->getParentLoop());
117
7.37M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains(llvm::MachineLoop const*) const
Line
Count
Source
110
1.29M
  bool contains(const LoopT *L) const {
111
1.29M
    assert(!isInvalid() && "Loop not in a valid state!");
112
1.29M
    if (L == this)
113
743k
      return true;
114
546k
    if (!L)
115
231k
      return false;
116
315k
    return contains(L->getParentLoop());
117
315k
  }
118
119
  /// Return true if the specified basic block is in this loop.
120
348M
  bool contains(const BlockT *BB) const {
121
348M
    assert(!isInvalid() && "Loop not in a valid state!");
122
348M
    return DenseBlockSet.count(BB);
123
348M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::BasicBlock const*) const
Line
Count
Source
120
332M
  bool contains(const BlockT *BB) const {
121
332M
    assert(!isInvalid() && "Loop not in a valid state!");
122
332M
    return DenseBlockSet.count(BB);
123
332M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains(llvm::MachineBasicBlock const*) const
Line
Count
Source
120
15.7M
  bool contains(const BlockT *BB) const {
121
15.7M
    assert(!isInvalid() && "Loop not in a valid state!");
122
15.7M
    return DenseBlockSet.count(BB);
123
15.7M
  }
124
125
  /// Return true if the specified instruction is in this loop.
126
46.6M
  template <class InstT> bool contains(const InstT *Inst) const {
127
46.6M
    return contains(Inst->getParent());
128
46.6M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::Instruction>(llvm::Instruction const*) const
Line
Count
Source
126
43.9M
  template <class InstT> bool contains(const InstT *Inst) const {
127
43.9M
    return contains(Inst->getParent());
128
43.9M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::PHINode>(llvm::PHINode const*) const
Line
Count
Source
126
465k
  template <class InstT> bool contains(const InstT *Inst) const {
127
465k
    return contains(Inst->getParent());
128
465k
  }
bool llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains<llvm::MachineInstr>(llvm::MachineInstr const*) const
Line
Count
Source
126
2.21M
  template <class InstT> bool contains(const InstT *Inst) const {
127
2.21M
    return contains(Inst->getParent());
128
2.21M
  }
129
130
  /// Return the loops contained entirely within this loop.
131
19.5M
  const std::vector<LoopT *> &getSubLoops() const {
132
19.5M
    assert(!isInvalid() && "Loop not in a valid state!");
133
19.5M
    return SubLoops;
134
19.5M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoops() const
Line
Count
Source
131
16.9M
  const std::vector<LoopT *> &getSubLoops() const {
132
16.9M
    assert(!isInvalid() && "Loop not in a valid state!");
133
16.9M
    return SubLoops;
134
16.9M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoops() const
Line
Count
Source
131
2.61M
  const std::vector<LoopT *> &getSubLoops() const {
132
2.61M
    assert(!isInvalid() && "Loop not in a valid state!");
133
2.61M
    return SubLoops;
134
2.61M
  }
135
13.3M
  std::vector<LoopT *> &getSubLoopsVector() {
136
13.3M
    assert(!isInvalid() && "Loop not in a valid state!");
137
13.3M
    return SubLoops;
138
13.3M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoopsVector()
Line
Count
Source
135
10.6M
  std::vector<LoopT *> &getSubLoopsVector() {
136
10.6M
    assert(!isInvalid() && "Loop not in a valid state!");
137
10.6M
    return SubLoops;
138
10.6M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoopsVector()
Line
Count
Source
135
2.77M
  std::vector<LoopT *> &getSubLoopsVector() {
136
2.77M
    assert(!isInvalid() && "Loop not in a valid state!");
137
2.77M
    return SubLoops;
138
2.77M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getSubLoopsVector()
Line
Count
Source
135
62
  std::vector<LoopT *> &getSubLoopsVector() {
136
62
    assert(!isInvalid() && "Loop not in a valid state!");
137
62
    return SubLoops;
138
62
  }
139
  typedef typename std::vector<LoopT *>::const_iterator iterator;
140
  typedef
141
      typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
142
6.29M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
142
4.99M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
142
1.29M
  iterator begin() const { return getSubLoops().begin(); }
143
6.43M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
143
5.14M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
143
1.29M
  iterator end() const { return getSubLoops().end(); }
144
1.57M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
144
1.57M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
145
1.57M
  reverse_iterator rend() const { return getSubLoops().rend(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
145
1.57M
  reverse_iterator rend() const { return getSubLoops().rend(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
146
1.51M
  bool empty() const { return getSubLoops().empty(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
146
1.51M
  bool empty() const { return getSubLoops().empty(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
Line
Count
Source
146
5.48k
  bool empty() const { return getSubLoops().empty(); }
147
148
  /// Get a list of the basic blocks which make up this loop.
149
209M
  ArrayRef<BlockT *> getBlocks() const {
150
209M
    assert(!isInvalid() && "Loop not in a valid state!");
151
209M
    return Blocks;
152
209M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocks() const
Line
Count
Source
149
192M
  ArrayRef<BlockT *> getBlocks() const {
150
192M
    assert(!isInvalid() && "Loop not in a valid state!");
151
192M
    return Blocks;
152
192M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocks() const
Line
Count
Source
149
16.8M
  ArrayRef<BlockT *> getBlocks() const {
150
16.8M
    assert(!isInvalid() && "Loop not in a valid state!");
151
16.8M
    return Blocks;
152
16.8M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocks() const
Line
Count
Source
149
73
  ArrayRef<BlockT *> getBlocks() const {
150
73
    assert(!isInvalid() && "Loop not in a valid state!");
151
73
    return Blocks;
152
73
  }
153
  typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
154
25.6M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_begin() const
Line
Count
Source
154
25.0M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_begin() const
Line
Count
Source
154
590k
  block_iterator block_begin() const { return getBlocks().begin(); }
155
25.4M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_end() const
Line
Count
Source
155
24.8M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_end() const
Line
Count
Source
155
590k
  block_iterator block_end() const { return getBlocks().end(); }
156
22.5M
  inline iterator_range<block_iterator> blocks() const {
157
22.5M
    assert(!isInvalid() && "Loop not in a valid state!");
158
22.5M
    return make_range(block_begin(), block_end());
159
22.5M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::blocks() const
Line
Count
Source
156
22.2M
  inline iterator_range<block_iterator> blocks() const {
157
22.2M
    assert(!isInvalid() && "Loop not in a valid state!");
158
22.2M
    return make_range(block_begin(), block_end());
159
22.2M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::blocks() const
Line
Count
Source
156
354k
  inline iterator_range<block_iterator> blocks() const {
157
354k
    assert(!isInvalid() && "Loop not in a valid state!");
158
354k
    return make_range(block_begin(), block_end());
159
354k
  }
160
161
  /// Get the number of blocks in this loop in constant time.
162
  /// Invalidate the loop, indicating that it is no longer a loop.
163
965k
  unsigned getNumBlocks() const {
164
965k
    assert(!isInvalid() && "Loop not in a valid state!");
165
965k
    return Blocks.size();
166
965k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getNumBlocks() const
Line
Count
Source
163
99.2k
  unsigned getNumBlocks() const {
164
99.2k
    assert(!isInvalid() && "Loop not in a valid state!");
165
99.2k
    return Blocks.size();
166
99.2k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBlocks() const
Line
Count
Source
163
866k
  unsigned getNumBlocks() const {
164
866k
    assert(!isInvalid() && "Loop not in a valid state!");
165
866k
    return Blocks.size();
166
866k
  }
167
168
  /// Return a direct, mutable handle to the blocks vector so that we can
169
  /// mutate it efficiently with techniques like `std::remove`.
170
1.08M
  std::vector<BlockT *> &getBlocksVector() {
171
1.08M
    assert(!isInvalid() && "Loop not in a valid state!");
172
1.08M
    return Blocks;
173
1.08M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksVector()
Line
Count
Source
170
868k
  std::vector<BlockT *> &getBlocksVector() {
171
868k
    assert(!isInvalid() && "Loop not in a valid state!");
172
868k
    return Blocks;
173
868k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksVector()
Line
Count
Source
170
221k
  std::vector<BlockT *> &getBlocksVector() {
171
221k
    assert(!isInvalid() && "Loop not in a valid state!");
172
221k
    return Blocks;
173
221k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocksVector()
Line
Count
Source
170
2
  std::vector<BlockT *> &getBlocksVector() {
171
2
    assert(!isInvalid() && "Loop not in a valid state!");
172
2
    return Blocks;
173
2
  }
174
  /// Return a direct, mutable handle to the blocks set so that we can
175
  /// mutate it efficiently.
176
586
  SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
177
586
    assert(!isInvalid() && "Loop not in a valid state!");
178
586
    return DenseBlockSet;
179
586
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksSet()
Line
Count
Source
176
586
  SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
177
586
    assert(!isInvalid() && "Loop not in a valid state!");
178
586
    return DenseBlockSet;
179
586
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksSet()
180
181
  /// Return a direct, immutable handle to the blocks set.
182
0
  const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
183
0
    assert(!isInvalid() && "Loop not in a valid state!");
184
0
    return DenseBlockSet;
185
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksSet() const
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksSet() const
186
187
  /// Return true if this loop is no longer valid.  The only valid use of this
188
  /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
189
  /// true by the destructor.  In other words, if this accessor returns true,
190
  /// the caller has already triggered UB by calling this accessor; and so it
191
  /// can only be called in a context where a return value of true indicates a
192
  /// programmer error.
193
0
  bool isInvalid() const {
194
0
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
195
0
    return IsInvalid;
196
0
#else
197
0
    return false;
198
0
#endif
199
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isInvalid() const
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isInvalid() const
200
201
  /// True if terminator in the block can branch to another block that is
202
  /// outside of the current loop.
203
4.74M
  bool isLoopExiting(const BlockT *BB) const {
204
4.74M
    assert(!isInvalid() && "Loop not in a valid state!");
205
7.10M
    for (const auto &Succ : children<const BlockT *>(BB)) {
206
7.10M
      if (!contains(Succ))
207
2.37M
        return true;
208
7.10M
    }
209
4.74M
    
return false2.36M
;
210
4.74M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopExiting(llvm::BasicBlock const*) const
Line
Count
Source
203
690k
  bool isLoopExiting(const BlockT *BB) const {
204
690k
    assert(!isInvalid() && "Loop not in a valid state!");
205
1.03M
    for (const auto &Succ : children<const BlockT *>(BB)) {
206
1.03M
      if (!contains(Succ))
207
540k
        return true;
208
1.03M
    }
209
690k
    
return false149k
;
210
690k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopExiting(llvm::MachineBasicBlock const*) const
Line
Count
Source
203
4.05M
  bool isLoopExiting(const BlockT *BB) const {
204
4.05M
    assert(!isInvalid() && "Loop not in a valid state!");
205
6.06M
    for (const auto &Succ : children<const BlockT *>(BB)) {
206
6.06M
      if (!contains(Succ))
207
1.83M
        return true;
208
6.06M
    }
209
4.05M
    
return false2.21M
;
210
4.05M
  }
211
212
  /// Returns true if \p BB is a loop-latch.
213
  /// A latch block is a block that contains a branch back to the header.
214
  /// This function is useful when there are multiple latches in a loop
215
  /// because \fn getLoopLatch will return nullptr in that case.
216
1.39k
  bool isLoopLatch(const BlockT *BB) const {
217
1.39k
    assert(!isInvalid() && "Loop not in a valid state!");
218
1.39k
    assert(contains(BB) && "block does not belong to the loop");
219
1.39k
220
1.39k
    BlockT *Header = getHeader();
221
1.39k
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
222
1.39k
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
223
1.39k
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
224
1.39k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopLatch(llvm::BasicBlock const*) const
Line
Count
Source
216
1.39k
  bool isLoopLatch(const BlockT *BB) const {
217
1.39k
    assert(!isInvalid() && "Loop not in a valid state!");
218
1.39k
    assert(contains(BB) && "block does not belong to the loop");
219
1.39k
220
1.39k
    BlockT *Header = getHeader();
221
1.39k
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
222
1.39k
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
223
1.39k
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
224
1.39k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopLatch(llvm::MachineBasicBlock const*) const
225
226
  /// Calculate the number of back edges to the loop header.
227
603k
  unsigned getNumBackEdges() const {
228
603k
    assert(!isInvalid() && "Loop not in a valid state!");
229
603k
    unsigned NumBackEdges = 0;
230
603k
    BlockT *H = getHeader();
231
603k
232
603k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
233
1.21M
      if (contains(Pred))
234
615k
        ++NumBackEdges;
235
603k
236
603k
    return NumBackEdges;
237
603k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBackEdges() const
Line
Count
Source
227
603k
  unsigned getNumBackEdges() const {
228
603k
    assert(!isInvalid() && "Loop not in a valid state!");
229
603k
    unsigned NumBackEdges = 0;
230
603k
    BlockT *H = getHeader();
231
603k
232
603k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
233
1.21M
      if (contains(Pred))
234
615k
        ++NumBackEdges;
235
603k
236
603k
    return NumBackEdges;
237
603k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getNumBackEdges() const
238
239
  //===--------------------------------------------------------------------===//
240
  // APIs for simple analysis of the loop.
241
  //
242
  // Note that all of these methods can fail on general loops (ie, there may not
243
  // be a preheader, etc).  For best success, the loop simplification and
244
  // induction variable canonicalization pass should be used to normalize loops
245
  // for easy analysis.  These methods assume canonical loops.
246
247
  /// Return all blocks inside the loop that have successors outside of the
248
  /// loop. These are the blocks _inside of the current loop_ which branch out.
249
  /// The returned list is always unique.
250
  void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
251
252
  /// If getExitingBlocks would return exactly one block, return that block.
253
  /// Otherwise return null.
254
  BlockT *getExitingBlock() const;
255
256
  /// Return all of the successor blocks of this loop. These are the blocks
257
  /// _outside of the current loop_ which are branched to.
258
  void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
259
260
  /// If getExitBlocks would return exactly one block, return that block.
261
  /// Otherwise return null.
262
  BlockT *getExitBlock() const;
263
264
  /// Return true if no exit block for the loop has a predecessor that is
265
  /// outside the loop.
266
  bool hasDedicatedExits() const;
267
268
  /// Return all unique successor blocks of this loop.
269
  /// These are the blocks _outside of the current loop_ which are branched to.
270
  /// This assumes that loop exits are in canonical form, i.e. all exits are
271
  /// dedicated exits.
272
  void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
273
274
  /// If getUniqueExitBlocks would return exactly one block, return that block.
275
  /// Otherwise return null.
276
  BlockT *getUniqueExitBlock() const;
277
278
  /// Edge type.
279
  typedef std::pair<const BlockT *, const BlockT *> Edge;
280
281
  /// Return all pairs of (_inside_block_,_outside_block_).
282
  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
283
284
  /// If there is a preheader for this loop, return it. A loop has a preheader
285
  /// if there is only one edge to the header of the loop from outside of the
286
  /// loop. If this is the case, the block branching to the header of the loop
287
  /// is the preheader node.
288
  ///
289
  /// This method returns null if there is no preheader for the loop.
290
  BlockT *getLoopPreheader() const;
291
292
  /// If the given loop's header has exactly one unique predecessor outside the
293
  /// loop, return it. Otherwise return null.
294
  ///  This is less strict that the loop "preheader" concept, which requires
295
  /// the predecessor to have exactly one successor.
296
  BlockT *getLoopPredecessor() const;
297
298
  /// If there is a single latch block for this loop, return it.
299
  /// A latch block is a block that contains a branch back to the header.
300
  BlockT *getLoopLatch() const;
301
302
  /// Return all loop latch blocks of this loop. A latch block is a block that
303
  /// contains a branch back to the header.
304
3.04M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
305
3.04M
    assert(!isInvalid() && "Loop not in a valid state!");
306
3.04M
    BlockT *H = getHeader();
307
3.04M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
308
6.09M
      if (contains(Pred))
309
3.04M
        LoopLatches.push_back(Pred);
310
3.04M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatches(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
304
3.04M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
305
3.04M
    assert(!isInvalid() && "Loop not in a valid state!");
306
3.04M
    BlockT *H = getHeader();
307
3.04M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
308
6.09M
      if (contains(Pred))
309
3.04M
        LoopLatches.push_back(Pred);
310
3.04M
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatches(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
311
312
  //===--------------------------------------------------------------------===//
313
  // APIs for updating loop information after changing the CFG
314
  //
315
316
  /// This method is used by other analyses to update loop information.
317
  /// NewBB is set to be a new member of the current loop.
318
  /// Because of this, it is added as a member of all parent loops, and is added
319
  /// to the specified LoopInfo object as being in the current basic block.  It
320
  /// is not valid to replace the loop header with this method.
321
  void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
322
323
  /// This is used when splitting loops up. It replaces the OldChild entry in
324
  /// our children list with NewChild, and updates the parent pointer of
325
  /// OldChild to be null and the NewChild to be this loop.
326
  /// This updates the loop depth of the new child.
327
  void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
328
329
  /// Add the specified loop to be a child of this loop.
330
  /// This updates the loop depth of the new child.
331
26.2k
  void addChildLoop(LoopT *NewChild) {
332
26.2k
    assert(!isInvalid() && "Loop not in a valid state!");
333
26.2k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
334
26.2k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
335
26.2k
    SubLoops.push_back(NewChild);
336
26.2k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addChildLoop(llvm::Loop*)
Line
Count
Source
331
26.2k
  void addChildLoop(LoopT *NewChild) {
332
26.2k
    assert(!isInvalid() && "Loop not in a valid state!");
333
26.2k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
334
26.2k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
335
26.2k
    SubLoops.push_back(NewChild);
336
26.2k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addChildLoop(llvm::MachineLoop*)
337
338
  /// This removes the specified child from being a subloop of this loop. The
339
  /// loop is not deleted, as it will presumably be inserted into another loop.
340
9.74k
  LoopT *removeChildLoop(iterator I) {
341
9.74k
    assert(!isInvalid() && "Loop not in a valid state!");
342
9.74k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
343
9.74k
    LoopT *Child = *I;
344
9.74k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
345
9.74k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
346
9.74k
    Child->ParentLoop = nullptr;
347
9.74k
    return Child;
348
9.74k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
340
9.74k
  LoopT *removeChildLoop(iterator I) {
341
9.74k
    assert(!isInvalid() && "Loop not in a valid state!");
342
9.74k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
343
9.74k
    LoopT *Child = *I;
344
9.74k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
345
9.74k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
346
9.74k
    Child->ParentLoop = nullptr;
347
9.74k
    return Child;
348
9.74k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeChildLoop(std::__1::__wrap_iter<llvm::MachineLoop* const*>)
349
350
  /// This removes the specified child from being a subloop of this loop. The
351
  /// loop is not deleted, as it will presumably be inserted into another loop.
352
39
  LoopT *removeChildLoop(LoopT *Child) {
353
39
    return removeChildLoop(llvm::find(*this, Child));
354
39
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(llvm::Loop*)
Line
Count
Source
352
39
  LoopT *removeChildLoop(LoopT *Child) {
353
39
    return removeChildLoop(llvm::find(*this, Child));
354
39
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeChildLoop(llvm::MachineLoop*)
355
356
  /// This adds a basic block directly to the basic block list.
357
  /// This should only be used by transformations that create new loops.  Other
358
  /// transformations should use addBasicBlockToLoop.
359
14.7M
  void addBlockEntry(BlockT *BB) {
360
14.7M
    assert(!isInvalid() && "Loop not in a valid state!");
361
14.7M
    Blocks.push_back(BB);
362
14.7M
    DenseBlockSet.insert(BB);
363
14.7M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBlockEntry(llvm::BasicBlock*)
Line
Count
Source
359
11.8M
  void addBlockEntry(BlockT *BB) {
360
11.8M
    assert(!isInvalid() && "Loop not in a valid state!");
361
11.8M
    Blocks.push_back(BB);
362
11.8M
    DenseBlockSet.insert(BB);
363
11.8M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBlockEntry(llvm::MachineBasicBlock*)
Line
Count
Source
359
2.90M
  void addBlockEntry(BlockT *BB) {
360
2.90M
    assert(!isInvalid() && "Loop not in a valid state!");
361
2.90M
    Blocks.push_back(BB);
362
2.90M
    DenseBlockSet.insert(BB);
363
2.90M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::addBlockEntry(llvm::VPBlockBase*)
Line
Count
Source
359
14
  void addBlockEntry(BlockT *BB) {
360
14
    assert(!isInvalid() && "Loop not in a valid state!");
361
14
    Blocks.push_back(BB);
362
14
    DenseBlockSet.insert(BB);
363
14
  }
364
365
  /// interface to reverse Blocks[from, end of loop] in this loop
366
4.10M
  void reverseBlock(unsigned from) {
367
4.10M
    assert(!isInvalid() && "Loop not in a valid state!");
368
4.10M
    std::reverse(Blocks.begin() + from, Blocks.end());
369
4.10M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reverseBlock(unsigned int)
Line
Count
Source
366
3.24M
  void reverseBlock(unsigned from) {
367
3.24M
    assert(!isInvalid() && "Loop not in a valid state!");
368
3.24M
    std::reverse(Blocks.begin() + from, Blocks.end());
369
3.24M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reverseBlock(unsigned int)
Line
Count
Source
366
851k
  void reverseBlock(unsigned from) {
367
851k
    assert(!isInvalid() && "Loop not in a valid state!");
368
851k
    std::reverse(Blocks.begin() + from, Blocks.end());
369
851k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reverseBlock(unsigned int)
Line
Count
Source
366
20
  void reverseBlock(unsigned from) {
367
20
    assert(!isInvalid() && "Loop not in a valid state!");
368
20
    std::reverse(Blocks.begin() + from, Blocks.end());
369
20
  }
370
371
  /// interface to do reserve() for Blocks
372
4.10M
  void reserveBlocks(unsigned size) {
373
4.10M
    assert(!isInvalid() && "Loop not in a valid state!");
374
4.10M
    Blocks.reserve(size);
375
4.10M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reserveBlocks(unsigned int)
Line
Count
Source
372
3.24M
  void reserveBlocks(unsigned size) {
373
3.24M
    assert(!isInvalid() && "Loop not in a valid state!");
374
3.24M
    Blocks.reserve(size);
375
3.24M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reserveBlocks(unsigned int)
Line
Count
Source
372
851k
  void reserveBlocks(unsigned size) {
373
851k
    assert(!isInvalid() && "Loop not in a valid state!");
374
851k
    Blocks.reserve(size);
375
851k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reserveBlocks(unsigned int)
Line
Count
Source
372
20
  void reserveBlocks(unsigned size) {
373
20
    assert(!isInvalid() && "Loop not in a valid state!");
374
20
    Blocks.reserve(size);
375
20
  }
376
377
  /// This method is used to move BB (which must be part of this loop) to be the
378
  /// loop header of the loop (the block that dominates all others).
379
40.5k
  void moveToHeader(BlockT *BB) {
380
40.5k
    assert(!isInvalid() && "Loop not in a valid state!");
381
40.5k
    if (Blocks[0] == BB)
382
0
      return;
383
132k
    
for (unsigned i = 0;; 40.5k
++i92.3k
) {
384
132k
      assert(i != Blocks.size() && "Loop does not contain BB!");
385
132k
      if (Blocks[i] == BB) {
386
40.5k
        Blocks[i] = Blocks[0];
387
40.5k
        Blocks[0] = BB;
388
40.5k
        return;
389
40.5k
      }
390
132k
    }
391
40.5k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::moveToHeader(llvm::BasicBlock*)
Line
Count
Source
379
40.5k
  void moveToHeader(BlockT *BB) {
380
40.5k
    assert(!isInvalid() && "Loop not in a valid state!");
381
40.5k
    if (Blocks[0] == BB)
382
0
      return;
383
132k
    
for (unsigned i = 0;; 40.5k
++i92.3k
) {
384
132k
      assert(i != Blocks.size() && "Loop does not contain BB!");
385
132k
      if (Blocks[i] == BB) {
386
40.5k
        Blocks[i] = Blocks[0];
387
40.5k
        Blocks[0] = BB;
388
40.5k
        return;
389
40.5k
      }
390
132k
    }
391
40.5k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::moveToHeader(llvm::MachineBasicBlock*)
392
393
  /// This removes the specified basic block from the current loop, updating the
394
  /// Blocks as appropriate. This does not update the mapping in the LoopInfo
395
  /// class.
396
472k
  void removeBlockFromLoop(BlockT *BB) {
397
472k
    assert(!isInvalid() && "Loop not in a valid state!");
398
472k
    auto I = find(Blocks, BB);
399
472k
    assert(I != Blocks.end() && "N is not in this list!");
400
472k
    Blocks.erase(I);
401
472k
402
472k
    DenseBlockSet.erase(BB);
403
472k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlockFromLoop(llvm::MachineBasicBlock*)
Line
Count
Source
396
42.5k
  void removeBlockFromLoop(BlockT *BB) {
397
42.5k
    assert(!isInvalid() && "Loop not in a valid state!");
398
42.5k
    auto I = find(Blocks, BB);
399
42.5k
    assert(I != Blocks.end() && "N is not in this list!");
400
42.5k
    Blocks.erase(I);
401
42.5k
402
42.5k
    DenseBlockSet.erase(BB);
403
42.5k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeBlockFromLoop(llvm::BasicBlock*)
Line
Count
Source
396
429k
  void removeBlockFromLoop(BlockT *BB) {
397
429k
    assert(!isInvalid() && "Loop not in a valid state!");
398
429k
    auto I = find(Blocks, BB);
399
429k
    assert(I != Blocks.end() && "N is not in this list!");
400
429k
    Blocks.erase(I);
401
429k
402
429k
    DenseBlockSet.erase(BB);
403
429k
  }
404
405
  /// Verify loop structure
406
  void verifyLoop() const;
407
408
  /// Verify loop structure of this loop and all nested loops.
409
  void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
410
411
  /// Print loop with all the BBs inside it.
412
  void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const;
413
414
protected:
415
  friend class LoopInfoBase<BlockT, LoopT>;
416
417
  /// This creates an empty loop.
418
42.9k
  LoopBase() : ParentLoop(nullptr) {}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase()
Line
Count
Source
418
42.9k
  LoopBase() : ParentLoop(nullptr) {}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase()
419
420
4.10M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
4.10M
    Blocks.push_back(BB);
422
4.10M
    DenseBlockSet.insert(BB);
423
4.10M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase(llvm::BasicBlock*)
Line
Count
Source
420
3.24M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
3.24M
    Blocks.push_back(BB);
422
3.24M
    DenseBlockSet.insert(BB);
423
3.24M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase(llvm::MachineBasicBlock*)
Line
Count
Source
420
851k
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
851k
    Blocks.push_back(BB);
422
851k
    DenseBlockSet.insert(BB);
423
851k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::LoopBase(llvm::VPBlockBase*)
Line
Count
Source
420
20
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
20
    Blocks.push_back(BB);
422
20
    DenseBlockSet.insert(BB);
423
20
  }
424
425
  // Since loop passes like SCEV are allowed to key analysis results off of
426
  // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
427
  // This means loop passes should not be `delete` ing `Loop` objects directly
428
  // (and risk a later `Loop` allocation re-using the address of a previous one)
429
  // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
430
  // pointer till the end of the lifetime of the `LoopInfo` object.
431
  //
432
  // To make it easier to follow this rule, we mark the destructor as
433
  // non-public.
434
4.14M
  ~LoopBase() {
435
4.14M
    for (auto *SubLoop : SubLoops)
436
1.10M
      SubLoop->~LoopT();
437
4.14M
438
4.14M
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
4.14M
    IsInvalid = true;
440
4.14M
#endif
441
4.14M
    SubLoops.clear();
442
4.14M
    Blocks.clear();
443
4.14M
    DenseBlockSet.clear();
444
4.14M
    ParentLoop = nullptr;
445
4.14M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::~LoopBase()
Line
Count
Source
434
3.29M
  ~LoopBase() {
435
3.29M
    for (auto *SubLoop : SubLoops)
436
884k
      SubLoop->~LoopT();
437
3.29M
438
3.29M
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
3.29M
    IsInvalid = true;
440
3.29M
#endif
441
3.29M
    SubLoops.clear();
442
3.29M
    Blocks.clear();
443
3.29M
    DenseBlockSet.clear();
444
3.29M
    ParentLoop = nullptr;
445
3.29M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopBase()
Line
Count
Source
434
851k
  ~LoopBase() {
435
851k
    for (auto *SubLoop : SubLoops)
436
221k
      SubLoop->~LoopT();
437
851k
438
851k
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
851k
    IsInvalid = true;
440
851k
#endif
441
851k
    SubLoops.clear();
442
851k
    Blocks.clear();
443
851k
    DenseBlockSet.clear();
444
851k
    ParentLoop = nullptr;
445
851k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopBase()
Line
Count
Source
434
20
  ~LoopBase() {
435
20
    for (auto *SubLoop : SubLoops)
436
2
      SubLoop->~LoopT();
437
20
438
20
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
20
    IsInvalid = true;
440
20
#endif
441
20
    SubLoops.clear();
442
20
    Blocks.clear();
443
20
    DenseBlockSet.clear();
444
20
    ParentLoop = nullptr;
445
20
  }
446
};
447
448
template <class BlockT, class LoopT>
449
449
raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
450
449
  Loop.print(OS);
451
449
  return OS;
452
449
}
453
454
// Implementation in LoopInfoImpl.h
455
extern template class LoopBase<BasicBlock, Loop>;
456
457
/// Represents a single loop in the control flow graph.  Note that not all SCCs
458
/// in the CFG are necessarily loops.
459
class Loop : public LoopBase<BasicBlock, Loop> {
460
public:
461
  /// A range representing the start and end location of a loop.
462
  class LocRange {
463
    DebugLoc Start;
464
    DebugLoc End;
465
466
  public:
467
0
    LocRange() {}
468
227k
    LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {}
469
    LocRange(DebugLoc Start, DebugLoc End)
470
18.3k
        : Start(std::move(Start)), End(std::move(End)) {}
471
472
245k
    const DebugLoc &getStart() const { return Start; }
473
0
    const DebugLoc &getEnd() const { return End; }
474
475
    /// Check for null.
476
    ///
477
0
    explicit operator bool() const { return Start && End; }
478
  };
479
480
  /// Return true if the specified value is loop invariant.
481
  bool isLoopInvariant(const Value *V) const;
482
483
  /// Return true if all the operands of the specified instruction are loop
484
  /// invariant.
485
  bool hasLoopInvariantOperands(const Instruction *I) const;
486
487
  /// If the given value is an instruction inside of the loop and it can be
488
  /// hoisted, do so to make it trivially loop-invariant.
489
  /// Return true if the value after any hoisting is loop invariant. This
490
  /// function can be used as a slightly more aggressive replacement for
491
  /// isLoopInvariant.
492
  ///
493
  /// If InsertPt is specified, it is the point to hoist instructions to.
494
  /// If null, the terminator of the loop preheader is used.
495
  bool makeLoopInvariant(Value *V, bool &Changed,
496
                         Instruction *InsertPt = nullptr) const;
497
498
  /// If the given instruction is inside of the loop and it can be hoisted, do
499
  /// so to make it trivially loop-invariant.
500
  /// Return true if the instruction after any hoisting is loop invariant. This
501
  /// function can be used as a slightly more aggressive replacement for
502
  /// isLoopInvariant.
503
  ///
504
  /// If InsertPt is specified, it is the point to hoist instructions to.
505
  /// If null, the terminator of the loop preheader is used.
506
  ///
507
  bool makeLoopInvariant(Instruction *I, bool &Changed,
508
                         Instruction *InsertPt = nullptr) const;
509
510
  /// Check to see if the loop has a canonical induction variable: an integer
511
  /// recurrence that starts at 0 and increments by one each time through the
512
  /// loop. If so, return the phi node that corresponds to it.
513
  ///
514
  /// The IndVarSimplify pass transforms loops to have a canonical induction
515
  /// variable.
516
  ///
517
  PHINode *getCanonicalInductionVariable() const;
518
519
  /// Return true if the Loop is in LCSSA form.
520
  bool isLCSSAForm(DominatorTree &DT) const;
521
522
  /// Return true if this Loop and all inner subloops are in LCSSA form.
523
  bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
524
525
  /// Return true if the Loop is in the form that the LoopSimplify form
526
  /// transforms loops to, which is sometimes called normal form.
527
  bool isLoopSimplifyForm() const;
528
529
  /// Return true if the loop body is safe to clone in practice.
530
  bool isSafeToClone() const;
531
532
  /// Returns true if the loop is annotated parallel.
533
  ///
534
  /// A parallel loop can be assumed to not contain any dependencies between
535
  /// iterations by the compiler. That is, any loop-carried dependency checking
536
  /// can be skipped completely when parallelizing the loop on the target
537
  /// machine. Thus, if the parallel loop information originates from the
538
  /// programmer, e.g. via the OpenMP parallel for pragma, it is the
539
  /// programmer's responsibility to ensure there are no loop-carried
540
  /// dependencies. The final execution order of the instructions across
541
  /// iterations is not guaranteed, thus, the end result might or might not
542
  /// implement actual concurrent execution of instructions across multiple
543
  /// iterations.
544
  bool isAnnotatedParallel() const;
545
546
  /// Return the llvm.loop loop id metadata node for this loop if it is present.
547
  ///
548
  /// If this loop contains the same llvm.loop metadata on each branch to the
549
  /// header then the node is returned. If any latch instruction does not
550
  /// contain llvm.loop or if multiple latches contain different nodes then
551
  /// 0 is returned.
552
  MDNode *getLoopID() const;
553
  /// Set the llvm.loop loop id metadata for this loop.
554
  ///
555
  /// The LoopID metadata node will be added to each terminator instruction in
556
  /// the loop that branches to the loop header.
557
  ///
558
  /// The LoopID metadata node should have one or more operands and the first
559
  /// operand should be the node itself.
560
  void setLoopID(MDNode *LoopID) const;
561
562
  /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
563
  ///
564
  /// Remove existing unroll metadata and add unroll disable metadata to
565
  /// indicate the loop has already been unrolled.  This prevents a loop
566
  /// from being unrolled more than is directed by a pragma if the loop
567
  /// unrolling pass is run more than once (which it generally is).
568
  void setLoopAlreadyUnrolled();
569
570
  void dump() const;
571
  void dumpVerbose() const;
572
573
  /// Return the debug location of the start of this loop.
574
  /// This looks for a BB terminating instruction with a known debug
575
  /// location by looking at the preheader and header blocks. If it
576
  /// cannot find a terminating instruction with location information,
577
  /// it returns an unknown location.
578
  DebugLoc getStartLoc() const;
579
580
  /// Return the source code span of the loop.
581
  LocRange getLocRange() const;
582
583
1.04M
  StringRef getName() const {
584
1.04M
    if (BasicBlock *Header = getHeader())
585
1.04M
      if (Header->hasName())
586
453k
        return Header->getName();
587
588k
    return "<unnamed loop>";
588
588k
  }
589
590
private:
591
42.9k
  Loop() = default;
592
593
  friend class LoopInfoBase<BasicBlock, Loop>;
594
  friend class LoopBase<BasicBlock, Loop>;
595
3.24M
  explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
596
3.29M
  ~Loop() = default;
597
};
598
599
//===----------------------------------------------------------------------===//
600
/// This class builds and contains all of the top-level loop
601
/// structures in the specified function.
602
///
603
604
template <class BlockT, class LoopT> class LoopInfoBase {
605
  // BBMap - Mapping of basic blocks to the inner most loop they occur in
606
  DenseMap<const BlockT *, LoopT *> BBMap;
607
  std::vector<LoopT *> TopLevelLoops;
608
  BumpPtrAllocator LoopAllocator;
609
610
  friend class LoopBase<BlockT, LoopT>;
611
  friend class LoopInfo;
612
613
  void operator=(const LoopInfoBase &) = delete;
614
  LoopInfoBase(const LoopInfoBase &) = delete;
615
616
public:
617
725k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase()
Line
Count
Source
617
337k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopInfoBase()
Line
Count
Source
617
350k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::LoopInfoBase()
Line
Count
Source
617
38.0k
  LoopInfoBase() {}
618
728k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::~LoopInfoBase()
Line
Count
Source
618
340k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopInfoBase()
Line
Count
Source
618
349k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopInfoBase()
Line
Count
Source
618
38.0k
  ~LoopInfoBase() { releaseMemory(); }
619
620
  LoopInfoBase(LoopInfoBase &&Arg)
621
      : BBMap(std::move(Arg.BBMap)),
622
        TopLevelLoops(std::move(Arg.TopLevelLoops)),
623
3.84k
        LoopAllocator(std::move(Arg.LoopAllocator)) {
624
3.84k
    // We have to clear the arguments top level loops as we've taken ownership.
625
3.84k
    Arg.TopLevelLoops.clear();
626
3.84k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&&)
Line
Count
Source
623
3.84k
        LoopAllocator(std::move(Arg.LoopAllocator)) {
624
3.84k
    // We have to clear the arguments top level loops as we've taken ownership.
625
3.84k
    Arg.TopLevelLoops.clear();
626
3.84k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopInfoBase(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&&)
627
0
  LoopInfoBase &operator=(LoopInfoBase &&RHS) {
628
0
    BBMap = std::move(RHS.BBMap);
629
0
630
0
    for (auto *L : TopLevelLoops)
631
0
      L->~LoopT();
632
0
633
0
    TopLevelLoops = std::move(RHS.TopLevelLoops);
634
0
    LoopAllocator = std::move(RHS.LoopAllocator);
635
0
    RHS.TopLevelLoops.clear();
636
0
    return *this;
637
0
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::operator=(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&&)
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::operator=(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&&)
638
639
18.7M
  void releaseMemory() {
640
18.7M
    BBMap.clear();
641
18.7M
642
18.7M
    for (auto *L : TopLevelLoops)
643
3.01M
      L->~LoopT();
644
18.7M
    TopLevelLoops.clear();
645
18.7M
    LoopAllocator.Reset();
646
18.7M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::releaseMemory()
Line
Count
Source
639
14.3M
  void releaseMemory() {
640
14.3M
    BBMap.clear();
641
14.3M
642
14.3M
    for (auto *L : TopLevelLoops)
643
2.38M
      L->~LoopT();
644
14.3M
    TopLevelLoops.clear();
645
14.3M
    LoopAllocator.Reset();
646
14.3M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::releaseMemory()
Line
Count
Source
639
4.42M
  void releaseMemory() {
640
4.42M
    BBMap.clear();
641
4.42M
642
4.42M
    for (auto *L : TopLevelLoops)
643
630k
      L->~LoopT();
644
4.42M
    TopLevelLoops.clear();
645
4.42M
    LoopAllocator.Reset();
646
4.42M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::releaseMemory()
Line
Count
Source
639
38.0k
  void releaseMemory() {
640
38.0k
    BBMap.clear();
641
38.0k
642
38.0k
    for (auto *L : TopLevelLoops)
643
18
      L->~LoopT();
644
38.0k
    TopLevelLoops.clear();
645
38.0k
    LoopAllocator.Reset();
646
38.0k
  }
647
648
4.14M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
4.14M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
4.14M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
4.14M
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<llvm::BasicBlock*&>(llvm::BasicBlock*&&&)
Line
Count
Source
648
3.24M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
3.24M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
3.24M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
3.24M
  }
llvm::MachineLoop* llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::AllocateLoop<llvm::MachineBasicBlock*&>(llvm::MachineBasicBlock*&&&)
Line
Count
Source
648
851k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
851k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
851k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
851k
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<>()
Line
Count
Source
648
42.9k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
42.9k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
42.9k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
42.9k
  }
llvm::VPLoop* llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::AllocateLoop<llvm::VPBlockBase*&>(llvm::VPBlockBase*&&&)
Line
Count
Source
648
20
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
20
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
20
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
20
  }
652
653
  /// iterator/begin/end - The interface to the top-level loops in the current
654
  /// function.
655
  ///
656
  typedef typename std::vector<LoopT *>::const_iterator iterator;
657
  typedef
658
      typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
659
10.0M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
659
8.08M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
659
2.00M
  iterator begin() const { return TopLevelLoops.begin(); }
660
10.0M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
660
8.04M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
660
2.00M
  iterator end() const { return TopLevelLoops.end(); }
661
3.01M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
661
3.01M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
662
3.01M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
662
3.01M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
663
4.20M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
663
2.27M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
Line
Count
Source
663
1.92M
  bool empty() const { return TopLevelLoops.empty(); }
664
665
  /// Return all of the loops in the function in preorder across the loop
666
  /// nests, with siblings in forward program order.
667
  ///
668
  /// Note that because loops form a forest of trees, preorder is equivalent to
669
  /// reverse postorder.
670
  SmallVector<LoopT *, 4> getLoopsInPreorder();
671
672
  /// Return all of the loops in the function in preorder across the loop
673
  /// nests, with siblings in *reverse* program order.
674
  ///
675
  /// Note that because loops form a forest of trees, preorder is equivalent to
676
  /// reverse postorder.
677
  ///
678
  /// Also note that this is *not* a reverse preorder. Only the siblings are in
679
  /// reverse program order.
680
  SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();
681
682
  /// Return the inner most loop that BB lives in. If a basic block is in no
683
  /// loop (for example the entry node), null is returned.
684
202M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopFor(llvm::BasicBlock const*) const
Line
Count
Source
684
140M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopFor(llvm::MachineBasicBlock const*) const
Line
Count
Source
684
61.2M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::getLoopFor(llvm::VPBlockBase const*) const
Line
Count
Source
684
115
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
685
686
  /// Same as getLoopFor.
687
2.04M
  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::operator[](llvm::BasicBlock const*) const
Line
Count
Source
687
2.04M
  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::operator[](llvm::MachineBasicBlock const*) const
688
689
  /// Return the loop nesting level of the specified block. A depth of 0 means
690
  /// the block is not inside any loop.
691
5.87M
  unsigned getLoopDepth(const BlockT *BB) const {
692
5.87M
    const LoopT *L = getLoopFor(BB);
693
5.87M
    return L ? 
L->getLoopDepth()1.94M
:
03.92M
;
694
5.87M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth(llvm::BasicBlock const*) const
Line
Count
Source
691
825k
  unsigned getLoopDepth(const BlockT *BB) const {
692
825k
    const LoopT *L = getLoopFor(BB);
693
825k
    return L ? 
L->getLoopDepth()725k
:
0100k
;
694
825k
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth(llvm::MachineBasicBlock const*) const
Line
Count
Source
691
5.05M
  unsigned getLoopDepth(const BlockT *BB) const {
692
5.05M
    const LoopT *L = getLoopFor(BB);
693
5.05M
    return L ? 
L->getLoopDepth()1.22M
:
03.82M
;
694
5.05M
  }
695
696
  // True if the block is a loop header node
697
3.51M
  bool isLoopHeader(const BlockT *BB) const {
698
3.51M
    const LoopT *L = getLoopFor(BB);
699
3.51M
    return L && 
L->getHeader() == BB947k
;
700
3.51M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopHeader(llvm::MachineBasicBlock const*) const
Line
Count
Source
697
3.35M
  bool isLoopHeader(const BlockT *BB) const {
698
3.35M
    const LoopT *L = getLoopFor(BB);
699
3.35M
    return L && 
L->getHeader() == BB818k
;
700
3.35M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::isLoopHeader(llvm::BasicBlock const*) const
Line
Count
Source
697
158k
  bool isLoopHeader(const BlockT *BB) const {
698
158k
    const LoopT *L = getLoopFor(BB);
699
158k
    return L && 
L->getHeader() == BB129k
;
700
158k
  }
701
702
  /// This removes the specified top-level loop from this loop info object.
703
  /// The loop is not deleted, as it will presumably be inserted into
704
  /// another loop.
705
19.8k
  LoopT *removeLoop(iterator I) {
706
19.8k
    assert(I != end() && "Cannot remove end iterator!");
707
19.8k
    LoopT *L = *I;
708
19.8k
    assert(!L->getParentLoop() && "Not a top-level loop!");
709
19.8k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
710
19.8k
    return L;
711
19.8k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
705
19.8k
  LoopT *removeLoop(iterator I) {
706
19.8k
    assert(I != end() && "Cannot remove end iterator!");
707
19.8k
    LoopT *L = *I;
708
19.8k
    assert(!L->getParentLoop() && "Not a top-level loop!");
709
19.8k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
710
19.8k
    return L;
711
19.8k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeLoop(std::__1::__wrap_iter<llvm::MachineLoop* const*>)
712
713
  /// Change the top-level loop that contains BB to the specified loop.
714
  /// This should be used by transformations that restructure the loop hierarchy
715
  /// tree.
716
13.3M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
13.3M
    if (!L) {
718
79.0k
      BBMap.erase(BB);
719
79.0k
      return;
720
79.0k
    }
721
13.2M
    BBMap[BB] = L;
722
13.2M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::changeLoopFor(llvm::MachineBasicBlock*, llvm::MachineLoop*)
Line
Count
Source
716
2.73M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
2.73M
    if (!L) {
718
16
      BBMap.erase(BB);
719
16
      return;
720
16
    }
721
2.73M
    BBMap[BB] = L;
722
2.73M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeLoopFor(llvm::BasicBlock*, llvm::Loop*)
Line
Count
Source
716
10.6M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
10.6M
    if (!L) {
718
79.0k
      BBMap.erase(BB);
719
79.0k
      return;
720
79.0k
    }
721
10.5M
    BBMap[BB] = L;
722
10.5M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::changeLoopFor(llvm::VPBlockBase*, llvm::VPLoop*)
Line
Count
Source
716
32
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
32
    if (!L) {
718
0
      BBMap.erase(BB);
719
0
      return;
720
0
    }
721
32
    BBMap[BB] = L;
722
32
  }
723
724
  /// Replace the specified loop in the top-level loops list with the indicated
725
  /// loop.
726
291
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
727
291
    auto I = find(TopLevelLoops, OldLoop);
728
291
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
729
291
    *I = NewLoop;
730
291
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
731
291
           "Loops already embedded into a subloop!");
732
291
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeTopLevelLoop(llvm::Loop*, llvm::Loop*)
Line
Count
Source
726
291
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
727
291
    auto I = find(TopLevelLoops, OldLoop);
728
291
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
729
291
    *I = NewLoop;
730
291
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
731
291
           "Loops already embedded into a subloop!");
732
291
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::changeTopLevelLoop(llvm::MachineLoop*, llvm::MachineLoop*)
733
734
  /// This adds the specified loop to the collection of top-level loops.
735
3.03M
  void addTopLevelLoop(LoopT *New) {
736
3.03M
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
3.03M
    TopLevelLoops.push_back(New);
738
3.03M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::addTopLevelLoop(llvm::Loop*)
Line
Count
Source
735
2.40M
  void addTopLevelLoop(LoopT *New) {
736
2.40M
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
2.40M
    TopLevelLoops.push_back(New);
738
2.40M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addTopLevelLoop(llvm::MachineLoop*)
Line
Count
Source
735
630k
  void addTopLevelLoop(LoopT *New) {
736
630k
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
630k
    TopLevelLoops.push_back(New);
738
630k
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::addTopLevelLoop(llvm::VPLoop*)
Line
Count
Source
735
18
  void addTopLevelLoop(LoopT *New) {
736
18
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
18
    TopLevelLoops.push_back(New);
738
18
  }
739
740
  /// This method completely removes BB from all data structures,
741
  /// including all of the Loop objects it is nested in and our mapping from
742
  /// BasicBlocks to loops.
743
393k
  void removeBlock(BlockT *BB) {
744
393k
    auto I = BBMap.find(BB);
745
393k
    if (I != BBMap.end()) {
746
781k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()465k
)
747
465k
        L->removeBlockFromLoop(BB);
748
316k
749
316k
      BBMap.erase(I);
750
316k
    }
751
393k
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlock(llvm::MachineBasicBlock*)
Line
Count
Source
743
79.2k
  void removeBlock(BlockT *BB) {
744
79.2k
    auto I = BBMap.find(BB);
745
79.2k
    if (I != BBMap.end()) {
746
69.4k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()42.5k
)
747
42.5k
        L->removeBlockFromLoop(BB);
748
26.9k
749
26.9k
      BBMap.erase(I);
750
26.9k
    }
751
79.2k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeBlock(llvm::BasicBlock*)
Line
Count
Source
743
314k
  void removeBlock(BlockT *BB) {
744
314k
    auto I = BBMap.find(BB);
745
314k
    if (I != BBMap.end()) {
746
712k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()423k
)
747
423k
        L->removeBlockFromLoop(BB);
748
289k
749
289k
      BBMap.erase(I);
750
289k
    }
751
314k
  }
752
753
  // Internals
754
755
  static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
756
0
                                      const LoopT *ParentLoop) {
757
0
    if (!SubLoop)
758
0
      return true;
759
0
    if (SubLoop == ParentLoop)
760
0
      return false;
761
0
    return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
762
0
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::isNotAlreadyContainedIn(llvm::Loop const*, llvm::Loop const*)
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isNotAlreadyContainedIn(llvm::MachineLoop const*, llvm::MachineLoop const*)
763
764
  /// Create the loop forest using a stable algorithm.
765
  void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
766
767
  // Debugging
768
  void print(raw_ostream &OS) const;
769
770
  void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
771
772
  /// Destroy a loop that has been removed from the `LoopInfo` nest.
773
  ///
774
  /// This runs the destructor of the loop object making it invalid to
775
  /// reference afterward. The memory is retained so that the *pointer* to the
776
  /// loop remains valid.
777
  ///
778
  /// The caller is responsible for removing this loop from the loop nest and
779
  /// otherwise disconnecting it from the broader `LoopInfo` data structures.
780
  /// Callers that don't naturally handle this themselves should probably call
781
  /// `erase' instead.
782
27.1k
  void destroy(LoopT *L) {
783
27.1k
    L->~LoopT();
784
27.1k
785
27.1k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
786
27.1k
    // \c L, but the pointer remains valid for non-dereferencing uses.
787
27.1k
    LoopAllocator.Deallocate(L);
788
27.1k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::destroy(llvm::Loop*)
Line
Count
Source
782
27.1k
  void destroy(LoopT *L) {
783
27.1k
    L->~LoopT();
784
27.1k
785
27.1k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
786
27.1k
    // \c L, but the pointer remains valid for non-dereferencing uses.
787
27.1k
    LoopAllocator.Deallocate(L);
788
27.1k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::destroy(llvm::MachineLoop*)
789
};
790
791
// Implementation in LoopInfoImpl.h
792
extern template class LoopInfoBase<BasicBlock, Loop>;
793
794
class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
795
  typedef LoopInfoBase<BasicBlock, Loop> BaseT;
796
797
  friend class LoopBase<BasicBlock, Loop>;
798
799
  void operator=(const LoopInfo &) = delete;
800
  LoopInfo(const LoopInfo &) = delete;
801
802
public:
803
331k
  LoopInfo() {}
804
  explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
805
806
3.84k
  LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
807
0
  LoopInfo &operator=(LoopInfo &&RHS) {
808
0
    BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
809
0
    return *this;
810
0
  }
811
812
  /// Handle invalidation explicitly.
813
  bool invalidate(Function &F, const PreservedAnalyses &PA,
814
                  FunctionAnalysisManager::Invalidator &);
815
816
  // Most of the public interface is provided via LoopInfoBase.
817
818
  /// Update LoopInfo after removing the last backedge from a loop. This updates
819
  /// the loop forest and parent loops for each block so that \c L is no longer
820
  /// referenced, but does not actually delete \c L immediately. The pointer
821
  /// will remain valid until this LoopInfo's memory is released.
822
  void erase(Loop *L);
823
824
  /// Returns true if replacing From with To everywhere is guaranteed to
825
  /// preserve LCSSA form.
826
591k
  bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
827
591k
    // Preserving LCSSA form is only problematic if the replacing value is an
828
591k
    // instruction.
829
591k
    Instruction *I = dyn_cast<Instruction>(To);
830
591k
    if (!I)
831
534k
      return true;
832
57.4k
    // If both instructions are defined in the same basic block then replacement
833
57.4k
    // cannot break LCSSA form.
834
57.4k
    if (I->getParent() == From->getParent())
835
5.33k
      return true;
836
52.1k
    // If the instruction is not defined in a loop then it can safely replace
837
52.1k
    // anything.
838
52.1k
    Loop *ToLoop = getLoopFor(I->getParent());
839
52.1k
    if (!ToLoop)
840
4.13k
      return true;
841
47.9k
    // If the replacing instruction is defined in the same loop as the original
842
47.9k
    // instruction, or in a loop that contains it as an inner loop, then using
843
47.9k
    // it as a replacement will not break LCSSA form.
844
47.9k
    return ToLoop->contains(getLoopFor(From->getParent()));
845
47.9k
  }
846
847
  /// Checks if moving a specific instruction can break LCSSA in any loop.
848
  ///
849
  /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
850
  /// assuming that the function containing \p Inst and \p NewLoc is currently
851
  /// in LCSSA form.
852
24.4k
  bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
853
24.4k
    assert(Inst->getFunction() == NewLoc->getFunction() &&
854
24.4k
           "Can't reason about IPO!");
855
24.4k
856
24.4k
    auto *OldBB = Inst->getParent();
857
24.4k
    auto *NewBB = NewLoc->getParent();
858
24.4k
859
24.4k
    // Movement within the same loop does not break LCSSA (the equality check is
860
24.4k
    // to avoid doing a hashtable lookup in case of intra-block movement).
861
24.4k
    if (OldBB == NewBB)
862
23.1k
      return true;
863
1.25k
864
1.25k
    auto *OldLoop = getLoopFor(OldBB);
865
1.25k
    auto *NewLoop = getLoopFor(NewBB);
866
1.25k
867
1.25k
    if (OldLoop == NewLoop)
868
1.25k
      return true;
869
0
870
0
    // Check if Outer contains Inner; with the null loop counting as the
871
0
    // "outermost" loop.
872
0
    auto Contains = [](const Loop *Outer, const Loop *Inner) {
873
0
      return !Outer || Outer->contains(Inner);
874
0
    };
875
0
876
0
    // To check that the movement of Inst to before NewLoc does not break LCSSA,
877
0
    // we need to check two sets of uses for possible LCSSA violations at
878
0
    // NewLoc: the users of NewInst, and the operands of NewInst.
879
0
880
0
    // If we know we're hoisting Inst out of an inner loop to an outer loop,
881
0
    // then the uses *of* Inst don't need to be checked.
882
0
883
0
    if (!Contains(NewLoop, OldLoop)) {
884
0
      for (Use &U : Inst->uses()) {
885
0
        auto *UI = cast<Instruction>(U.getUser());
886
0
        auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
887
0
                                     : UI->getParent();
888
0
        if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
889
0
          return false;
890
0
      }
891
0
    }
892
0
893
0
    // If we know we're sinking Inst from an outer loop into an inner loop, then
894
0
    // the *operands* of Inst don't need to be checked.
895
0
896
0
    if (!Contains(OldLoop, NewLoop)) {
897
0
      // See below on why we can't handle phi nodes here.
898
0
      if (isa<PHINode>(Inst))
899
0
        return false;
900
0
901
0
      for (Use &U : Inst->operands()) {
902
0
        auto *DefI = dyn_cast<Instruction>(U.get());
903
0
        if (!DefI)
904
0
          return false;
905
0
906
0
        // This would need adjustment if we allow Inst to be a phi node -- the
907
0
        // new use block won't simply be NewBB.
908
0
909
0
        auto *DefBlock = DefI->getParent();
910
0
        if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
911
0
          return false;
912
0
      }
913
0
    }
914
0
915
0
    return true;
916
0
  }
917
};
918
919
// Allow clients to walk the list of nested loops...
920
template <> struct GraphTraits<const Loop *> {
921
  typedef const Loop *NodeRef;
922
  typedef LoopInfo::iterator ChildIteratorType;
923
924
1.75k
  static NodeRef getEntryNode(const Loop *L) { return L; }
925
1.89k
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
926
2.02k
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
927
};
928
929
template <> struct GraphTraits<Loop *> {
930
  typedef Loop *NodeRef;
931
  typedef LoopInfo::iterator ChildIteratorType;
932
933
406k
  static NodeRef getEntryNode(Loop *L) { return L; }
934
561k
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
935
717k
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
936
};
937
938
/// Analysis pass that exposes the \c LoopInfo for a function.
939
class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
940
  friend AnalysisInfoMixin<LoopAnalysis>;
941
  static AnalysisKey Key;
942
943
public:
944
  typedef LoopInfo Result;
945
946
  LoopInfo run(Function &F, FunctionAnalysisManager &AM);
947
};
948
949
/// Printer pass for the \c LoopAnalysis results.
950
class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> {
951
  raw_ostream &OS;
952
953
public:
954
1
  explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
955
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
956
};
957
958
/// Verifier pass for the \c LoopAnalysis results.
959
struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> {
960
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
961
};
962
963
/// The legacy pass manager's analysis pass to compute loop information.
964
class LoopInfoWrapperPass : public FunctionPass {
965
  LoopInfo LI;
966
967
public:
968
  static char ID; // Pass identification, replacement for typeid
969
970
329k
  LoopInfoWrapperPass() : FunctionPass(ID) {
971
329k
    initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
972
329k
  }
973
974
40.7M
  LoopInfo &getLoopInfo() { return LI; }
975
0
  const LoopInfo &getLoopInfo() const { return LI; }
976
977
  /// Calculate the natural loop information for a given function.
978
  bool runOnFunction(Function &F) override;
979
980
  void verifyAnalysis() const override;
981
982
13.9M
  void releaseMemory() override { LI.releaseMemory(); }
983
984
  void print(raw_ostream &O, const Module *M = nullptr) const override;
985
986
  void getAnalysisUsage(AnalysisUsage &AU) const override;
987
};
988
989
/// Function to print a loop's contents as LLVM's text IR assembly.
990
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
991
992
} // End llvm namespace
993
994
#endif