Coverage Report

Created: 2019-07-24 05:18

/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 InductionDescriptor;
58
class MDNode;
59
class MemorySSAUpdater;
60
class PHINode;
61
class ScalarEvolution;
62
class raw_ostream;
63
template <class N, bool IsPostDom> class DominatorTreeBase;
64
template <class N, class M> class LoopInfoBase;
65
template <class N, class M> class LoopBase;
66
67
//===----------------------------------------------------------------------===//
68
/// Instances of this class are used to represent loops that are detected in the
69
/// flow graph.
70
///
71
template <class BlockT, class LoopT> class LoopBase {
72
  LoopT *ParentLoop;
73
  // Loops contained entirely within this one.
74
  std::vector<LoopT *> SubLoops;
75
76
  // The list of blocks in this loop. First entry is the header node.
77
  std::vector<BlockT *> Blocks;
78
79
  SmallPtrSet<const BlockT *, 8> DenseBlockSet;
80
81
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
82
  /// Indicator that this loop is no longer a valid loop.
83
  bool IsInvalid = false;
84
#endif
85
86
  LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
87
  const LoopBase<BlockT, LoopT> &
88
  operator=(const LoopBase<BlockT, LoopT> &) = delete;
89
90
public:
91
  /// Return the nesting level of this loop.  An outer-most loop has depth 1,
92
  /// for consistency with loop depth values used for basic blocks, where depth
93
  /// 0 is used for blocks not inside any loops.
94
3.53M
  unsigned getLoopDepth() const {
95
3.53M
    assert(!isInvalid() && "Loop not in a valid state!");
96
3.53M
    unsigned D = 1;
97
4.32M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
98
3.53M
         
CurLoop = CurLoop->ParentLoop782k
)
99
782k
      ++D;
100
3.53M
    return D;
101
3.53M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth() const
Line
Count
Source
94
1.09M
  unsigned getLoopDepth() const {
95
1.09M
    assert(!isInvalid() && "Loop not in a valid state!");
96
1.09M
    unsigned D = 1;
97
1.45M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
98
1.09M
         
CurLoop = CurLoop->ParentLoop364k
)
99
364k
      ++D;
100
1.09M
    return D;
101
1.09M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth() const
Line
Count
Source
94
2.44M
  unsigned getLoopDepth() const {
95
2.44M
    assert(!isInvalid() && "Loop not in a valid state!");
96
2.44M
    unsigned D = 1;
97
2.86M
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
98
2.44M
         
CurLoop = CurLoop->ParentLoop418k
)
99
418k
      ++D;
100
2.44M
    return D;
101
2.44M
  }
102
165M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getHeader() const
Line
Count
Source
102
150M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getHeader() const
Line
Count
Source
102
14.3M
  BlockT *getHeader() const { return getBlocks().front(); }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getHeader() const
Line
Count
Source
102
179
  BlockT *getHeader() const { return getBlocks().front(); }
103
43.7M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getParentLoop() const
Line
Count
Source
103
37.3M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getParentLoop() const
Line
Count
Source
103
6.41M
  LoopT *getParentLoop() const { return ParentLoop; }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getParentLoop() const
Line
Count
Source
103
137
  LoopT *getParentLoop() const { return ParentLoop; }
104
105
  /// This is a raw interface for bypassing addChildLoop.
