Coverage Report

Created: 2018-09-19 20:53

/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
2.38M
  unsigned getLoopDepth() const {
93
2.38M
    assert(!isInvalid() && "Loop not in a valid state!");
94
2.38M
    unsigned D = 1;
95
3.31M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
2.38M
         
CurLoop = CurLoop->ParentLoop932k
)
97
932k
      ++D;
98
2.38M
    return D;
99
2.38M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth() const
Line
Count
Source
92
1.09M
  unsigned getLoopDepth() const {
93
1.09M
    assert(!isInvalid() && "Loop not in a valid state!");
94
1.09M
    unsigned D = 1;
95
1.48M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
1.09M
         
CurLoop = CurLoop->ParentLoop385k
)
97
385k
      ++D;
98
1.09M
    return D;
99
1.09M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth() const
Line
Count
Source
92
1.28M
  unsigned getLoopDepth() const {
93
1.28M
    assert(!isInvalid() && "Loop not in a valid state!");
94
1.28M
    unsigned D = 1;
95
1.83M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
96
1.28M
         
CurLoop = CurLoop->ParentLoop546k
)
97
546k
      ++D;
98
1.28M
    return D;
99
1.28M
  }
100
159M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getHeader() const
Line
Count
Source
100
144M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getHeader() const
Line
Count
Source
100
14.7M
  BlockT *getHeader() const { return getBlocks().front(); }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getHeader() const
