Coverage Report

Created: 2019-02-15 18:59

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