106
1.09M
  void setParentLoop(LoopT *L) {
107
1.09M
    assert(!isInvalid() && "Loop not in a valid state!");
108
1.09M
    ParentLoop = L;
109
1.09M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::setParentLoop(llvm::Loop*)
Line
Count
Source
106
869k
  void setParentLoop(LoopT *L) {
107
869k
    assert(!isInvalid() && "Loop not in a valid state!");
108
869k
    ParentLoop = L;
109
869k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::setParentLoop(llvm::MachineLoop*)
Line
Count
Source
106
224k
  void setParentLoop(LoopT *L) {
107
224k
    assert(!isInvalid() && "Loop not in a valid state!");
108
224k
    ParentLoop = L;
109
224k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::setParentLoop(llvm::VPLoop*)
Line
Count
Source
106
9
  void setParentLoop(LoopT *L) {
107
9
    assert(!isInvalid() && "Loop not in a valid state!");
108
9
    ParentLoop = L;
109
9
  }
110
111
  /// Return true if the specified loop is contained within in this loop.
112
36.1M
  bool contains(const LoopT *L) const {
113
36.1M
    assert(!isInvalid() && "Loop not in a valid state!");
114
36.1M
    if (L == this)
115
23.9M
      return true;
116
12.2M
    if (!L)
117
2.89M
      return false;
118
9.35M
    return contains(L->getParentLoop());
119
9.35M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::Loop const*) const
Line
Count
Source
112
35.0M
  bool contains(const LoopT *L) const {
113
35.0M
    assert(!isInvalid() && "Loop not in a valid state!");
114
35.0M
    if (L == this)
115
23.2M
      return true;
116
11.7M
    if (!L)
117
2.71M
      return false;
118
9.06M
    return contains(L->getParentLoop());
119
9.06M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains(llvm::MachineLoop const*) const
Line
Count
Source
112
1.09M
  bool contains(const LoopT *L) const {
113
1.09M
    assert(!isInvalid() && "Loop not in a valid state!");
114
1.09M
    if (L == this)
115
625k
      return true;
116
473k
    if (!L)
117
181k
      return false;
118
292k
    return contains(L->getParentLoop());
119
292k
  }
120
121
  /// Return true if the specified basic block is in this loop.
122
353M
  bool contains(const BlockT *BB) const {
123
353M
    assert(!isInvalid() && "Loop not in a valid state!");
124
353M
    return DenseBlockSet.count(BB);
125
353M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::BasicBlock const*) const
Line
Count
Source
122
338M
  bool contains(const BlockT *BB) const {
123
338M
    assert(!isInvalid() && "Loop not in a valid state!");
124
338M
    return DenseBlockSet.count(BB);
125
338M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains(llvm::MachineBasicBlock const*) const
Line
Count
Source
122
14.9M
  bool contains(const BlockT *BB) const {
123
14.9M
    assert(!isInvalid() && "Loop not in a valid state!");
124
14.9M
    return DenseBlockSet.count(BB);
125
14.9M
  }
126
127
  /// Return true if the specified instruction is in this loop.
128
46.4M
  template <class InstT> bool contains(const InstT *Inst) const {
129
46.4M
    return contains(Inst->getParent());
130
46.4M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::Instruction>(llvm::Instruction const*) const
Line
Count
Source
128
44.2M
  template <class InstT> bool contains(const InstT *Inst) const {
129
44.2M
    return contains(Inst->getParent());
130
44.2M
  }
bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains<llvm::PHINode>(llvm::PHINode const*) const
Line
Count
Source
128
416k
  template <class InstT> bool contains(const InstT *Inst) const {
129
416k
    return contains(Inst->getParent());
130
416k
  }
bool llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::contains<llvm::MachineInstr>(llvm::MachineInstr const*) const
Line
Count
Source
128
1.80M
  template <class InstT> bool contains(const InstT *Inst) const {
129
1.80M
    return contains(Inst->getParent());
130
1.80M
  }
131
132
  /// Return the loops contained entirely within this loop.
133
19.9M
  const std::vector<LoopT *> &getSubLoops() const {
134
19.9M
    assert(!isInvalid() && "Loop not in a valid state!");
135
19.9M
    return SubLoops;
136
19.9M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoops() const
Line
Count
Source
133
17.3M
  const std::vector<LoopT *> &getSubLoops() const {
134
17.3M
    assert(!isInvalid() && "Loop not in a valid state!");
135
17.3M
    return SubLoops;
136
17.3M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoops() const
Line
Count
Source
133
2.61M
  const std::vector<LoopT *> &getSubLoops() const {
134
2.61M
    assert(!isInvalid() && "Loop not in a valid state!");
135
2.61M
    return SubLoops;
136
2.61M
  }
137
13.4M
  std::vector<LoopT *> &getSubLoopsVector() {
138
13.4M
    assert(!isInvalid() && "Loop not in a valid state!");
139
13.4M
    return SubLoops;
140
13.4M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoopsVector()
Line
Count
Source
137
10.6M
  std::vector<LoopT *> &getSubLoopsVector() {
138
10.6M
    assert(!isInvalid() && "Loop not in a valid state!");
139
10.6M
    return SubLoops;
140
10.6M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getSubLoopsVector()
Line
Count
Source
137
2.81M
  std::vector<LoopT *> &getSubLoopsVector() {
138
2.81M
    assert(!isInvalid() && "Loop not in a valid state!");
139
2.81M
    return SubLoops;
140
2.81M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getSubLoopsVector()
Line
Count
Source
137
111
  std::vector<LoopT *> &getSubLoopsVector() {
138
111
    assert(!isInvalid() && "Loop not in a valid state!");
139
111
    return SubLoops;
140
111
  }
141
  typedef typename std::vector<LoopT *>::const_iterator iterator;
142
  typedef
143
      typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
144
6.28M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
144
4.99M
  iterator begin() const { return getSubLoops().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
144
1.29M
  iterator begin() const { return getSubLoops().begin(); }
145
6.43M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
145
5.13M
  iterator end() const { return getSubLoops().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
145
1.29M
  iterator end() const { return getSubLoops().end(); }
146
1.76M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
146
1.76M
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
147
1.76M
  reverse_iterator rend() const { return getSubLoops().rend(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
147
1.76M
  reverse_iterator rend() const { return getSubLoops().rend(); }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
148
1.52M
  bool empty() const { return getSubLoops().empty(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
148
1.51M
  bool empty() const { return getSubLoops().empty(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
Line
Count
Source
148
6.50k
  bool empty() const { return getSubLoops().empty(); }
149
150
  /// Get a list of the basic blocks which make up this loop.
151
218M
  ArrayRef<BlockT *> getBlocks() const {
152
218M
    assert(!isInvalid() && "Loop not in a valid state!");
153
218M
    return Blocks;
154
218M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocks() const
Line
Count
Source
151
202M
  ArrayRef<BlockT *> getBlocks() const {
152
202M
    assert(!isInvalid() && "Loop not in a valid state!");
153
202M
    return Blocks;
154
202M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocks() const
Line
Count
Source
151
16.1M
  ArrayRef<BlockT *> getBlocks() const {
152
16.1M
    assert(!isInvalid() && "Loop not in a valid state!");
153
16.1M
    return Blocks;
154
16.1M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocks() const
Line
Count
Source
151
183
  ArrayRef<BlockT *> getBlocks() const {
152
183
    assert(!isInvalid() && "Loop not in a valid state!");
153
183
    return Blocks;
154
183
  }
155
  typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
156
25.6M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_begin() const
Line
Count
Source
156
25.0M
  block_iterator block_begin() const { return getBlocks().begin(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_begin() const
Line
Count
Source
156
581k
  block_iterator block_begin() const { return getBlocks().begin(); }
157
25.4M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::block_end() const
Line
Count
Source
157
24.8M
  block_iterator block_end() const { return getBlocks().end(); }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::block_end() const
Line
Count
Source
157
581k
  block_iterator block_end() const { return getBlocks().end(); }
158
22.6M
  inline iterator_range<block_iterator> blocks() const {
159
22.6M
    assert(!isInvalid() && "Loop not in a valid state!");
160
22.6M
    return make_range(block_begin(), block_end());
161
22.6M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::blocks() const
Line
Count
Source
158
22.2M
  inline iterator_range<block_iterator> blocks() const {
159
22.2M
    assert(!isInvalid() && "Loop not in a valid state!");
160
22.2M
    return make_range(block_begin(), block_end());
161
22.2M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::blocks() const
Line
Count
Source
158
352k
  inline iterator_range<block_iterator> blocks() const {
159
352k
    assert(!isInvalid() && "Loop not in a valid state!");
160
352k
    return make_range(block_begin(), block_end());
161
352k
  }
162
163
  /// Get the number of blocks in this loop in constant time.
164
  /// Invalidate the loop, indicating that it is no longer a loop.
165
2.24M
  unsigned getNumBlocks() const {
166
2.24M
    assert(!isInvalid() && "Loop not in a valid state!");
167
2.24M
    return Blocks.size();
168
2.24M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getNumBlocks() const
Line
Count
Source
165
84.9k
  unsigned getNumBlocks() const {
166
84.9k
    assert(!isInvalid() && "Loop not in a valid state!");
167
84.9k
    return Blocks.size();
168
84.9k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBlocks() const
Line
Count
Source
165
2.16M
  unsigned getNumBlocks() const {
166
2.16M
    assert(!isInvalid() && "Loop not in a valid state!");
167
2.16M
    return Blocks.size();
168
2.16M
  }
169
170
  /// Return a direct, mutable handle to the blocks vector so that we can
171
  /// mutate it efficiently with techniques like `std::remove`.
172
1.09M
  std::vector<BlockT *> &getBlocksVector() {
173
1.09M
    assert(!isInvalid() && "Loop not in a valid state!");
174
1.09M
    return Blocks;
175
1.09M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksVector()
Line
Count
Source
172
871k
  std::vector<BlockT *> &getBlocksVector() {
173
871k
    assert(!isInvalid() && "Loop not in a valid state!");
174
871k
    return Blocks;
175
871k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksVector()
Line
Count
Source
172
224k
  std::vector<BlockT *> &getBlocksVector() {
173
224k
    assert(!isInvalid() && "Loop not in a valid state!");
174
224k
    return Blocks;
175
224k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::getBlocksVector()
Line
Count
Source
172
9
  std::vector<BlockT *> &getBlocksVector() {
173
9
    assert(!isInvalid() && "Loop not in a valid state!");
174
9
    return Blocks;
175
9
  }
176
  /// Return a direct, mutable handle to the blocks set so that we can
177
  /// mutate it efficiently.
178
13.1k
  SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
179
13.1k
    assert(!isInvalid() && "Loop not in a valid state!");
180
13.1k
    return DenseBlockSet;
181
13.1k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksSet()
Line
Count
Source
178
13.1k
  SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
179
13.1k
    assert(!isInvalid() && "Loop not in a valid state!");
180
13.1k
    return DenseBlockSet;
181
13.1k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksSet()
182
183
  /// Return a direct, immutable handle to the blocks set.
184
0
  const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
185
0
    assert(!isInvalid() && "Loop not in a valid state!");
186
0
    return DenseBlockSet;
187
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocksSet() const
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getBlocksSet() const
188
189
  /// Return true if this loop is no longer valid.  The only valid use of this
190
  /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
191
  /// true by the destructor.  In other words, if this accessor returns true,
192
  /// the caller has already triggered UB by calling this accessor; and so it
193
  /// can only be called in a context where a return value of true indicates a
194
  /// programmer error.
195
20
  bool isInvalid() const {
196
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
197
    return IsInvalid;
198
#else
199
    return false;
200
20
#endif
201
20
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isInvalid() const
Line
Count
Source
195
20
  bool isInvalid() const {
196
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
197
    return IsInvalid;
198
#else
199
    return false;
200
20
#endif
201
20
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isInvalid() const
202
203
  /// True if terminator in the block can branch to another block that is
204
  /// outside of the current loop. \p BB must be inside the loop.
205
5.09M
  bool isLoopExiting(const BlockT *BB) const {
206
5.09M
    assert(!isInvalid() && "Loop not in a valid state!");
207
5.09M
    assert(contains(BB) && "Exiting block must be part of the loop");
208
7.54M
    for (const auto &Succ : children<const BlockT *>(BB)) {
209
7.54M
      if (!contains(Succ))
210
2.59M
        return true;
211
7.54M
    }
212
5.09M
    
return false2.50M
;
213
5.09M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopExiting(llvm::BasicBlock const*) const
Line
Count
Source
205
794k
  bool isLoopExiting(const BlockT *BB) const {
206
794k
    assert(!isInvalid() && "Loop not in a valid state!");
207
794k
    assert(contains(BB) && "Exiting block must be part of the loop");
208
1.14M
    for (const auto &Succ : children<const BlockT *>(BB)) {
209
1.14M
      if (!contains(Succ))
210
646k
        return true;
211
1.14M
    }
212
794k
    
return false147k
;
213
794k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopExiting(llvm::MachineBasicBlock const*) const
Line
Count
Source
205
4.30M
  bool isLoopExiting(const BlockT *BB) const {
206
4.30M
    assert(!isInvalid() && "Loop not in a valid state!");
207
4.30M
    assert(contains(BB) && "Exiting block must be part of the loop");
208
6.39M
    for (const auto &Succ : children<const BlockT *>(BB)) {
209
6.39M
      if (!contains(Succ))
210
1.94M
        return true;
211
6.39M
    }
212
4.30M
    
return false2.35M
;
213
4.30M
  }
214
215
  /// Returns true if \p BB is a loop-latch.
216
  /// A latch block is a block that contains a branch back to the header.
217
  /// This function is useful when there are multiple latches in a loop
218
  /// because \fn getLoopLatch will return nullptr in that case.
219
11.8k
  bool isLoopLatch(const BlockT *BB) const {
220
11.8k
    assert(!isInvalid() && "Loop not in a valid state!");
221
11.8k
    assert(contains(BB) && "block does not belong to the loop");
222
11.8k
223
11.8k
    BlockT *Header = getHeader();
224
11.8k
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
225
11.8k
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
226
11.8k
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
227
11.8k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::isLoopLatch(llvm::BasicBlock const*) const
Line
Count
Source
219
11.8k
  bool isLoopLatch(const BlockT *BB) const {
220
11.8k
    assert(!isInvalid() && "Loop not in a valid state!");
221
11.8k
    assert(contains(BB) && "block does not belong to the loop");
222
11.8k
223
11.8k
    BlockT *Header = getHeader();
224
11.8k
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
225
11.8k
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
226
11.8k
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
227
11.8k
  }
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
219
31
  bool isLoopLatch(const BlockT *BB) const {
220
31
    assert(!isInvalid() && "Loop not in a valid state!");
221
31
    assert(contains(BB) && "block does not belong to the loop");
222
31
223
31
    BlockT *Header = getHeader();
224
31
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
225
31
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
226
31
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
227
31
  }
228
229
  /// Calculate the number of back edges to the loop header.
230
606k
  unsigned getNumBackEdges() const {
231
606k
    assert(!isInvalid() && "Loop not in a valid state!");
232
606k
    unsigned NumBackEdges = 0;
233
606k
    BlockT *H = getHeader();
234
606k
235
606k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
236
1.22M
      if (contains(Pred))
237
618k
        ++NumBackEdges;
238
606k
239
606k
    return NumBackEdges;
240
606k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getNumBackEdges() const
Line
Count
Source
230
606k
  unsigned getNumBackEdges() const {
231
606k
    assert(!isInvalid() && "Loop not in a valid state!");
232
606k
    unsigned NumBackEdges = 0;
233
606k
    BlockT *H = getHeader();
234
606k
235
606k
    for (const auto Pred : children<Inverse<BlockT *>>(H))
236
1.22M
      if (contains(Pred))
237
618k
        ++NumBackEdges;
238
606k
239
606k
    return NumBackEdges;
240
606k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getNumBackEdges() const
241
242
  //===--------------------------------------------------------------------===//
243
  // APIs for simple analysis of the loop.
244
  //
245
  // Note that all of these methods can fail on general loops (ie, there may not
246
  // be a preheader, etc).  For best success, the loop simplification and
247
  // induction variable canonicalization pass should be used to normalize loops
248
  // for easy analysis.  These methods assume canonical loops.
249
250
  /// Return all blocks inside the loop that have successors outside of the
251
  /// loop. These are the blocks _inside of the current loop_ which branch out.
252
  /// The returned list is always unique.
253
  void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
254
255
  /// If getExitingBlocks would return exactly one block, return that block.
256
  /// Otherwise return null.
257
  BlockT *getExitingBlock() const;
258
259
  /// Return all of the successor blocks of this loop. These are the blocks
260
  /// _outside of the current loop_ which are branched to.
261
  void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
262
263
  /// If getExitBlocks would return exactly one block, return that block.
264
  /// Otherwise return null.
265
  BlockT *getExitBlock() const;
266
267
  /// Return true if no exit block for the loop has a predecessor that is
268
  /// outside the loop.
269
  bool hasDedicatedExits() const;
270
271
  /// Return all unique successor blocks of this loop.
272
  /// These are the blocks _outside of the current loop_ which are branched to.
273
  void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
274
275
  /// Return all unique successor blocks of this loop except successors from
276
  /// Latch block are not considered. If the exit comes from Latch has also
277
  /// non Latch predecessor in a loop it will be added to ExitBlocks.
278
  /// These are the blocks _outside of the current loop_ which are branched to.
279
  void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
280
281
  /// If getUniqueExitBlocks would return exactly one block, return that block.
282
  /// Otherwise return null.
283
  BlockT *getUniqueExitBlock() const;
284
285
  /// Edge type.
286
  typedef std::pair<BlockT *, BlockT *> Edge;
287
288
  /// Return all pairs of (_inside_block_,_outside_block_).
289
  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
290
291
  /// If there is a preheader for this loop, return it. A loop has a preheader
292
  /// if there is only one edge to the header of the loop from outside of the
293
  /// loop. If this is the case, the block branching to the header of the loop
294
  /// is the preheader node.
295
  ///
296
  /// This method returns null if there is no preheader for the loop.
297
  BlockT *getLoopPreheader() const;
298
299
  /// If the given loop's header has exactly one unique predecessor outside the
300
  /// loop, return it. Otherwise return null.
301
  ///  This is less strict that the loop "preheader" concept, which requires
302
  /// the predecessor to have exactly one successor.
303
  BlockT *getLoopPredecessor() const;
304
305
  /// If there is a single latch block for this loop, return it.
306
  /// A latch block is a block that contains a branch back to the header.
307
  BlockT *getLoopLatch() const;
308
309
  /// Return all loop latch blocks of this loop. A latch block is a block that
310
  /// contains a branch back to the header.
311
8.69M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
312
8.69M
    assert(!isInvalid() && "Loop not in a valid state!");
313
8.69M
    BlockT *H = getHeader();
314
8.69M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
315
17.9M
      if (contains(Pred))
316
8.70M
        LoopLatches.push_back(Pred);
317
8.69M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatches(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
311
8.69M
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
312
8.69M
    assert(!isInvalid() && "Loop not in a valid state!");
313
8.69M
    BlockT *H = getHeader();
314
8.69M
    for (const auto Pred : children<Inverse<BlockT *>>(H))
315
17.9M
      if (contains(Pred))
316
8.70M
        LoopLatches.push_back(Pred);
317
8.69M
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatches(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
318
319
  /// Return all inner loops in the loop nest rooted by the loop in preorder,
320
  /// with siblings in forward program order.
321
  template <class Type>
322
  static void getInnerLoopsInPreorder(const LoopT &L,
323
134k
                                      SmallVectorImpl<Type> &PreOrderLoops) {
324
134k
    SmallVector<LoopT *, 4> PreOrderWorklist;
325
134k
    PreOrderWorklist.append(L.rbegin(), L.rend());
326
134k
327
184k
    while (!PreOrderWorklist.empty()) {
328
50.5k
      LoopT *L = PreOrderWorklist.pop_back_val();
329
50.5k
      // Sub-loops are stored in forward program order, but will process the
330
50.5k
      // worklist backwards so append them in reverse order.
331
50.5k
      PreOrderWorklist.append(L->rbegin(), L->rend());
332
50.5k
      PreOrderLoops.push_back(L);
333
50.5k
    }
334
134k
  }
Unexecuted instantiation: void llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getInnerLoopsInPreorder<llvm::Loop const*>(llvm::Loop const&, llvm::SmallVectorImpl<llvm::Loop const*>&)
void llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getInnerLoopsInPreorder<llvm::Loop*>(llvm::Loop const&, llvm::SmallVectorImpl<llvm::Loop*>&)
Line
Count
Source
323
134k
                                      SmallVectorImpl<Type> &PreOrderLoops) {
324
134k
    SmallVector<LoopT *, 4> PreOrderWorklist;
325
134k
    PreOrderWorklist.append(L.rbegin(), L.rend());
326
134k
327
184k
    while (!PreOrderWorklist.empty()) {
328
50.5k
      LoopT *L = PreOrderWorklist.pop_back_val();
329
50.5k
      // Sub-loops are stored in forward program order, but will process the
330
50.5k
      // worklist backwards so append them in reverse order.
331
50.5k
      PreOrderWorklist.append(L->rbegin(), L->rend());
332
50.5k
      PreOrderLoops.push_back(L);
333
50.5k
    }
334
134k
  }
Unexecuted instantiation: void llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getInnerLoopsInPreorder<llvm::MachineLoop const*>(llvm::MachineLoop const&, llvm::SmallVectorImpl<llvm::MachineLoop const*>&)
Unexecuted instantiation: void llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getInnerLoopsInPreorder<llvm::MachineLoop*>(llvm::MachineLoop const&, llvm::SmallVectorImpl<llvm::MachineLoop*>&)
335
336
  /// Return all loops in the loop nest rooted by the loop in preorder, with
337
  /// siblings in forward program order.
338
0
  SmallVector<const LoopT *, 4> getLoopsInPreorder() const {
339
0
    SmallVector<const LoopT *, 4> PreOrderLoops;
340
0
    const LoopT *CurLoop = static_cast<const LoopT *>(this);
341
0
    PreOrderLoops.push_back(CurLoop);
342
0
    getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
343
0
    return PreOrderLoops;
344
0
  }
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder() const
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder() const
345
134k
  SmallVector<LoopT *, 4> getLoopsInPreorder() {
346
134k
    SmallVector<LoopT *, 4> PreOrderLoops;
347
134k
    LoopT *CurLoop = static_cast<LoopT *>(this);
348
134k
    PreOrderLoops.push_back(CurLoop);
349
134k
    getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
350
134k
    return PreOrderLoops;
351
134k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder()
Line
Count
Source
345
134k
  SmallVector<LoopT *, 4> getLoopsInPreorder() {
346
134k
    SmallVector<LoopT *, 4> PreOrderLoops;
347
134k
    LoopT *CurLoop = static_cast<LoopT *>(this);
348
134k
    PreOrderLoops.push_back(CurLoop);
349
134k
    getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
350
134k
    return PreOrderLoops;
351
134k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder()
352
353
  //===--------------------------------------------------------------------===//
354
  // APIs for updating loop information after changing the CFG
355
  //
356
357
  /// This method is used by other analyses to update loop information.
358
  /// NewBB is set to be a new member of the current loop.
359
  /// Because of this, it is added as a member of all parent loops, and is added
360
  /// to the specified LoopInfo object as being in the current basic block.  It
361
  /// is not valid to replace the loop header with this method.
362
  void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
363
364
  /// This is used when splitting loops up. It replaces the OldChild entry in
365
  /// our children list with NewChild, and updates the parent pointer of
366
  /// OldChild to be null and the NewChild to be this loop.
367
  /// This updates the loop depth of the new child.
368
  void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
369
370
  /// Add the specified loop to be a child of this loop.
371
  /// This updates the loop depth of the new child.
372
15.1k
  void addChildLoop(LoopT *NewChild) {
373
15.1k
    assert(!isInvalid() && "Loop not in a valid state!");
374
15.1k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
375
15.1k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
376
15.1k
    SubLoops.push_back(NewChild);
377
15.1k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addChildLoop(llvm::Loop*)
Line
Count
Source
372
15.1k
  void addChildLoop(LoopT *NewChild) {
373
15.1k
    assert(!isInvalid() && "Loop not in a valid state!");
374
15.1k
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
375
15.1k
    NewChild->ParentLoop = static_cast<LoopT *>(this);
376
15.1k
    SubLoops.push_back(NewChild);
377
15.1k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addChildLoop(llvm::MachineLoop*)
378
379
  /// This removes the specified child from being a subloop of this loop. The
380
  /// loop is not deleted, as it will presumably be inserted into another loop.
381
8.44k
  LoopT *removeChildLoop(iterator I) {
382
8.44k
    assert(!isInvalid() && "Loop not in a valid state!");
383
8.44k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
384
8.44k
    LoopT *Child = *I;
385
8.44k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
386
8.44k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
387
8.44k
    Child->ParentLoop = nullptr;
388
8.44k
    return Child;
389
8.44k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
381
8.44k
  LoopT *removeChildLoop(iterator I) {
382
8.44k
    assert(!isInvalid() && "Loop not in a valid state!");
383
8.44k
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
384
8.44k
    LoopT *Child = *I;
385
8.44k
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
386
8.44k
    SubLoops.erase(SubLoops.begin() + (I - begin()));
387
8.44k
    Child->ParentLoop = nullptr;
388
8.44k
    return Child;
389
8.44k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeChildLoop(std::__1::__wrap_iter<llvm::MachineLoop* const*>)
390
391
  /// This removes the specified child from being a subloop of this loop. The
392
  /// loop is not deleted, as it will presumably be inserted into another loop.
393
61
  LoopT *removeChildLoop(LoopT *Child) {
394
61
    return removeChildLoop(llvm::find(*this, Child));
395
61
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeChildLoop(llvm::Loop*)
Line
Count
Source
393
61
  LoopT *removeChildLoop(LoopT *Child) {
394
61
    return removeChildLoop(llvm::find(*this, Child));
395
61
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeChildLoop(llvm::MachineLoop*)
396
397
  /// This adds a basic block directly to the basic block list.
398
  /// This should only be used by transformations that create new loops.  Other
399
  /// transformations should use addBasicBlockToLoop.
400
14.3M
  void addBlockEntry(BlockT *BB) {
401
14.3M
    assert(!isInvalid() && "Loop not in a valid state!");
402
14.3M
    Blocks.push_back(BB);
403
14.3M
    DenseBlockSet.insert(BB);
404
14.3M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBlockEntry(llvm::BasicBlock*)
Line
Count
Source
400
11.5M
  void addBlockEntry(BlockT *BB) {
401
11.5M
    assert(!isInvalid() && "Loop not in a valid state!");
402
11.5M
    Blocks.push_back(BB);
403
11.5M
    DenseBlockSet.insert(BB);
404
11.5M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBlockEntry(llvm::MachineBasicBlock*)
Line
Count
Source
400
2.82M
  void addBlockEntry(BlockT *BB) {
401
2.82M
    assert(!isInvalid() && "Loop not in a valid state!");
402
2.82M
    Blocks.push_back(BB);
403
2.82M
    DenseBlockSet.insert(BB);
404
2.82M
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::addBlockEntry(llvm::VPBlockBase*)
Line
Count
Source
400
44
  void addBlockEntry(BlockT *BB) {
401
44
    assert(!isInvalid() && "Loop not in a valid state!");
402
44
    Blocks.push_back(BB);
403
44
    DenseBlockSet.insert(BB);
404
44
  }
405
406
  /// interface to reverse Blocks[from, end of loop] in this loop
407
4.11M
  void reverseBlock(unsigned from) {
408
4.11M
    assert(!isInvalid() && "Loop not in a valid state!");
409
4.11M
    std::reverse(Blocks.begin() + from, Blocks.end());
410
4.11M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reverseBlock(unsigned int)
Line
Count
Source
407
3.25M
  void reverseBlock(unsigned from) {
408
3.25M
    assert(!isInvalid() && "Loop not in a valid state!");
409
3.25M
    std::reverse(Blocks.begin() + from, Blocks.end());
410
3.25M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reverseBlock(unsigned int)
Line
Count
Source
407
863k
  void reverseBlock(unsigned from) {
408
863k
    assert(!isInvalid() && "Loop not in a valid state!");
409
863k
    std::reverse(Blocks.begin() + from, Blocks.end());
410
863k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reverseBlock(unsigned int)
Line
Count
Source
407
34
  void reverseBlock(unsigned from) {
408
34
    assert(!isInvalid() && "Loop not in a valid state!");
409
34
    std::reverse(Blocks.begin() + from, Blocks.end());
410
34
  }
411
412
  /// interface to do reserve() for Blocks
413
4.11M
  void reserveBlocks(unsigned size) {
414
4.11M
    assert(!isInvalid() && "Loop not in a valid state!");
415
4.11M
    Blocks.reserve(size);
416
4.11M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::reserveBlocks(unsigned int)
Line
Count
Source
413
3.25M
  void reserveBlocks(unsigned size) {
414
3.25M
    assert(!isInvalid() && "Loop not in a valid state!");
415
3.25M
    Blocks.reserve(size);
416
3.25M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::reserveBlocks(unsigned int)
Line
Count
Source
413
863k
  void reserveBlocks(unsigned size) {
414
863k
    assert(!isInvalid() && "Loop not in a valid state!");
415
863k
    Blocks.reserve(size);
416
863k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::reserveBlocks(unsigned int)
Line
Count
Source
413
34
  void reserveBlocks(unsigned size) {
414
34
    assert(!isInvalid() && "Loop not in a valid state!");
415
34
    Blocks.reserve(size);
416
34
  }
417
418
  /// This method is used to move BB (which must be part of this loop) to be the
419
  /// loop header of the loop (the block that dominates all others).
420
40.7k
  void moveToHeader(BlockT *BB) {
421
40.7k
    assert(!isInvalid() && "Loop not in a valid state!");
422
40.7k
    if (Blocks[0] == BB)
423
76
      return;
424
133k
    
for (unsigned i = 0;; 40.6k
++i93.1k
) {
425
133k
      assert(i != Blocks.size() && "Loop does not contain BB!");
426
133k
      if (Blocks[i] == BB) {
427
40.6k
        Blocks[i] = Blocks[0];
428
40.6k
        Blocks[0] = BB;
429
40.6k
        return;
430
40.6k
      }
431
133k
    }
432
40.6k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::moveToHeader(llvm::BasicBlock*)
Line
Count
Source
420
40.7k
  void moveToHeader(BlockT *BB) {
421
40.7k
    assert(!isInvalid() && "Loop not in a valid state!");
422
40.7k
    if (Blocks[0] == BB)
423
76
      return;
424
133k
    
for (unsigned i = 0;; 40.6k
++i93.1k
) {
425
133k
      assert(i != Blocks.size() && "Loop does not contain BB!");
426
133k
      if (Blocks[i] == BB) {
427
40.6k
        Blocks[i] = Blocks[0];
428
40.6k
        Blocks[0] = BB;
429
40.6k
        return;
430
40.6k
      }
431
133k
    }
432
40.6k
  }
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::moveToHeader(llvm::MachineBasicBlock*)
433
434
  /// This removes the specified basic block from the current loop, updating the
435
  /// Blocks as appropriate. This does not update the mapping in the LoopInfo
436
  /// class.
437
459k
  void removeBlockFromLoop(BlockT *BB) {
438
459k
    assert(!isInvalid() && "Loop not in a valid state!");
439
459k
    auto I = find(Blocks, BB);
440
459k
    assert(I != Blocks.end() && "N is not in this list!");
441
459k
    Blocks.erase(I);
442
459k
443
459k
    DenseBlockSet.erase(BB);
444
459k
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlockFromLoop(llvm::MachineBasicBlock*)
Line
Count
Source
437
33.2k
  void removeBlockFromLoop(BlockT *BB) {
438
33.2k
    assert(!isInvalid() && "Loop not in a valid state!");
439
33.2k
    auto I = find(Blocks, BB);
440
33.2k
    assert(I != Blocks.end() && "N is not in this list!");
441
33.2k
    Blocks.erase(I);
442
33.2k
443
33.2k
    DenseBlockSet.erase(BB);
444
33.2k
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::removeBlockFromLoop(llvm::BasicBlock*)
Line
Count
Source
437
426k
  void removeBlockFromLoop(BlockT *BB) {
438
426k
    assert(!isInvalid() && "Loop not in a valid state!");
439
426k
    auto I = find(Blocks, BB);
440
426k
    assert(I != Blocks.end() && "N is not in this list!");
441
426k
    Blocks.erase(I);
442
426k
443
426k
    DenseBlockSet.erase(BB);
444
426k
  }
445
446
  /// Verify loop structure
447
  void verifyLoop() const;
448
449
  /// Verify loop structure of this loop and all nested loops.
450
  void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
451
452
  /// Returns true if the loop is annotated parallel.
453
  ///
454
  /// Derived classes can override this method using static template
455
  /// polymorphism.
456
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
457
458
  /// Print loop with all the BBs inside it.
459
  void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const;
460
461
protected:
462
  friend class LoopInfoBase<BlockT, LoopT>;
463
464
  /// This creates an empty loop.
465
30.7k
  LoopBase() : ParentLoop(nullptr) {}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase()
Line
Count
Source
465
30.7k
  LoopBase() : ParentLoop(nullptr) {}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase()
466
467
4.11M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
468
4.11M
    Blocks.push_back(BB);
469
4.11M
    DenseBlockSet.insert(BB);
470
4.11M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::LoopBase(llvm::BasicBlock*)
Line
Count
Source
467
3.25M
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
468
3.25M
    Blocks.push_back(BB);
469
3.25M
    DenseBlockSet.insert(BB);
470
3.25M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopBase(llvm::MachineBasicBlock*)
Line
Count
Source
467
863k
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
468
863k
    Blocks.push_back(BB);
469
863k
    DenseBlockSet.insert(BB);
470
863k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::LoopBase(llvm::VPBlockBase*)
Line
Count
Source
467
34
  explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
468
34
    Blocks.push_back(BB);
469
34
    DenseBlockSet.insert(BB);
470
34
  }
471
472
  // Since loop passes like SCEV are allowed to key analysis results off of
473
  // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
474
  // This means loop passes should not be `delete` ing `Loop` objects directly
475
  // (and risk a later `Loop` allocation re-using the address of a previous one)
476
  // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
477
  // pointer till the end of the lifetime of the `LoopInfo` object.
478
  //
479
  // To make it easier to follow this rule, we mark the destructor as
480
  // non-public.
481
4.14M
  ~LoopBase() {
482
4.14M
    for (auto *SubLoop : SubLoops)
483
1.09M
      SubLoop->~LoopT();
484
4.14M
485
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
486
    IsInvalid = true;
487
#endif
488
    SubLoops.clear();
489
4.14M
    Blocks.clear();
490
4.14M
    DenseBlockSet.clear();
491
4.14M
    ParentLoop = nullptr;
492
4.14M
  }
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::~LoopBase()
Line
Count
Source
481
3.28M
  ~LoopBase() {
482
3.28M
    for (auto *SubLoop : SubLoops)
483
875k
      SubLoop->~LoopT();
484
3.28M
485
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
486
    IsInvalid = true;
487
#endif
488
    SubLoops.clear();
489
3.28M
    Blocks.clear();
490
3.28M
    DenseBlockSet.clear();
491
3.28M
    ParentLoop = nullptr;
492
3.28M
  }
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopBase()
Line
Count
Source
481
863k
  ~LoopBase() {
482
863k
    for (auto *SubLoop : SubLoops)
483
224k
      SubLoop->~LoopT();
484
863k
485
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
486
    IsInvalid = true;
487
#endif
488
    SubLoops.clear();
489
863k
    Blocks.clear();
490
863k
    DenseBlockSet.clear();
491
863k
    ParentLoop = nullptr;
492
863k
  }
llvm::LoopBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopBase()
Line
Count
Source
481
34
  ~LoopBase() {
482
34
    for (auto *SubLoop : SubLoops)
483
9
      SubLoop->~LoopT();
484
34
485
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
486
    IsInvalid = true;
487
#endif
488
    SubLoops.clear();
489
34
    Blocks.clear();
490
34
    DenseBlockSet.clear();
491
34
    ParentLoop = nullptr;
492
34
  }
493
};
494
495
template <class BlockT, class LoopT>
496
440
raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
497
440
  Loop.print(OS);
498
440
  return OS;
499
440
}
500
501
// Implementation in LoopInfoImpl.h
502
extern template class LoopBase<BasicBlock, Loop>;
503
504
/// Represents a single loop in the control flow graph.  Note that not all SCCs
505
/// in the CFG are necessarily loops.
506
class Loop : public LoopBase<BasicBlock, Loop> {
507
public:
508
  /// A range representing the start and end location of a loop.
509
  class LocRange {
510
    DebugLoc Start;
511
    DebugLoc End;
512
513
  public:
514
0
    LocRange() {}
515
683k
    LocRange(DebugLoc Start) : Start(Start), End(Start) {}
516
    LocRange(DebugLoc Start, DebugLoc End)
517
54.0k
        : Start(std::move(Start)), End(std::move(End)) {}
518
519
737k
    const DebugLoc &getStart() const { return Start; }
520
0
    const DebugLoc &getEnd() const { return End; }
521
522
    /// Check for null.
523
    ///
524
0
    explicit operator bool() const { return Start && End; }
525
  };
526
527
  /// Return true if the specified value is loop invariant.
528
  bool isLoopInvariant(const Value *V) const;
529
530
  /// Return true if all the operands of the specified instruction are loop
531
  /// invariant.
532
  bool hasLoopInvariantOperands(const Instruction *I) const;
533
534
  /// If the given value is an instruction inside of the loop and it can be
535
  /// hoisted, do so to make it trivially loop-invariant.
536
  /// Return true if the value after any hoisting is loop invariant. This
537
  /// function can be used as a slightly more aggressive replacement for
538
  /// isLoopInvariant.
539
  ///
540
  /// If InsertPt is specified, it is the point to hoist instructions to.
541
  /// If null, the terminator of the loop preheader is used.
542
  bool makeLoopInvariant(Value *V, bool &Changed,
543
                         Instruction *InsertPt = nullptr,
544
                         MemorySSAUpdater *MSSAU = nullptr) const;
545
546
  /// If the given instruction is inside of the loop and it can be hoisted, do
547
  /// so to make it trivially loop-invariant.
548
  /// Return true if the instruction after any hoisting is loop invariant. This
549
  /// function can be used as a slightly more aggressive replacement for
550
  /// isLoopInvariant.
551
  ///
552
  /// If InsertPt is specified, it is the point to hoist instructions to.
553
  /// If null, the terminator of the loop preheader is used.
554
  ///
555
  bool makeLoopInvariant(Instruction *I, bool &Changed,
556
                         Instruction *InsertPt = nullptr,
557
                         MemorySSAUpdater *MSSAU = nullptr) const;
558
559
  /// Check to see if the loop has a canonical induction variable: an integer
560
  /// recurrence that starts at 0 and increments by one each time through the
561
  /// loop. If so, return the phi node that corresponds to it.
562
  ///
563
  /// The IndVarSimplify pass transforms loops to have a canonical induction
564
  /// variable.
565
  ///
566
  PHINode *getCanonicalInductionVariable() const;
567
568
  /// Obtain the unique incoming and back edge. Return false if they are
569
  /// non-unique or the loop is dead; otherwise, return true.
570
  bool getIncomingAndBackEdge(BasicBlock *&Incoming,
571
                              BasicBlock *&Backedge) const;
572
573
  /// Below are some utilities to get loop bounds and induction variable, and
574
  /// check if a given phinode is an auxiliary induction variable, as well as
575
  /// checking if the loop is canonical.
576
  ///
577
  /// Here is an example:
578
  /// \code
579
  /// for (int i = lb; i < ub; i+=step)
580
  ///   <loop body>
581
  /// --- pseudo LLVMIR ---
582
  /// beforeloop:
583
  ///   guardcmp = (lb < ub)
584
  ///   if (guardcmp) goto preheader; else goto afterloop
585
  /// preheader:
586
  /// loop:
587
  ///   i_1 = phi[{lb, preheader}, {i_2, latch}]
588
  ///   <loop body>
589
  ///   i_2 = i_1 + step
590
  /// latch:
591
  ///   cmp = (i_2 < ub)
592
  ///   if (cmp) goto loop
593
  /// exit:
594
  /// afterloop:
595
  /// \endcode
596
  ///
597
  /// - getBounds
598
  ///   - getInitialIVValue      --> lb
599
  ///   - getStepInst            --> i_2 = i_1 + step
600
  ///   - getStepValue           --> step
601
  ///   - getFinalIVValue        --> ub
602
  ///   - getCanonicalPredicate  --> '<'
603
  ///   - getDirection           --> Increasing
604
  ///
605
  /// - getInductionVariable            --> i_1
606
  /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
607
  /// - isCanonical                     --> false
608
  struct LoopBounds {
609
    /// Return the LoopBounds object if
610
    /// - the given \p IndVar is an induction variable
611
    /// - the initial value of the induction variable can be found
612
    /// - the step instruction of the induction variable can be found
613
    /// - the final value of the induction variable can be found
614
    ///
615
    /// Else None.
616
    static Optional<Loop::LoopBounds> getBounds(const Loop &L, PHINode &IndVar,
617
                                                ScalarEvolution &SE);
618
619
    /// Get the initial value of the loop induction variable.
620
    Value &getInitialIVValue() const { return InitialIVValue; }
621
622
    /// Get the instruction that updates the loop induction variable.
623
54
    Instruction &getStepInst() const { return StepInst; }
624
625
    /// Get the step that the loop induction variable gets updated by in each
626
    /// loop iteration. Return nullptr if not found.
627
    Value *getStepValue() const { return StepValue; }
628
629
    /// Get the final value of the loop induction variable.
630
32
    Value &getFinalIVValue() const { return FinalIVValue; }
631
632
    /// Return the canonical predicate for the latch compare instruction, if
633
    /// able to be calcuated. Else BAD_ICMP_PREDICATE.
634
    ///
635
    /// A predicate is considered as canonical if requirements below are all
636
    /// satisfied:
637
    /// 1. The first successor of the latch branch is the loop header
638
    ///    If not, inverse the predicate.
639
    /// 2. One of the operands of the latch comparison is StepInst
640
    ///    If not, and
641
    ///    - if the current calcuated predicate is not ne or eq, flip the
642
    ///      predicate.
643
    ///    - else if the loop is increasing, return slt
644
    ///      (notice that it is safe to change from ne or eq to sign compare)
645
    ///    - else if the loop is decreasing, return sgt
646
    ///      (notice that it is safe to change from ne or eq to sign compare)
647
    ///
648
    /// Here is an example when both (1) and (2) are not satisfied:
649
    /// \code
650
    /// loop.header:
651
    ///  %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
652
    ///  %inc = add %iv, %step
653
    ///  %cmp = slt %iv, %finaliv
654
    ///  br %cmp, %loop.exit, %loop.header
655
    /// loop.exit:
656
    /// \endcode
657
    /// - The second successor of the latch branch is the loop header instead
658
    ///   of the first successor (slt -> sge)
659
    /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv)
660
    ///   instead of the StepInst (%inc) (sge -> sgt)
661
    ///
662
    /// The predicate would be sgt if both (1) and (2) are satisfied.
663
    /// getCanonicalPredicate() returns sgt for this example.
664
    /// Note: The IR is not changed.
665
    ICmpInst::Predicate getCanonicalPredicate() const;
666
667
    /// An enum for the direction of the loop
668
    /// - for (int i = 0; i < ub; ++i)  --> Increasing
669
    /// - for (int i = ub; i > 0; --i)  --> Descresing
670
    /// - for (int i = x; i != y; i+=z) --> Unknown
671
    enum class Direction { Increasing, Decreasing, Unknown };
672
673
    /// Get the direction of the loop.
674
    Direction getDirection() const;
675
676
  private:
677
    LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,
678
               ScalarEvolution &SE)
679
        : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),
680
16
          FinalIVValue(F), SE(SE) {}
681
682
    const Loop &L;
683
684
    // The initial value of the loop induction variable
685
    Value &InitialIVValue;
686
687
    // The instruction that updates the loop induction variable
688
    Instruction &StepInst;
689
690
    // The value that the loop induction variable gets updated by in each loop
691
    // iteration
692
    Value *StepValue;
693
694
    // The final value of the loop induction variable
695
    Value &FinalIVValue;
696
697
    ScalarEvolution &SE;
698
  };
699
700
  /// Return the struct LoopBounds collected if all struct members are found,
701
  /// else None.
702
  Optional<LoopBounds> getBounds(ScalarEvolution &SE) const;
703
704
  /// Return the loop induction variable if found, else return nullptr.
705
  /// An instruction is considered as the loop induction variable if
706
  /// - it is an induction variable of the loop; and
707
  /// - it is used to determine the condition of the branch in the loop latch
708
  ///
709
  /// Note: the induction variable doesn't need to be canonical, i.e. starts at
710
  /// zero and increments by one each time through the loop (but it can be).
711
  PHINode *getInductionVariable(ScalarEvolution &SE) const;
712
713
  /// Get the loop induction descriptor for the loop induction variable. Return
714
  /// true if the loop induction variable is found.
715
  bool getInductionDescriptor(ScalarEvolution &SE,
716
                              InductionDescriptor &IndDesc) const;
717
718
  /// Return true if the given PHINode \p AuxIndVar is
719
  /// - in the loop header
720
  /// - not used outside of the loop
721
  /// - incremented by a loop invariant step for each loop iteration
722
  /// - step instruction opcode should be add or sub
723
  /// Note: auxiliary induction variable is not required to be used in the
724
  ///       conditional branch in the loop latch. (but it can be)
725
  bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
726
                                    ScalarEvolution &SE) const;
727
728
  /// Return true if the loop induction variable starts at zero and increments
729
  /// by one each time through the loop.
730
  bool isCanonical(ScalarEvolution &SE) const;
731
732
  /// Return true if the Loop is in LCSSA form.
733
  bool isLCSSAForm(DominatorTree &DT) const;
734
735
  /// Return true if this Loop and all inner subloops are in LCSSA form.
736
  bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
737
738
  /// Return true if the Loop is in the form that the LoopSimplify form
739
  /// transforms loops to, which is sometimes called normal form.
740
  bool isLoopSimplifyForm() const;
741
742
  /// Return true if the loop body is safe to clone in practice.
743
  bool isSafeToClone() const;
744
745
  /// Returns true if the loop is annotated parallel.
746
  ///
747
  /// A parallel loop can be assumed to not contain any dependencies between
748
  /// iterations by the compiler. That is, any loop-carried dependency checking
749
  /// can be skipped completely when parallelizing the loop on the target
750
  /// machine. Thus, if the parallel loop information originates from the
751
  /// programmer, e.g. via the OpenMP parallel for pragma, it is the
752
  /// programmer's responsibility to ensure there are no loop-carried
753
  /// dependencies. The final execution order of the instructions across
754
  /// iterations is not guaranteed, thus, the end result might or might not
755
  /// implement actual concurrent execution of instructions across multiple
756
  /// iterations.
757
  bool isAnnotatedParallel() const;
758
759
  /// Return the llvm.loop loop id metadata node for this loop if it is present.
760
  ///
761
  /// If this loop contains the same llvm.loop metadata on each branch to the
762
  /// header then the node is returned. If any latch instruction does not
763
  /// contain llvm.loop or if multiple latches contain different nodes then
764
  /// 0 is returned.
765
  MDNode *getLoopID() const;
766
  /// Set the llvm.loop loop id metadata for this loop.
767
  ///
768
  /// The LoopID metadata node will be added to each terminator instruction in
769
  /// the loop that branches to the loop header.
770
  ///
771
  /// The LoopID metadata node should have one or more operands and the first
772
  /// operand should be the node itself.
773
  void setLoopID(MDNode *LoopID) const;
774
775
  /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
776
  ///
777
  /// Remove existing unroll metadata and add unroll disable metadata to
778
  /// indicate the loop has already been unrolled.  This prevents a loop
779
  /// from being unrolled more than is directed by a pragma if the loop
780
  /// unrolling pass is run more than once (which it generally is).
781
  void setLoopAlreadyUnrolled();
782
783
  void dump() const;
784
  void dumpVerbose() const;
785
786
  /// Return the debug location of the start of this loop.
787
  /// This looks for a BB terminating instruction with a known debug
788
  /// location by looking at the preheader and header blocks. If it
789
  /// cannot find a terminating instruction with location information,
790
  /// it returns an unknown location.
791
  DebugLoc getStartLoc() const;
792
793
  /// Return the source code span of the loop.
794
  LocRange getLocRange() const;
795
796
300k
  StringRef getName() const {
797
300k
    if (BasicBlock *Header = getHeader())
798
300k
      if (Header->hasName())
799
115k
        return Header->getName();
800
184k
    return "<unnamed loop>";
801
184k
  }
802
803
private:
804
30.7k
  Loop() = default;
805
806
  friend class LoopInfoBase<BasicBlock, Loop>;
807
  friend class LoopBase<BasicBlock, Loop>;
808
3.25M
  explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
809
3.28M
  ~Loop() = default;
810
};
811
812
//===----------------------------------------------------------------------===//
813
/// This class builds and contains all of the top-level loop
814
/// structures in the specified function.
815
///
816
817
template <class BlockT, class LoopT> class LoopInfoBase {
818
  // BBMap - Mapping of basic blocks to the inner most loop they occur in
819
  DenseMap<const BlockT *, LoopT *> BBMap;
820
  std::vector<LoopT *> TopLevelLoops;
821
  BumpPtrAllocator LoopAllocator;
822
823
  friend class LoopBase<BlockT, LoopT>;
824
  friend class LoopInfo;
825
826
  void operator=(const LoopInfoBase &) = delete;
827
  LoopInfoBase(const LoopInfoBase &) = delete;
828
829
public:
830
777k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase()
Line
Count
Source
830
353k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopInfoBase()
Line
Count
Source
830
384k
  LoopInfoBase() {}
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::LoopInfoBase()
Line
Count
Source
830
38.5k
  LoopInfoBase() {}
831
786k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::~LoopInfoBase()
Line
Count
Source
831
363k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::~LoopInfoBase()
Line
Count
Source
831
383k
  ~LoopInfoBase() { releaseMemory(); }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::~LoopInfoBase()
Line
Count
Source
831
38.5k
  ~LoopInfoBase() { releaseMemory(); }
832
833
  LoopInfoBase(LoopInfoBase &&Arg)
834
      : BBMap(std::move(Arg.BBMap)),
835
        TopLevelLoops(std::move(Arg.TopLevelLoops)),
836
10.4k
        LoopAllocator(std::move(Arg.LoopAllocator)) {
837
10.4k
    // We have to clear the arguments top level loops as we've taken ownership.
838
10.4k
    Arg.TopLevelLoops.clear();
839
10.4k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::LoopInfoBase(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&&)
Line
Count
Source
836
10.4k
        LoopAllocator(std::move(Arg.LoopAllocator)) {
837
10.4k
    // We have to clear the arguments top level loops as we've taken ownership.
838
10.4k
    Arg.TopLevelLoops.clear();
839
10.4k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::LoopInfoBase(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&&)
840
0
  LoopInfoBase &operator=(LoopInfoBase &&RHS) {
841
0
    BBMap = std::move(RHS.BBMap);
842
0
843
0
    for (auto *L : TopLevelLoops)
844
0
      L->~LoopT();
845
0
846
0
    TopLevelLoops = std::move(RHS.TopLevelLoops);
847
0
    LoopAllocator = std::move(RHS.LoopAllocator);
848
0
    RHS.TopLevelLoops.clear();
849
0
    return *this;
850
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>&&)
851
852
19.3M
  void releaseMemory() {
853
19.3M
    BBMap.clear();
854
19.3M
855
19.3M
    for (auto *L : TopLevelLoops)
856
3.02M
      L->~LoopT();
857
19.3M
    TopLevelLoops.clear();
858
19.3M
    LoopAllocator.Reset();
859
19.3M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::releaseMemory()
Line
Count
Source
852
14.7M
  void releaseMemory() {
853
14.7M
    BBMap.clear();
854
14.7M
855
14.7M
    for (auto *L : TopLevelLoops)
856
2.38M
      L->~LoopT();
857
14.7M
    TopLevelLoops.clear();
858
14.7M
    LoopAllocator.Reset();
859
14.7M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::releaseMemory()
Line
Count
Source
852
4.63M
  void releaseMemory() {
853
4.63M
    BBMap.clear();
854
4.63M
855
4.63M
    for (auto *L : TopLevelLoops)
856
638k
      L->~LoopT();
857
4.63M
    TopLevelLoops.clear();
858
4.63M
    LoopAllocator.Reset();
859
4.63M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::releaseMemory()
Line
Count
Source
852
38.5k
  void releaseMemory() {
853
38.5k
    BBMap.clear();
854
38.5k
855
38.5k
    for (auto *L : TopLevelLoops)
856
25
      L->~LoopT();
857
38.5k
    TopLevelLoops.clear();
858
38.5k
    LoopAllocator.Reset();
859
38.5k
  }
860
861
4.14M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
862
4.14M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
863
4.14M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
864
4.14M
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<llvm::BasicBlock*&>(llvm::BasicBlock*&&&)
Line
Count
Source
861
3.25M
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
862
3.25M
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
863
3.25M
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
864
3.25M
  }
llvm::MachineLoop* llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::AllocateLoop<llvm::MachineBasicBlock*&>(llvm::MachineBasicBlock*&&&)
Line
Count
Source
861
863k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
862
863k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
863
863k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
864
863k
  }
llvm::Loop* llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::AllocateLoop<>()
Line
Count
Source
861
30.7k
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
862
30.7k
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
863
30.7k
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
864
30.7k
  }
llvm::VPLoop* llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::AllocateLoop<llvm::VPBlockBase*&>(llvm::VPBlockBase*&&&)
Line
Count
Source
861
34
  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
862
34
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
863
34
    return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
864
34
  }
865
866
  /// iterator/begin/end - The interface to the top-level loops in the current
867
  /// function.
868
  ///
869
  typedef typename std::vector<LoopT *>::const_iterator iterator;
870
  typedef
871
      typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
872
10.3M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::begin() const
Line
Count
Source
872
2.07M
  iterator begin() const { return TopLevelLoops.begin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::begin() const
Line
Count
Source
872
8.24M
  iterator begin() const { return TopLevelLoops.begin(); }
873
10.2M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::end() const
Line
Count
Source
873
2.07M
  iterator end() const { return TopLevelLoops.end(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::end() const
Line
Count
Source
873
8.20M
  iterator end() const { return TopLevelLoops.end(); }
874
3.32M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rbegin() const
Line
Count
Source
874
3.32M
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rbegin() const
875
3.32M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::rend() const
Line
Count
Source
875
3.32M
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::rend() const
876
4.34M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::empty() const
Line
Count
Source
876
2.03M
  bool empty() const { return TopLevelLoops.empty(); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::empty() const
Line
Count
Source
876
2.31M
  bool empty() const { return TopLevelLoops.empty(); }
877
878
  /// Return all of the loops in the function in preorder across the loop
879
  /// nests, with siblings in forward program order.
880
  ///
881
  /// Note that because loops form a forest of trees, preorder is equivalent to
882
  /// reverse postorder.
883
  SmallVector<LoopT *, 4> getLoopsInPreorder();
884
885
  /// Return all of the loops in the function in preorder across the loop
886
  /// nests, with siblings in *reverse* program order.
887
  ///
888
  /// Note that because loops form a forest of trees, preorder is equivalent to
889
  /// reverse postorder.
890
  ///
891
  /// Also note that this is *not* a reverse preorder. Only the siblings are in
892
  /// reverse program order.
893
  SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();
894
895
  /// Return the inner most loop that BB lives in. If a basic block is in no
896
  /// loop (for example the entry node), null is returned.
897
205M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopFor(llvm::BasicBlock const*) const
Line
Count
Source
897
144M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopFor(llvm::MachineBasicBlock const*) const
Line
Count
Source
897
60.8M
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::getLoopFor(llvm::VPBlockBase const*) const
Line
Count
Source
897
278
  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
898
899
  /// Same as getLoopFor.
900
1.07M
  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::operator[](llvm::BasicBlock const*) const
Line
Count
Source
900
1.07M
  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::operator[](llvm::MachineBasicBlock const*) const
901
902
  /// Return the loop nesting level of the specified block. A depth of 0 means
903
  /// the block is not inside any loop.
904
6.54M
  unsigned getLoopDepth(const BlockT *BB) const {
905
6.54M
    const LoopT *L = getLoopFor(BB);
906
6.54M
    return L ? 
L->getLoopDepth()2.36M
:
04.17M
;
907
6.54M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopDepth(llvm::MachineBasicBlock const*) const
Line
Count
Source
904
5.07M
  unsigned getLoopDepth(const BlockT *BB) const {
905
5.07M
    const LoopT *L = getLoopFor(BB);
906
5.07M
    return L ? 
L->getLoopDepth()984k
:
04.09M
;
907
5.07M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopDepth(llvm::BasicBlock const*) const
Line
Count
Source
904
1.46M
  unsigned getLoopDepth(const BlockT *BB) const {
905
1.46M
    const LoopT *L = getLoopFor(BB);
906
1.46M
    return L ? 
L->getLoopDepth()1.38M
:
083.8k
;
907
1.46M
  }
908
909
  // True if the block is a loop header node
910
4.87M
  bool isLoopHeader(const BlockT *BB) const {
911
4.87M
    const LoopT *L = getLoopFor(BB);
912
4.87M
    return L && 
L->getHeader() == BB1.52M
;
913
4.87M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::isLoopHeader(llvm::MachineBasicBlock const*) const
Line
Count
Source
910
3.43M
  bool isLoopHeader(const BlockT *BB) const {
911
3.43M
    const LoopT *L = getLoopFor(BB);
912
3.43M
    return L && 
L->getHeader() == BB737k
;
913
3.43M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::isLoopHeader(llvm::BasicBlock const*) const
Line
Count
Source
910
1.43M
  bool isLoopHeader(const BlockT *BB) const {
911
1.43M
    const LoopT *L = getLoopFor(BB);
912
1.43M
    return L && 
L->getHeader() == BB784k
;
913
1.43M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::isLoopHeader(llvm::VPBlockBase const*) const
Line
Count
Source
910
16
  bool isLoopHeader(const BlockT *BB) const {
911
16
    const LoopT *L = getLoopFor(BB);
912
16
    return L && 
L->getHeader() == BB14
;
913
16
  }
914
915
  /// This removes the specified top-level loop from this loop info object.
916
  /// The loop is not deleted, as it will presumably be inserted into
917
  /// another loop.
918
18.6k
  LoopT *removeLoop(iterator I) {
919
18.6k
    assert(I != end() && "Cannot remove end iterator!");
920
18.6k
    LoopT *L = *I;
921
18.6k
    assert(!L->getParentLoop() && "Not a top-level loop!");
922
18.6k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
923
18.6k
    return L;
924
18.6k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeLoop(std::__1::__wrap_iter<llvm::MachineLoop* const*>)
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeLoop(std::__1::__wrap_iter<llvm::Loop* const*>)
Line
Count
Source
918
18.6k
  LoopT *removeLoop(iterator I) {
919
18.6k
    assert(I != end() && "Cannot remove end iterator!");
920
18.6k
    LoopT *L = *I;
921
18.6k
    assert(!L->getParentLoop() && "Not a top-level loop!");
922
18.6k
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
923
18.6k
    return L;
924
18.6k
  }
925
926
  /// Change the top-level loop that contains BB to the specified loop.
927
  /// This should be used by transformations that restructure the loop hierarchy
928
  /// tree.
929
13.1M
  void changeLoopFor(BlockT *BB, LoopT *L) {
930
13.1M
    if (!L) {
931
88.0k
      BBMap.erase(BB);
932
88.0k
      return;
933
88.0k
    }
934
13.0M
    BBMap[BB] = L;
935
13.0M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::changeLoopFor(llvm::MachineBasicBlock*, llvm::MachineLoop*)
Line
Count
Source
929
2.70M
  void changeLoopFor(BlockT *BB, LoopT *L) {
930
2.70M
    if (!L) {
931
0
      BBMap.erase(BB);
932
0
      return;
933
0
    }
934
2.70M
    BBMap[BB] = L;
935
2.70M
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeLoopFor(llvm::BasicBlock*, llvm::Loop*)
Line
Count
Source
929
10.4M
  void changeLoopFor(BlockT *BB, LoopT *L) {
930
10.4M
    if (!L) {
931
88.0k
      BBMap.erase(BB);
932
88.0k
      return;
933
88.0k
    }
934
10.3M
    BBMap[BB] = L;
935
10.3M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::changeLoopFor(llvm::VPBlockBase*, llvm::VPLoop*)
Line
Count
Source
929
61
  void changeLoopFor(BlockT *BB, LoopT *L) {
930
61
    if (!L) {
931
0
      BBMap.erase(BB);
932
0
      return;
933
0
    }
934
61
    BBMap[BB] = L;
935
61
  }
936
937
  /// Replace the specified loop in the top-level loops list with the indicated
938
  /// loop.
939
293
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
940
293
    auto I = find(TopLevelLoops, OldLoop);
941
293
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
942
293
    *I = NewLoop;
943
293
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
944
293
           "Loops already embedded into a subloop!");
945
293
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::changeTopLevelLoop(llvm::MachineLoop*, llvm::MachineLoop*)
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::changeTopLevelLoop(llvm::Loop*, llvm::Loop*)
Line
Count
Source
939
293
  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
940
293
    auto I = find(TopLevelLoops, OldLoop);
941
293
    assert(I != TopLevelLoops.end() && "Old loop not at top level!");
942
293
    *I = NewLoop;
943
293
    assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
944
293
           "Loops already embedded into a subloop!");
945
293
  }
946
947
  /// This adds the specified loop to the collection of top-level loops.
948
3.04M
  void addTopLevelLoop(LoopT *New) {
949
3.04M
    assert(!New->getParentLoop() && "Loop already in subloop!");
950
3.04M
    TopLevelLoops.push_back(New);
951
3.04M
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addTopLevelLoop(llvm::MachineLoop*)
Line
Count
Source
948
638k
  void addTopLevelLoop(LoopT *New) {
949
638k
    assert(!New->getParentLoop() && "Loop already in subloop!");
950
638k
    TopLevelLoops.push_back(New);
951
638k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::addTopLevelLoop(llvm::Loop*)
Line
Count
Source
948
2.40M
  void addTopLevelLoop(LoopT *New) {
949
2.40M
    assert(!New->getParentLoop() && "Loop already in subloop!");
950
2.40M
    TopLevelLoops.push_back(New);
951
2.40M
  }
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::addTopLevelLoop(llvm::VPLoop*)
Line
Count
Source
948
25
  void addTopLevelLoop(LoopT *New) {
949
25
    assert(!New->getParentLoop() && "Loop already in subloop!");
950
25
    TopLevelLoops.push_back(New);
951
25
  }
952
953
  /// This method completely removes BB from all data structures,
954
  /// including all of the Loop objects it is nested in and our mapping from
955
  /// BasicBlocks to loops.
956
372k
  void removeBlock(BlockT *BB) {
957
372k
    auto I = BBMap.find(BB);
958
372k
    if (I != BBMap.end()) {
959
758k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()452k
)
960
452k
        L->removeBlockFromLoop(BB);
961
305k
962
305k
      BBMap.erase(I);
963
305k
    }
964
372k
  }
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::removeBlock(llvm::MachineBasicBlock*)
Line
Count
Source
956
62.5k
  void removeBlock(BlockT *BB) {
957
62.5k
    auto I = BBMap.find(BB);
958
62.5k
    if (I != BBMap.end()) {
959
52.8k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()33.2k
)
960
33.2k
        L->removeBlockFromLoop(BB);
961
19.6k
962
19.6k
      BBMap.erase(I);
963
19.6k
    }
964
62.5k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::removeBlock(llvm::BasicBlock*)
Line
Count
Source
956
309k
  void removeBlock(BlockT *BB) {
957
309k
    auto I = BBMap.find(BB);
958
309k
    if (I != BBMap.end()) {
959
705k
      for (LoopT *L = I->second; L; 
L = L->getParentLoop()419k
)
960
419k
        L->removeBlockFromLoop(BB);
961
286k
962
286k
      BBMap.erase(I);
963
286k
    }
964
309k
  }
965
966
  // Internals
967
968
  static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
969
0
                                      const LoopT *ParentLoop) {
970
0
    if (!SubLoop)
971
0
      return true;
972
0
    if (SubLoop == ParentLoop)
973
0
      return false;
974
0
    return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
975
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*)
976
977
  /// Create the loop forest using a stable algorithm.
978
  void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
979
980
  // Debugging
981
  void print(raw_ostream &OS) const;
982
983
  void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
984
985
  /// Destroy a loop that has been removed from the `LoopInfo` nest.
986
  ///
987
  /// This runs the destructor of the loop object making it invalid to
988
  /// reference afterward. The memory is retained so that the *pointer* to the
989
  /// loop remains valid.
990
  ///
991
  /// The caller is responsible for removing this loop from the loop nest and
992
  /// otherwise disconnecting it from the broader `LoopInfo` data structures.
993
  /// Callers that don't naturally handle this themselves should probably call
994
  /// `erase' instead.
995
25.1k
  void destroy(LoopT *L) {
996
25.1k
    L->~LoopT();
997
25.1k
998
25.1k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
999
25.1k
    // \c L, but the pointer remains valid for non-dereferencing uses.
1000
25.1k
    LoopAllocator.Deallocate(L);
1001
25.1k
  }
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::destroy(llvm::Loop*)
Line
Count
Source
995
25.1k
  void destroy(LoopT *L) {
996
25.1k
    L->~LoopT();
997
25.1k
998
25.1k
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
999
25.1k
    // \c L, but the pointer remains valid for non-dereferencing uses.
1000
25.1k
    LoopAllocator.Deallocate(L);
1001
25.1k
  }
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::destroy(llvm::MachineLoop*)
1002
};
1003
1004
// Implementation in LoopInfoImpl.h
1005
extern template class LoopInfoBase<BasicBlock, Loop>;
1006
1007
class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
1008
  typedef LoopInfoBase<BasicBlock, Loop> BaseT;
1009
1010
  friend class LoopBase<BasicBlock, Loop>;
1011
1012
  void operator=(const LoopInfo &) = delete;
1013
  LoopInfo(const LoopInfo &) = delete;
1014
1015
public:
1016
350k
  LoopInfo() {}
1017
  explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
1018
1019
10.4k
  LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
1020
0
  LoopInfo &operator=(LoopInfo &&RHS) {
1021
0
    BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
1022
0
    return *this;
1023
0
  }
1024
1025
  /// Handle invalidation explicitly.
1026
  bool invalidate(Function &F, const PreservedAnalyses &PA,
1027
                  FunctionAnalysisManager::Invalidator &);
1028
1029
  // Most of the public interface is provided via LoopInfoBase.
1030
1031
  /// Update LoopInfo after removing the last backedge from a loop. This updates
1032
  /// the loop forest and parent loops for each block so that \c L is no longer
1033
  /// referenced, but does not actually delete \c L immediately. The pointer
1034
  /// will remain valid until this LoopInfo's memory is released.
1035
  void erase(Loop *L);
1036
1037
  /// Returns true if replacing From with To everywhere is guaranteed to
1038
  /// preserve LCSSA form.
1039
589k
  bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
1040
589k
    // Preserving LCSSA form is only problematic if the replacing value is an
1041
589k
    // instruction.
1042
589k
    Instruction *I = dyn_cast<Instruction>(To);
1043
589k
    if (!I)
1044
532k
      return true;
1045
57.2k
    // If both instructions are defined in the same basic block then replacement
1046
57.2k
    // cannot break LCSSA form.
1047
57.2k
    if (I->getParent() == From->getParent())
1048
5.25k
      return true;
1049
51.9k
    // If the instruction is not defined in a loop then it can safely replace
1050
51.9k
    // anything.
1051
51.9k
    Loop *ToLoop = getLoopFor(I->getParent());
1052
51.9k
    if (!ToLoop)
1053
4.04k
      return true;
1054
47.9k
    // If the replacing instruction is defined in the same loop as the original
1055
47.9k
    // instruction, or in a loop that contains it as an inner loop, then using
1056
47.9k
    // it as a replacement will not break LCSSA form.
1057
47.9k
    return ToLoop->contains(getLoopFor(From->getParent()));
1058
47.9k
  }
1059
1060
  /// Checks if moving a specific instruction can break LCSSA in any loop.
1061
  ///
1062
  /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
1063
  /// assuming that the function containing \p Inst and \p NewLoc is currently
1064
  /// in LCSSA form.
1065
24.7k
  bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
1066
24.7k
    assert(Inst->getFunction() == NewLoc->getFunction() &&
1067
24.7k
           "Can't reason about IPO!");
1068
24.7k
1069
24.7k
    auto *OldBB = Inst->getParent();
1070
24.7k
    auto *NewBB = NewLoc->getParent();
1071
24.7k
1072
24.7k
    // Movement within the same loop does not break LCSSA (the equality check is
1073
24.7k
    // to avoid doing a hashtable lookup in case of intra-block movement).
1074
24.7k
    if (OldBB == NewBB)
1075
23.4k
      return true;
1076
1.32k
1077
1.32k
    auto *OldLoop = getLoopFor(OldBB);
1078
1.32k
    auto *NewLoop = getLoopFor(NewBB);
1079
1.32k
1080
1.32k
    if (OldLoop == NewLoop)
1081
1.32k
      return true;
1082
0
1083
0
    // Check if Outer contains Inner; with the null loop counting as the
1084
0
    // "outermost" loop.
1085
0
    auto Contains = [](const Loop *Outer, const Loop *Inner) {
1086
0
      return !Outer || Outer->contains(Inner);
1087
0
    };
1088
0
1089
0
    // To check that the movement of Inst to before NewLoc does not break LCSSA,
1090
0
    // we need to check two sets of uses for possible LCSSA violations at
1091
0
    // NewLoc: the users of NewInst, and the operands of NewInst.
1092
0
1093
0
    // If we know we're hoisting Inst out of an inner loop to an outer loop,
1094
0
    // then the uses *of* Inst don't need to be checked.
1095
0
1096
0
    if (!Contains(NewLoop, OldLoop)) {
1097
0
      for (Use &U : Inst->uses()) {
1098
0
        auto *UI = cast<Instruction>(U.getUser());
1099
0
        auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
1100
0
                                     : UI->getParent();
1101
0
        if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
1102
0
          return false;
1103
0
      }
1104
0
    }
1105
0
1106
0
    // If we know we're sinking Inst from an outer loop into an inner loop, then
1107
0
    // the *operands* of Inst don't need to be checked.
1108
0
1109
0
    if (!Contains(OldLoop, NewLoop)) {
1110
0
      // See below on why we can't handle phi nodes here.
1111
0
      if (isa<PHINode>(Inst))
1112
0
        return false;
1113
0
1114
0
      for (Use &U : Inst->operands()) {
1115
0
        auto *DefI = dyn_cast<Instruction>(U.get());
1116
0
        if (!DefI)
1117
0
          return false;
1118
0
1119
0
        // This would need adjustment if we allow Inst to be a phi node -- the
1120
0
        // new use block won't simply be NewBB.
1121
0
1122
0
        auto *DefBlock = DefI->getParent();
1123
0
        if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
1124
0
          return false;
1125
0
      }
1126
0
    }
1127
0
1128
0
    return true;
1129
0
  }
1130
};
1131
1132
// Allow clients to walk the list of nested loops...
1133
template <> struct GraphTraits<const Loop *> {
1134
  typedef const Loop *NodeRef;
1135
  typedef LoopInfo::iterator ChildIteratorType;
1136
1137
1.89k
  static NodeRef getEntryNode(const Loop *L) { return L; }
1138
2.11k
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1139
2.32k
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1140
};
1141
1142
template <> struct GraphTraits<Loop *> {
1143
  typedef Loop *NodeRef;
1144
  typedef LoopInfo::iterator ChildIteratorType;
1145
1146
407k
  static NodeRef getEntryNode(Loop *L) { return L; }
1147
563k
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1148
720k
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1149
};
1150
1151
/// Analysis pass that exposes the \c LoopInfo for a function.
1152
class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
1153
  friend AnalysisInfoMixin<LoopAnalysis>;
1154
  static AnalysisKey Key;
1155
1156
public:
1157
  typedef LoopInfo Result;
1158
1159
  LoopInfo run(Function &F, FunctionAnalysisManager &AM);
1160
};
1161
1162
/// Printer pass for the \c LoopAnalysis results.
1163
class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> {
1164
  raw_ostream &OS;
1165
1166
public:
1167
26
  explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
1168
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1169
};
1170
1171
/// Verifier pass for the \c LoopAnalysis results.
1172
struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> {
1173
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1174
};
1175
1176
/// The legacy pass manager's analysis pass to compute loop information.
1177
class LoopInfoWrapperPass : public FunctionPass {
1178
  LoopInfo LI;
1179
1180
public:
1181
  static char ID; // Pass identification, replacement for typeid
1182
1183
344k
  LoopInfoWrapperPass() : FunctionPass(ID) {
1184
344k
    initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1185
344k
  }
1186
1187
42.3M
  LoopInfo &getLoopInfo() { return LI; }
1188
0
  const LoopInfo &getLoopInfo() const { return LI; }
1189
1190
  /// Calculate the natural loop information for a given function.
1191
  bool runOnFunction(Function &F) override;
1192
1193
  void verifyAnalysis() const override;
1194
1195
14.3M
  void releaseMemory() override { LI.releaseMemory(); }
1196
1197
  void print(raw_ostream &O, const Module *M = nullptr) const override;
1198
1199
  void getAnalysisUsage(AnalysisUsage &AU) const override;
1200
};
1201
1202
/// Function to print a loop's contents as LLVM's text IR assembly.
1203
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
1204
1205
/// Find and return the loop attribute node for the attribute @p Name in
1206
/// @p LoopID. Return nullptr if there is no such attribute.
1207
MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name);
1208
1209
/// Find string metadata for a loop.
1210
///
1211
/// Returns the MDNode where the first operand is the metadata's name. The
1212
/// following operands are the metadata's values. If no metadata with @p Name is
1213
/// found, return nullptr.
1214
MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
1215
1216
/// Return whether an MDNode might represent an access group.
1217
///
1218
/// Access group metadata nodes have to be distinct and empty. Being
1219
/// always-empty ensures that it never needs to be changed (which -- because
1220
/// MDNodes are designed immutable -- would require creating a new MDNode). Note
1221
/// that this is not a sufficient condition: not every distinct and empty NDNode
1222
/// is representing an access group.
1223
bool isValidAsAccessGroup(MDNode *AccGroup);
1224
1225
/// Create a new LoopID after the loop has been transformed.
1226
///
1227
/// This can be used when no follow-up loop attributes are defined
1228
/// (llvm::makeFollowupLoopID returning None) to stop transformations to be
1229
/// applied again.
1230
///
1231
/// @param Context        The LLVMContext in which to create the new LoopID.
1232
/// @param OrigLoopID     The original LoopID; can be nullptr if the original
1233
///                       loop has no LoopID.
1234
/// @param RemovePrefixes Remove all loop attributes that have these prefixes.
1235
///                       Use to remove metadata of the transformation that has
1236
///                       been applied.
1237
/// @param AddAttrs       Add these loop attributes to the new LoopID.
1238
///
1239
/// @return A new LoopID that can be applied using Loop::setLoopID().
1240
llvm::MDNode *
1241
makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID,
1242
                               llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
1243
                               llvm::ArrayRef<llvm::MDNode *> AddAttrs);
1244
1245
} // End llvm namespace
1246
1247
#endif