101
41.9M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getParentLoop() const
Line
Count
Source
101
6.37M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getParentLoop() const
Line
Count
Source
101
35.5M
  LoopT *getParentLoop() const { return ParentLoop; }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getParentLoop() const
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
864k
  void setParentLoop(LoopT *L) {
105
864k
    assert(!isInvalid() && "Loop not in a valid state!");
106
864k
    ParentLoop = L;
107
864k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::setParentLoop(llvm::MachineLoop*)
Line
Count
Source
104
219k
  void setParentLoop(LoopT *L) {
105
219k
    assert(!isInvalid() && "Loop not in a valid state!");
106
219k
    ParentLoop = L;
107
219k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::setParentLoop(llvm::VPLoop*)
108
109
  /// Return true if the specified loop is contained within in this loop.
110
28.4M
  bool contains(const LoopT *L) const {
111
28.4M
    assert(!isInvalid() && "Loop not in a valid state!");
112
28.4M
    if (L == this)
113
19.1M
      return true;
114
9.27M
    if (!L)
115
1.97M
      return false;
116
7.29M
    return contains(L->getParentLoop());
117
7.29M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::Loop const*) const
Line
Count
Source
110
27.1M
  bool contains(const LoopT *L) const {
111
27.1M
    assert(!isInvalid() && "Loop not in a valid state!");
112
27.1M
    if (L == this)
113
18.3M
      return true;
114
8.73M
    if (!L)
115
1.74M
      return false;
116
6.98M
    return contains(L->getParentLoop());
117
6.98M
  }
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
745k
      return true;
114
544k
    if (!L)
115
229k
      return false;
116
314k
    return contains(L->getParentLoop());
117
314k
  }
118
119
  /// Return true if the specified basic block is in this loop.
120
344M
  bool contains(const BlockT *BB) const {
121
344M
    assert(!isInvalid() && "Loop not in a valid state!");
122
344M
    return DenseBlockSet.count(BB);
123
344M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::BasicBlock const*) const
Line
Count
Source
120
329M
  bool contains(const BlockT *BB) const {
121
329M
    assert(!isInvalid() && "Loop not in a valid state!");
122
329M
    return DenseBlockSet.count(BB);
123
329M
  }
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.2M
  template <class InstT> bool contains(const InstT *Inst) const {
127
46.2M
    return contains(Inst->getParent());
128
46.2M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::Instruction>(llvm::Instruction const*) const
Line
Count
Source
126
43.6M
  template <class InstT> bool contains(const InstT *Inst) const {
127
43.6M
    return contains(Inst->getParent());
128
43.6M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::PHINode>(llvm::PHINode const*) const
Line
Count
Source
126
458k
  template <class InstT> bool contains(const InstT *Inst) const {
127
458k
    return contains(Inst->getParent());
128
458k
  }
bool llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains<llvm::MachineInstr>(llvm::MachineInstr const*) const
Line
Count
Source
126
2.18M
  template <class InstT> bool contains(const InstT *Inst) const {
127
2.18M
    return contains(Inst->getParent());
128
2.18M
  }
129
130
  /// Return the loops contained entirely within this loop.
131
19.3M
  const std::vector<LoopT *> &getSubLoops() const {
132
19.3M
    assert(!isInvalid() && "Loop not in a valid state!");
133
19.3M
    return SubLoops;
134
19.3M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoops() const
Line
Count
Source
131
16.8M
  const std::vector<LoopT *> &getSubLoops() const {
132
16.8M
    assert(!isInvalid() && "Loop not in a valid state!");
133
16.8M
    return SubLoops;
134
16.8M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoops() const
Line
Count
Source
131
2.51M
  const std::vector<LoopT *> &getSubLoops() const {
132
2.51M
    assert(!isInvalid() && "Loop not in a valid state!");
133
2.51M
    return SubLoops;
134
2.51M
  }
135
13.1M
  std::vector<LoopT *> &getSubLoopsVector() {
136
13.1M
    assert(!isInvalid() && "Loop not in a valid state!");
137
13.1M
    return SubLoops;
138
13.1M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoopsVector()
Line
Count
Source
135
10.5M
  std::vector<LoopT *> &getSubLoopsVector() {
136
10.5M
    assert(!isInvalid() && "Loop not in a valid state!");
137
10.5M
    return SubLoops;
138
10.5M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoopsVector()
Line
Count
Source
135
2.67M
  std::vector<LoopT *> &getSubLoopsVector() {
136
2.67M
    assert(!isInvalid() && "Loop not in a valid state!");
137
2.67M
    return SubLoops;
138
2.67M
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getSubLoopsVector()
139
  typedef typename std::vector<LoopT *>::const_iterator iterator;
140
  typedef
141
      typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
142
6.20M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
142
4.95M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
142
1.24M
  iterator begin() const { return getSubLoops().begin(); }
143
6.34M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
143
5.09M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
143
1.24M
  iterator end() const { return getSubLoops().end(); }
144
1.56M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
144
1.56M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
145
1.56M
  reverse_iterator rend() const { return getSubLoops().rend(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
145
1.56M
  reverse_iterator rend() const { return getSubLoops().rend(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
146
1.50M
  bool empty() const { return getSubLoops().empty(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
146
1.50M
  bool empty() const { return getSubLoops().empty(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
147
148
  /// Get a list of the basic blocks which make up this loop.
149
211M
  ArrayRef<BlockT *> getBlocks() const {
150
211M
    assert(!isInvalid() && "Loop not in a valid state!");
151
211M
    return Blocks;
152
211M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocks() const
Line
Count
Source
149
195M
  ArrayRef<BlockT *> getBlocks() const {
150
195M
    assert(!isInvalid() && "Loop not in a valid state!");
151
195M
    return Blocks;
152
195M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocks() const
Line
Count
Source
149
16.4M
  ArrayRef<BlockT *> getBlocks() const {
150
16.4M
    assert(!isInvalid() && "Loop not in a valid state!");
151
16.4M
    return Blocks;
152
16.4M
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocks() const
153
  typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
154
25.3M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_begin() const
Line
Count
Source
154
24.8M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_begin() const
Line
Count
Source
154
571k
  block_iterator block_begin() const { return getBlocks().begin(); }
155
25.2M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_end() const
Line
Count
Source
155
24.6M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_end() const
Line
Count
Source
155
571k
  block_iterator block_end() const { return getBlocks().end(); }
156
21.7M
  inline iterator_range<block_iterator> blocks() const {
157
21.7M
    assert(!isInvalid() && "Loop not in a valid state!");
158
21.7M
    return make_range(block_begin(), block_end());
159
21.7M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::blocks() const
Line
Count
Source
156
21.4M
  inline iterator_range<block_iterator> blocks() const {
157
21.4M
    assert(!isInvalid() && "Loop not in a valid state!");
158
21.4M
    return make_range(block_begin(), block_end());
159
21.4M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::blocks() const
Line
Count
Source
156
341k
  inline iterator_range<block_iterator> blocks() const {
157
341k
    assert(!isInvalid() && "Loop not in a valid state!");
158
341k
    return make_range(block_begin(), block_end());
159
341k
  }
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
952k
  unsigned getNumBlocks() const {
164
952k
    assert(!isInvalid() && "Loop not in a valid state!");
165
952k
    return Blocks.size();
166
952k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getNumBlocks() const
Line
Count
Source
163
97.7k
  unsigned getNumBlocks() const {
164
97.7k
    assert(!isInvalid() && "Loop not in a valid state!");
165
97.7k
    return Blocks.size();
166
97.7k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBlocks() const
Line
Count
Source
163
854k
  unsigned getNumBlocks() const {
164
854k
    assert(!isInvalid() && "Loop not in a valid state!");
165
854k
    return Blocks.size();
166
854k
  }
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
864k
  std::vector<BlockT *> &getBlocksVector() {
171
864k
    assert(!isInvalid() && "Loop not in a valid state!");
172
864k
    return Blocks;
173
864k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksVector()
Line
Count
Source
170
219k
  std::vector<BlockT *> &getBlocksVector() {
171
219k
    assert(!isInvalid() && "Loop not in a valid state!");
172
219k
    return Blocks;
173
219k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocksVector()
174
  /// Return a direct, mutable handle to the blocks set so that we can
175
  /// mutate it efficiently.
176
0
  SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
177
0
    assert(!isInvalid() && "Loop not in a valid state!");
178
0
    return DenseBlockSet;
179
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksSet()
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.70M
  bool isLoopExiting(const BlockT *BB) const {
204
4.70M
    assert(!isInvalid() && "Loop not in a valid state!");
205
7.03M
    for (const auto &Succ : children<const BlockT *>(BB)) {
206
7.03M
      if (!contains(Succ))
207
2.35M
        return true;
208
7.03M
    }
209
4.70M
    
return false2.35M
;
210
4.70M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopExiting(llvm::BasicBlock const*) const
Line
Count
Source
203
686k
  bool isLoopExiting(const BlockT *BB) const {
204
686k
    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
538k
        return true;
208
1.03M
    }
209
686k
    
return false148k
;
210
686k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopExiting(llvm::MachineBasicBlock const*) const
Line
Count
Source
203
4.01M
  bool isLoopExiting(const BlockT *BB) const {
204
4.01M
    assert(!isInvalid() && "Loop not in a valid state!");
205
6.00M
    for (const auto &Succ : children<const BlockT *>(BB)) {
206
6.00M
      if (!contains(Succ))
207
1.81M
        return true;
208
6.00M
    }
209
4.01M
    
return false2.20M
;
210
4.01M
  }
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
43
  bool isLoopLatch(const BlockT *BB) const {
217
43
    assert(!isInvalid() && "Loop not in a valid state!");
218
43
    assert(contains(BB) && "block does not belong to the loop");
219
43
220
43
    BlockT *Header = getHeader();
221
43
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
222
43
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
223
43
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
224
43
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopLatch(llvm::BasicBlock const*) const
Line
Count
Source
216
43
  bool isLoopLatch(const BlockT *BB) const {
217
43
    assert(!isInvalid() && "Loop not in a valid state!");
218
43
    assert(contains(BB) && "block does not belong to the loop");
219
43
220
43
    BlockT *Header = getHeader();
221
43
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
222
43
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
223
43
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
224
43
  }
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
599k
  unsigned getNumBackEdges() const {
228
599k
    assert(!isInvalid() && "Loop not in a valid state!");
229
599k
    unsigned NumBackEdges = 0;
230
599k
    BlockT *H = getHeader();
231
599k
232
599k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
233
1.21M
      if (contains(Pred))
234
611k
        ++NumBackEdges;
235
599k
236
599k
    return NumBackEdges;
237
599k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBackEdges() const
Line
Count
Source
227
599k
  unsigned getNumBackEdges() const {
228
599k
    assert(!isInvalid() && "Loop not in a valid state!");
229
599k
    unsigned NumBackEdges = 0;
230
599k
    BlockT *H = getHeader();
231
599k
232
599k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
233
1.21M
      if (contains(Pred))
234
611k
        ++NumBackEdges;
235
599k
236
599k
    return NumBackEdges;
237
599k
  }
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.02M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
305
3.02M
    assert(!isInvalid() && "Loop not in a valid state!");
306
3.02M
    BlockT *H = getHeader();
307
3.02M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
308
6.05M
      if (contains(Pred))
309
3.02M
        LoopLatches.push_back(Pred);
310
3.02M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatches(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
304
3.02M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
305
3.02M
    assert(!isInvalid() && "Loop not in a valid state!");
306
3.02M
    BlockT *H = getHeader();
307
3.02M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
308
6.05M
      if (contains(Pred))
309
3.02M
        LoopLatches.push_back(Pred);
310
3.02M
  }
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
25.9k
  void addChildLoop(LoopT *NewChild) {
332
25.9k
    assert(!isInvalid() && "Loop not in a valid state!");
333
25.9k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
334
25.9k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
335
25.9k
    SubLoops.push_back(NewChild);
336
25.9k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addChildLoop(llvm::Loop*)
Line
Count
Source
331
25.9k
  void addChildLoop(LoopT *NewChild) {
332
25.9k
    assert(!isInvalid() && "Loop not in a valid state!");
333
25.9k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
334
25.9k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
335
25.9k
    SubLoops.push_back(NewChild);
336
25.9k
  }
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.58k
  LoopT *removeChildLoop(iterator I) {
341
9.58k
    assert(!isInvalid() && "Loop not in a valid state!");
342
9.58k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
343
9.58k
    LoopT *Child = *I;
344
9.58k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
345
9.58k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
346
9.58k
    Child->ParentLoop = nullptr;
347
9.58k
    return Child;
348
9.58k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
340
9.58k
  LoopT *removeChildLoop(iterator I) {
341
9.58k
    assert(!isInvalid() && "Loop not in a valid state!");
342
9.58k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
343
9.58k
    LoopT *Child = *I;
344
9.58k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
345
9.58k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
346
9.58k
    Child->ParentLoop = nullptr;
347
9.58k
    return Child;
348
9.58k
  }
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
0
  LoopT *removeChildLoop(LoopT *Child) {
353
0
    return removeChildLoop(llvm::find(*this, Child));
354
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(llvm::Loop*)
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.5M
  void addBlockEntry(BlockT *BB) {
360
14.5M
    assert(!isInvalid() && "Loop not in a valid state!");
361
14.5M
    Blocks.push_back(BB);
362
14.5M
    DenseBlockSet.insert(BB);
363
14.5M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBlockEntry(llvm::BasicBlock*)
Line
Count
Source
359
11.7M
  void addBlockEntry(BlockT *BB) {
360
11.7M
    assert(!isInvalid() && "Loop not in a valid state!");
361
11.7M
    Blocks.push_back(BB);
362
11.7M
    DenseBlockSet.insert(BB);
363
11.7M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBlockEntry(llvm::MachineBasicBlock*)
Line
Count
Source
359
2.86M
  void addBlockEntry(BlockT *BB) {
360
2.86M
    assert(!isInvalid() && "Loop not in a valid state!");
361
2.86M
    Blocks.push_back(BB);
362
2.86M
    DenseBlockSet.insert(BB);
363
2.86M
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::addBlockEntry(llvm::VPBlockBase*)
364
365
  /// interface to reverse Blocks[from, end of loop] in this loop
366
4.03M
  void reverseBlock(unsigned from) {
367
4.03M
    assert(!isInvalid() && "Loop not in a valid state!");
368
4.03M
    std::reverse(Blocks.begin() + from, Blocks.end());
369
4.03M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reverseBlock(unsigned int)
Line
Count
Source
366
3.21M
  void reverseBlock(unsigned from) {
367
3.21M
    assert(!isInvalid() && "Loop not in a valid state!");
368
3.21M
    std::reverse(Blocks.begin() + from, Blocks.end());
369
3.21M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reverseBlock(unsigned int)
Line
Count
Source
366
818k
  void reverseBlock(unsigned from) {
367
818k
    assert(!isInvalid() && "Loop not in a valid state!");
368
818k
    std::reverse(Blocks.begin() + from, Blocks.end());
369
818k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reverseBlock(unsigned int)
370
371
  /// interface to do reserve() for Blocks
372
4.03M
  void reserveBlocks(unsigned size) {
373
4.03M
    assert(!isInvalid() && "Loop not in a valid state!");
374
4.03M
    Blocks.reserve(size);
375
4.03M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reserveBlocks(unsigned int)
Line
Count
Source
372
3.21M
  void reserveBlocks(unsigned size) {
373
3.21M
    assert(!isInvalid() && "Loop not in a valid state!");
374
3.21M
    Blocks.reserve(size);
375
3.21M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reserveBlocks(unsigned int)
Line
Count
Source
372
818k
  void reserveBlocks(unsigned size) {
373
818k
    assert(!isInvalid() && "Loop not in a valid state!");
374
818k
    Blocks.reserve(size);
375
818k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reserveBlocks(unsigned int)
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.1k
  void moveToHeader(BlockT *BB) {
380
40.1k
    assert(!isInvalid() && "Loop not in a valid state!");
381
40.1k
    if (Blocks[0] == BB)
382
0
      return;
383
131k
    
for (unsigned i = 0;; 40.1k
++i91.3k
) {
384
131k
      assert(i != Blocks.size() && "Loop does not contain BB!");
385
131k
      if (Blocks[i] == BB) {
386
40.1k
        Blocks[i] = Blocks[0];
387
40.1k
        Blocks[0] = BB;
388
40.1k
        return;
389
40.1k
      }
390
131k
    }
391
40.1k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::moveToHeader(llvm::BasicBlock*)
Line
Count
Source
379
40.1k
  void moveToHeader(BlockT *BB) {
380
40.1k
    assert(!isInvalid() && "Loop not in a valid state!");
381
40.1k
    if (Blocks[0] == BB)
382
0
      return;
383
131k
    
for (unsigned i = 0;; 40.1k
++i91.3k
) {
384
131k
      assert(i != Blocks.size() && "Loop does not contain BB!");
385
131k
      if (Blocks[i] == BB) {
386
40.1k
        Blocks[i] = Blocks[0];
387
40.1k
        Blocks[0] = BB;
388
40.1k
        return;
389
40.1k
      }
390
131k
    }
391
40.1k
  }
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
459k
  void removeBlockFromLoop(BlockT *BB) {
397
459k
    assert(!isInvalid() && "Loop not in a valid state!");
398
459k
    auto I = find(Blocks, BB);
399
459k
    assert(I != Blocks.end() && "N is not in this list!");
400
459k
    Blocks.erase(I);
401
459k
402
459k
    DenseBlockSet.erase(BB);
403
459k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlockFromLoop(llvm::MachineBasicBlock*)
Line
Count
Source
396
42.2k
  void removeBlockFromLoop(BlockT *BB) {
397
42.2k
    assert(!isInvalid() && "Loop not in a valid state!");
398
42.2k
    auto I = find(Blocks, BB);
399
42.2k
    assert(I != Blocks.end() && "N is not in this list!");
400
42.2k
    Blocks.erase(I);
401
42.2k
402
42.2k
    DenseBlockSet.erase(BB);
403
42.2k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeBlockFromLoop(llvm::BasicBlock*)
Line
Count
Source
396
416k
  void removeBlockFromLoop(BlockT *BB) {
397
416k
    assert(!isInvalid() && "Loop not in a valid state!");
398
416k
    auto I = find(Blocks, BB);
399
416k
    assert(I != Blocks.end() && "N is not in this list!");
400
416k
    Blocks.erase(I);
401
416k
402
416k
    DenseBlockSet.erase(BB);
403
416k
  }
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
41.4k
  LoopBase() : ParentLoop(nullptr) {}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase()
Line
Count
Source
418
41.4k
  LoopBase() : ParentLoop(nullptr) {}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase()
419
420
4.03M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
4.03M
    Blocks.push_back(BB);
422
4.03M
    DenseBlockSet.insert(BB);
423
4.03M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase(llvm::BasicBlock*)
Line
Count
Source
420
3.21M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
3.21M
    Blocks.push_back(BB);
422
3.21M
    DenseBlockSet.insert(BB);
423
3.21M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase(llvm::MachineBasicBlock*)
Line
Count
Source
420
818k
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
421
818k
    Blocks.push_back(BB);
422
818k
    DenseBlockSet.insert(BB);
423
818k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::LoopBase(llvm::VPBlockBase*)
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.07M
  ~LoopBase() {
435
4.07M
    for (auto *SubLoop : SubLoops)
436
1.09M
      SubLoop->~LoopT();
437
4.07M
438
4.07M
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
4.07M
    IsInvalid = true;
440
4.07M
#endif
441
4.07M
    SubLoops.clear();
442
4.07M
    Blocks.clear();
443
4.07M
    DenseBlockSet.clear();
444
4.07M
    ParentLoop = nullptr;
445
4.07M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::~LoopBase()
Line
Count
Source
434
3.25M
  ~LoopBase() {
435
3.25M
    for (auto *SubLoop : SubLoops)
436
880k
      SubLoop->~LoopT();
437
3.25M
438
3.25M
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
3.25M
    IsInvalid = true;
440
3.25M
#endif
441
3.25M
    SubLoops.clear();
442
3.25M
    Blocks.clear();
443
3.25M
    DenseBlockSet.clear();
444
3.25M
    ParentLoop = nullptr;
445
3.25M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopBase()
Line
Count
Source
434
818k
  ~LoopBase() {
435
818k
    for (auto *SubLoop : SubLoops)
436
219k
      SubLoop->~LoopT();
437
818k
438
818k
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
439
818k
    IsInvalid = true;
440
818k
#endif
441
818k
    SubLoops.clear();
442
818k
    Blocks.clear();
443
818k
    DenseBlockSet.clear();
444
818k
    ParentLoop = nullptr;
445
818k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopBase()
446
};
447
448
template <class BlockT, class LoopT>
449
0
raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
450
0
  Loop.print(OS);
451
0
  return OS;
452
0
}
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
226k
    LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {}
469
    LocRange(DebugLoc Start, DebugLoc End)
470
18.2k
        : Start(std::move(Start)), End(std::move(End)) {}
471
472
244k
    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.03M
  StringRef getName() const {
584
1.03M
    if (BasicBlock *Header = getHeader())
585
1.03M
      if (Header->hasName())
586
445k
        return Header->getName();
587
593k
    return "<unnamed loop>";
588
593k
  }
589
590
private:
591
41.4k
  Loop() = default;
592
593
  friend class LoopInfoBase<BasicBlock, Loop>;
594
  friend class LoopBase<BasicBlock, Loop>;
595
3.21M
  explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
596
3.25M
  ~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
317k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase()
Line
Count
Source
617
220k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopInfoBase()
Line
Count
Source
617
59.4k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::LoopInfoBase()
Line
Count
Source
617
36.7k
  LoopInfoBase() {}
618
317k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::~LoopInfoBase()
Line
Count
Source
618
220k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopInfoBase()
Line
Count
Source
618
59.4k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopInfoBase()
Line
Count
Source
618
36.7k
  ~LoopInfoBase() { releaseMemory(); }
619
620
  LoopInfoBase(LoopInfoBase &&Arg)
621
      : BBMap(std::move(Arg.BBMap)),
622
        TopLevelLoops(std::move(Arg.TopLevelLoops)),
623
6
        LoopAllocator(std::move(Arg.LoopAllocator)) {
624
6
    // We have to clear the arguments top level loops as we've taken ownership.
625
6
    Arg.TopLevelLoops.clear();
626
6
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&&)
Line
Count
Source
623
6
        LoopAllocator(std::move(Arg.LoopAllocator)) {
624
6
    // We have to clear the arguments top level loops as we've taken ownership.
625
6
    Arg.TopLevelLoops.clear();
626
6
  }
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
14.5M
  void releaseMemory() {
640
14.5M
    BBMap.clear();
641
14.5M
642
14.5M
    for (auto *L : TopLevelLoops)
643
2.95M
      L->~LoopT();
644
14.5M
    TopLevelLoops.clear();
645
14.5M
    LoopAllocator.Reset();
646
14.5M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::releaseMemory()
Line
Count
Source
639
12.2M
  void releaseMemory() {
640
12.2M
    BBMap.clear();
641
12.2M
642
12.2M
    for (auto *L : TopLevelLoops)
643
2.35M
      L->~LoopT();
644
12.2M
    TopLevelLoops.clear();
645
12.2M
    LoopAllocator.Reset();
646
12.2M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::releaseMemory()
Line
Count
Source
639
2.30M
  void releaseMemory() {
640
2.30M
    BBMap.clear();
641
2.30M
642
2.30M
    for (auto *L : TopLevelLoops)
643
599k
      L->~LoopT();
644
2.30M
    TopLevelLoops.clear();
645
2.30M
    LoopAllocator.Reset();
646
2.30M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::releaseMemory()
Line
Count
Source
639
36.7k
  void releaseMemory() {
640
36.7k
    BBMap.clear();
641
36.7k
642
36.7k
    for (auto *L : TopLevelLoops)
643
0
      L->~LoopT();
644
36.7k
    TopLevelLoops.clear();
645
36.7k
    LoopAllocator.Reset();
646
36.7k
  }
647
648
4.07M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
4.07M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
4.07M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
4.07M
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<llvm::BasicBlock*&>(llvm::BasicBlock*&&&)
Line
Count
Source
648
3.21M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
3.21M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
3.21M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
3.21M
  }
llvm::MachineLoop* llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::AllocateLoop<llvm::MachineBasicBlock*&>(llvm::MachineBasicBlock*&&&)
Line
Count
Source
648
818k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
818k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
818k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
818k
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<>()
Line
Count
Source
648
41.4k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
649
41.4k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
650
41.4k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
651
41.4k
  }
Unexecuted instantiation: llvm::VPLoop* llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::AllocateLoop<llvm::VPBlockBase*&>(llvm::VPBlockBase*&&&)
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
8.72M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
659
7.48M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
659
1.24M
  iterator begin() const { return TopLevelLoops.begin(); }
660
8.68M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
660
7.44M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
660
1.24M
  iterator end() const { return TopLevelLoops.end(); }
661
2.72M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
661
2.72M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
662
2.72M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
662
2.72M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
663
2.96M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
663
1.85M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
Line
Count
Source
663
1.10M
  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
194M
  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
137M
  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
57.1M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::getLoopFor(llvm::VPBlockBase const*) const
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
4.93M
  unsigned getLoopDepth(const BlockT *BB) const {
692
4.93M
    const LoopT *L = getLoopFor(BB);
693
4.93M
    return L ? 
L->getLoopDepth()1.27M
:
03.66M
;
694
4.93M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth(llvm::BasicBlock const*) const
Line
Count
Source
691
166k
  unsigned getLoopDepth(const BlockT *BB) const {
692
166k
    const LoopT *L = getLoopFor(BB);
693
166k
    return L ? 
L->getLoopDepth()67.0k
:
099.3k
;
694
166k
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth(llvm::MachineBasicBlock const*) const
Line
Count
Source
691
4.77M
  unsigned getLoopDepth(const BlockT *BB) const {
692
4.77M
    const LoopT *L = getLoopFor(BB);
693
4.77M
    return L ? 
L->getLoopDepth()1.20M
:
03.56M
;
694
4.77M
  }
695
696
  // True if the block is a loop header node
697
3.26M
  bool isLoopHeader(const BlockT *BB) const {
698
3.26M
    const LoopT *L = getLoopFor(BB);
699
3.26M
    return L && 
L->getHeader() == BB933k
;
700
3.26M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopHeader(llvm::MachineBasicBlock const*) const
Line
Count
Source
697
3.10M
  bool isLoopHeader(const BlockT *BB) const {
698
3.10M
    const LoopT *L = getLoopFor(BB);
699
3.10M
    return L && 
L->getHeader() == BB805k
;
700
3.10M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::isLoopHeader(llvm::BasicBlock const*) const
Line
Count
Source
697
155k
  bool isLoopHeader(const BlockT *BB) const {
698
155k
    const LoopT *L = getLoopFor(BB);
699
155k
    return L && 
L->getHeader() == BB127k
;
700
155k
  }
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.7k
  LoopT *removeLoop(iterator I) {
706
19.7k
    assert(I != end() && "Cannot remove end iterator!");
707
19.7k
    LoopT *L = *I;
708
19.7k
    assert(!L->getParentLoop() && "Not a top-level loop!");
709
19.7k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
710
19.7k
    return L;
711
19.7k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
705
19.7k
  LoopT *removeLoop(iterator I) {
706
19.7k
    assert(I != end() && "Cannot remove end iterator!");
707
19.7k
    LoopT *L = *I;
708
19.7k
    assert(!L->getParentLoop() && "Not a top-level loop!");
709
19.7k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
710
19.7k
    return L;
711
19.7k
  }
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.2M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
13.2M
    if (!L) {
718
77.5k
      BBMap.erase(BB);
719
77.5k
      return;
720
77.5k
    }
721
13.1M
    BBMap[BB] = L;
722
13.1M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::changeLoopFor(llvm::MachineBasicBlock*, llvm::MachineLoop*)
Line
Count
Source
716
2.68M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
2.68M
    if (!L) {
718
0
      BBMap.erase(BB);
719
0
      return;
720
0
    }
721
2.68M
    BBMap[BB] = L;
722
2.68M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeLoopFor(llvm::BasicBlock*, llvm::Loop*)
Line
Count
Source
716
10.5M
  void changeLoopFor(BlockT *BB, LoopT *L) {
717
10.5M
    if (!L) {
718
77.5k
      BBMap.erase(BB);
719
77.5k
      return;
720
77.5k
    }
721
10.4M
    BBMap[BB] = L;
722
10.4M
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::changeLoopFor(llvm::VPBlockBase*, llvm::VPLoop*)
723
724
  /// Replace the specified loop in the top-level loops list with the indicated
725
  /// loop.
726
259
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
727
259
    auto I = find(TopLevelLoops, OldLoop);
728
259
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
729
259
    *I = NewLoop;
730
259
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
731
259
           "Loops already embedded into a subloop!");
732
259
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeTopLevelLoop(llvm::Loop*, llvm::Loop*)
Line
Count
Source
726
259
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
727
259
    auto I = find(TopLevelLoops, OldLoop);
728
259
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
729
259
    *I = NewLoop;
730
259
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
731
259
           "Loops already embedded into a subloop!");
732
259
  }
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
2.97M
  void addTopLevelLoop(LoopT *New) {
736
2.97M
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
2.97M
    TopLevelLoops.push_back(New);
738
2.97M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::addTopLevelLoop(llvm::Loop*)
Line
Count
Source
735
2.37M
  void addTopLevelLoop(LoopT *New) {
736
2.37M
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
2.37M
    TopLevelLoops.push_back(New);
738
2.37M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addTopLevelLoop(llvm::MachineLoop*)
Line
Count
Source
735
599k
  void addTopLevelLoop(LoopT *New) {
736
599k
    assert(!New->getParentLoop() && "Loop already in subloop!");
737
599k
    TopLevelLoops.push_back(New);
738
599k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::addTopLevelLoop(llvm::VPLoop*)
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
380k
  void removeBlock(BlockT *BB) {
744
380k
    auto I = BBMap.find(BB);
745
380k
    if (I != BBMap.end()) {
746
756k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()452k
)
747
452k
        L->removeBlockFromLoop(BB);
748
303k
749
303k
      BBMap.erase(I);
750
303k
    }
751
380k
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlock(llvm::MachineBasicBlock*)
Line
Count
Source
743
78.6k
  void removeBlock(BlockT *BB) {
744
78.6k
    auto I = BBMap.find(BB);
745
78.6k
    if (I != BBMap.end()) {
746
69.0k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()42.2k
)
747
42.2k
        L->removeBlockFromLoop(BB);
748
26.7k
749
26.7k
      BBMap.erase(I);
750
26.7k
    }
751
78.6k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeBlock(llvm::BasicBlock*)
Line
Count
Source
743
301k
  void removeBlock(BlockT *BB) {
744
301k
    auto I = BBMap.find(BB);
745
301k
    if (I != BBMap.end()) {
746
687k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()410k
)
747
410k
        L->removeBlockFromLoop(BB);
748
277k
749
277k
      BBMap.erase(I);
750
277k
    }
751
301k
  }
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
26.9k
  void destroy(LoopT *L) {
783
26.9k
    L->~LoopT();
784
26.9k
785
26.9k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
786
26.9k
    // \c L, but the pointer remains valid for non-dereferencing uses.
787
26.9k
    LoopAllocator.Deallocate(L);
788
26.9k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::destroy(llvm::Loop*)
Line
Count
Source
782
26.9k
  void destroy(LoopT *L) {
783
26.9k
    L->~LoopT();
784
26.9k
785
26.9k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
786
26.9k
    // \c L, but the pointer remains valid for non-dereferencing uses.
787
26.9k
    LoopAllocator.Deallocate(L);
788
26.9k
  }
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
220k
  LoopInfo() {}
804
  explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
805
806
6
  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
565k
  bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
827
565k
    // Preserving LCSSA form is only problematic if the replacing value is an
828
565k
    // instruction.
829
565k
    Instruction *I = dyn_cast<Instruction>(To);
830
565k
    if (!I)
831
508k
      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.32k
      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.86k
      return true;
841
47.2k
    // If the replacing instruction is defined in the same loop as the original
842
47.2k
    // instruction, or in a loop that contains it as an inner loop, then using
843
47.2k
    // it as a replacement will not break LCSSA form.
844
47.2k
    return ToLoop->contains(getLoopFor(From->getParent()));
845
47.2k
  }
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.3k
  bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
853
24.3k
    assert(Inst->getFunction() == NewLoc->getFunction() &&
854
24.3k
           "Can't reason about IPO!");
855
24.3k
856
24.3k
    auto *OldBB = Inst->getParent();
857
24.3k
    auto *NewBB = NewLoc->getParent();
858
24.3k
859
24.3k
    // Movement within the same loop does not break LCSSA (the equality check is
860
24.3k
    // to avoid doing a hashtable lookup in case of intra-block movement).
861
24.3k
    if (OldBB == NewBB)
862
23.0k
      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
0
  static NodeRef getEntryNode(const Loop *L) { return L; }
925
0
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
926
0
  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
404k
  static NodeRef getEntryNode(Loop *L) { return L; }
934
560k
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
935
715k
  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
0
  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
220k
  LoopInfoWrapperPass() : FunctionPass(ID) {
971
220k
    initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
972
220k
  }
973
974
38.0M
  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
12.0M
  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