Coverage Report

Created: 2019-02-20 00:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopInfoImpl.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/LoopInfoImpl.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 is the generic implementation of LoopInfo used for both Loops and
10
// MachineLoops.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15
#define LLVM_ANALYSIS_LOOPINFOIMPL_H
16
17
#include "llvm/ADT/DepthFirstIterator.h"
18
#include "llvm/ADT/PostOrderIterator.h"
19
#include "llvm/ADT/STLExtras.h"
20
#include "llvm/ADT/SetVector.h"
21
#include "llvm/Analysis/LoopInfo.h"
22
#include "llvm/IR/Dominators.h"
23
24
namespace llvm {
25
26
//===----------------------------------------------------------------------===//
27
// APIs for simple analysis of the loop. See header notes.
28
29
/// getExitingBlocks - Return all blocks inside the loop that have successors
30
/// outside of the loop.  These are the blocks _inside of the current loop_
31
/// which branch out.  The returned list is always unique.
32
///
33
template <class BlockT, class LoopT>
34
void LoopBase<BlockT, LoopT>::getExitingBlocks(
35
7.10M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
7.10M
  assert(!isInvalid() && "Loop not in a valid state!");
37
7.10M
  for (const auto BB : blocks())
38
28.5M
    for (const auto &Succ : children<BlockT *>(BB))
39
43.5M
      if (!contains(Succ)) {
40
9.36M
        // Not in current loop? It must be an exit block.
41
9.36M
        ExitingBlocks.push_back(BB);
42
9.36M
        break;
43
9.36M
      }
44
7.10M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
35
7.05M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
7.05M
  assert(!isInvalid() && "Loop not in a valid state!");
37
7.05M
  for (const auto BB : blocks())
38
26.3M
    for (const auto &Succ : children<BlockT *>(BB))
39
39.8M
      if (!contains(Succ)) {
40
9.19M
        // Not in current loop? It must be an exit block.
41
9.19M
        ExitingBlocks.push_back(BB);
42
9.19M
        break;
43
9.19M
      }
44
7.05M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
35
44.9k
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
44.9k
  assert(!isInvalid() && "Loop not in a valid state!");
37
44.9k
  for (const auto BB : blocks())
38
2.25M
    for (const auto &Succ : children<BlockT *>(BB))
39
3.65M
      if (!contains(Succ)) {
40
169k
        // Not in current loop? It must be an exit block.
41
169k
        ExitingBlocks.push_back(BB);
42
169k
        break;
43
169k
      }
44
44.9k
}
45
46
/// getExitingBlock - If getExitingBlocks would return exactly one block,
47
/// return that block. Otherwise return null.
48
template <class BlockT, class LoopT>
49
3.73M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
50
3.73M
  assert(!isInvalid() && "Loop not in a valid state!");
51
3.73M
  SmallVector<BlockT *, 8> ExitingBlocks;
52
3.73M
  getExitingBlocks(ExitingBlocks);
53
3.73M
  if (ExitingBlocks.size() == 1)
54
3.17M
    return ExitingBlocks[0];
55
561k
  return nullptr;
56
561k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const
Line
Count
Source
49
3.73M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
50
3.73M
  assert(!isInvalid() && "Loop not in a valid state!");
51
3.73M
  SmallVector<BlockT *, 8> ExitingBlocks;
52
3.73M
  getExitingBlocks(ExitingBlocks);
53
3.73M
  if (ExitingBlocks.size() == 1)
54
3.17M
    return ExitingBlocks[0];
55
561k
  return nullptr;
56
561k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlock() const
Line
Count
Source
49
34
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
50
34
  assert(!isInvalid() && "Loop not in a valid state!");
51
34
  SmallVector<BlockT *, 8> ExitingBlocks;
52
34
  getExitingBlocks(ExitingBlocks);
53
34
  if (ExitingBlocks.size() == 1)
54
17
    return ExitingBlocks[0];
55
17
  return nullptr;
56
17
}
57
58
/// getExitBlocks - Return all of the successor blocks of this loop.  These
59
/// are the blocks _outside of the current loop_ which are branched to.
60
///
61
template <class BlockT, class LoopT>
62
void LoopBase<BlockT, LoopT>::getExitBlocks(
63
8.59M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
64
8.59M
  assert(!isInvalid() && "Loop not in a valid state!");
65
8.59M
  for (const auto BB : blocks())
66
47.3M
    for (const auto &Succ : children<BlockT *>(BB))
67
79.3M
      if (!contains(Succ))
68
12.0M
        // Not in current loop? It must be an exit block.
69
12.0M
        ExitBlocks.push_back(Succ);
70
8.59M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
63
8.28M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
64
8.28M
  assert(!isInvalid() && "Loop not in a valid state!");
65
8.28M
  for (const auto BB : blocks())
66
45.9M
    for (const auto &Succ : children<BlockT *>(BB))
67
77.0M
      if (!contains(Succ))
68
11.6M
        // Not in current loop? It must be an exit block.
69
11.6M
        ExitBlocks.push_back(Succ);
70
8.28M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
63
304k
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
64
304k
  assert(!isInvalid() && "Loop not in a valid state!");
65
304k
  for (const auto BB : blocks())
66
1.33M
    for (const auto &Succ : children<BlockT *>(BB))
67
2.28M
      if (!contains(Succ))
68
404k
        // Not in current loop? It must be an exit block.
69
404k
        ExitBlocks.push_back(Succ);
70
304k
}
71
72
/// getExitBlock - If getExitBlocks would return exactly one block,
73
/// return that block. Otherwise return null.
74
template <class BlockT, class LoopT>
75
255k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
76
255k
  assert(!isInvalid() && "Loop not in a valid state!");
77
255k
  SmallVector<BlockT *, 8> ExitBlocks;
78
255k
  getExitBlocks(ExitBlocks);
79
255k
  if (ExitBlocks.size() == 1)
80
201k
    return ExitBlocks[0];
81
54.0k
  return nullptr;
82
54.0k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlock() const
Line
Count
Source
75
255k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
76
255k
  assert(!isInvalid() && "Loop not in a valid state!");
77
255k
  SmallVector<BlockT *, 8> ExitBlocks;
78
255k
  getExitBlocks(ExitBlocks);
79
255k
  if (ExitBlocks.size() == 1)
80
201k
    return ExitBlocks[0];
81
54.0k
  return nullptr;
82
54.0k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const
83
84
template <class BlockT, class LoopT>
85
4.65M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
86
4.65M
  // Each predecessor of each exit block of a normal loop is contained
87
4.65M
  // within the loop.
88
4.65M
  SmallVector<BlockT *, 4> ExitBlocks;
89
4.65M
  getExitBlocks(ExitBlocks);
90
4.65M
  for (BlockT *EB : ExitBlocks)
91
6.37M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
92
13.0M
      if (!contains(Predecessor))
93
83
        return false;
94
4.65M
  // All the requirements are met.
95
4.65M
  
return true4.65M
;
96
4.65M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::hasDedicatedExits() const
Line
Count
Source
85
4.65M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
86
4.65M
  // Each predecessor of each exit block of a normal loop is contained
87
4.65M
  // within the loop.
88
4.65M
  SmallVector<BlockT *, 4> ExitBlocks;
89
4.65M
  getExitBlocks(ExitBlocks);
90
4.65M
  for (BlockT *EB : ExitBlocks)
91
6.37M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
92
13.0M
      if (!contains(Predecessor))
93
83
        return false;
94
4.65M
  // All the requirements are met.
95
4.65M
  
return true4.65M
;
96
4.65M
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::hasDedicatedExits() const
97
98
template <class BlockT, class LoopT>
99
void LoopBase<BlockT, LoopT>::getUniqueExitBlocks(
100
1.59M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
101
1.59M
  typedef GraphTraits<BlockT *> BlockTraits;
102
1.59M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
103
1.59M
104
1.59M
  assert(hasDedicatedExits() &&
105
1.59M
         "getUniqueExitBlocks assumes the loop has canonical form exits!");
106
1.59M
107
1.59M
  SmallVector<BlockT *, 32> SwitchExitBlocks;
108
6.10M
  for (BlockT *Block : this->blocks()) {
109
6.10M
    SwitchExitBlocks.clear();
110
10.3M
    for (BlockT *Successor : children<BlockT *>(Block)) {
111
10.3M
      // If block is inside the loop then it is not an exit block.
112
10.3M
      if (contains(Successor))
113
8.40M
        continue;
114
1.99M
115
1.99M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
116
1.99M
117
1.99M
      // If current basic block is this exit block's first predecessor then only
118
1.99M
      // insert exit block in to the output ExitBlocks vector. This ensures that
119
1.99M
      // same exit block is not inserted twice into ExitBlocks vector.
120
1.99M
      if (Block != FirstPred)
121
112k
        continue;
122
1.88M
123
1.88M
      // If a terminator has more then two successors, for example SwitchInst,
124
1.88M
      // then it is possible that there are multiple edges from current block to
125
1.88M
      // one exit block.
126
1.88M
      if (std::distance(BlockTraits::child_begin(Block),
127
1.88M
                        BlockTraits::child_end(Block)) <= 2) {
128
1.85M
        ExitBlocks.push_back(Successor);
129
1.85M
        continue;
130
1.85M
      }
131
33.1k
132
33.1k
      // In case of multiple edges from current block to exit block, collect
133
33.1k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
134
33.1k
      // duplicate edges.
135
33.1k
      if (!is_contained(SwitchExitBlocks, Successor)) {
136
26.4k
        SwitchExitBlocks.push_back(Successor);
137
26.4k
        ExitBlocks.push_back(Successor);
138
26.4k
      }
139
33.1k
    }
140
6.10M
  }
141
1.59M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getUniqueExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
100
1.59M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
101
1.59M
  typedef GraphTraits<BlockT *> BlockTraits;
102
1.59M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
103
1.59M
104
1.59M
  assert(hasDedicatedExits() &&
105
1.59M
         "getUniqueExitBlocks assumes the loop has canonical form exits!");
106
1.59M
107
1.59M
  SmallVector<BlockT *, 32> SwitchExitBlocks;
108
6.10M
  for (BlockT *Block : this->blocks()) {
109
6.10M
    SwitchExitBlocks.clear();
110
10.3M
    for (BlockT *Successor : children<BlockT *>(Block)) {
111
10.3M
      // If block is inside the loop then it is not an exit block.
112
10.3M
      if (contains(Successor))
113
8.40M
        continue;
114
1.99M
115
1.99M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
116
1.99M
117
1.99M
      // If current basic block is this exit block's first predecessor then only
118
1.99M
      // insert exit block in to the output ExitBlocks vector. This ensures that
119
1.99M
      // same exit block is not inserted twice into ExitBlocks vector.
120
1.99M
      if (Block != FirstPred)
121
112k
        continue;
122
1.88M
123
1.88M
      // If a terminator has more then two successors, for example SwitchInst,
124
1.88M
      // then it is possible that there are multiple edges from current block to
125
1.88M
      // one exit block.
126
1.88M
      if (std::distance(BlockTraits::child_begin(Block),
127
1.88M
                        BlockTraits::child_end(Block)) <= 2) {
128
1.85M
        ExitBlocks.push_back(Successor);
129
1.85M
        continue;
130
1.85M
      }
131
33.1k
132
33.1k
      // In case of multiple edges from current block to exit block, collect
133
33.1k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
134
33.1k
      // duplicate edges.
135
33.1k
      if (!is_contained(SwitchExitBlocks, Successor)) {
136
26.4k
        SwitchExitBlocks.push_back(Successor);
137
26.4k
        ExitBlocks.push_back(Successor);
138
26.4k
      }
139
33.1k
    }
140
6.10M
  }
141
1.59M
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getUniqueExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
142
143
template <class BlockT, class LoopT>
144
483k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
145
483k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
146
483k
  getUniqueExitBlocks(UniqueExitBlocks);
147
483k
  if (UniqueExitBlocks.size() == 1)
148
454k
    return UniqueExitBlocks[0];
149
29.4k
  return nullptr;
150
29.4k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getUniqueExitBlock() const
Line
Count
Source
144
483k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
145
483k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
146
483k
  getUniqueExitBlocks(UniqueExitBlocks);
147
483k
  if (UniqueExitBlocks.size() == 1)
148
454k
    return UniqueExitBlocks[0];
149
29.4k
  return nullptr;
150
29.4k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getUniqueExitBlock() const
151
152
/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
153
template <class BlockT, class LoopT>
154
void LoopBase<BlockT, LoopT>::getExitEdges(
155
72
    SmallVectorImpl<Edge> &ExitEdges) const {
156
72
  assert(!isInvalid() && "Loop not in a valid state!");
157
72
  for (const auto BB : blocks())
158
120
    for (const auto &Succ : children<BlockT *>(BB))
159
232
      if (!contains(Succ))
160
104
        // Not in current loop? It must be an exit block.
161
104
        ExitEdges.emplace_back(BB, Succ);
162
72
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::BasicBlock const*, llvm::BasicBlock const*> >&) const
Line
Count
Source
155
72
    SmallVectorImpl<Edge> &ExitEdges) const {
156
72
  assert(!isInvalid() && "Loop not in a valid state!");
157
72
  for (const auto BB : blocks())
158
120
    for (const auto &Succ : children<BlockT *>(BB))
159
232
      if (!contains(Succ))
160
104
        // Not in current loop? It must be an exit block.
161
104
        ExitEdges.emplace_back(BB, Succ);
162
72
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*> >&) const
163
164
/// getLoopPreheader - If there is a preheader for this loop, return it.  A
165
/// loop has a preheader if there is only one edge to the header of the loop
166
/// from outside of the loop and it is legal to hoist instructions into the
167
/// predecessor. If this is the case, the block branching to the header of the
168
/// loop is the preheader node.
169
///
170
/// This method returns null if there is no preheader for the loop.
171
///
172
template <class BlockT, class LoopT>
173
11.4M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
174
11.4M
  assert(!isInvalid() && "Loop not in a valid state!");
175
11.4M
  // Keep track of nodes outside the loop branching to the header...
176
11.4M
  BlockT *Out = getLoopPredecessor();
177
11.4M
  if (!Out)
178
20.6k
    return nullptr;
179
11.4M
180
11.4M
  // Make sure we are allowed to hoist instructions into the predecessor.
181
11.4M
  if (!Out->isLegalToHoistInto())
182
465
    return nullptr;
183
11.4M
184
11.4M
  // Make sure there is only one exit out of the preheader.
185
11.4M
  typedef GraphTraits<BlockT *> BlockTraits;
186
11.4M
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
187
11.4M
  ++SI;
188
11.4M
  if (SI != BlockTraits::child_end(Out))
189
496k
    return nullptr; // Multiple exits from the block, must not be a preheader.
190
10.9M
191
10.9M
  // The predecessor has exactly one successor, so it is a preheader.
192
10.9M
  return Out;
193
10.9M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPreheader() const
Line
Count
Source
173
11.1M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
174
11.1M
  assert(!isInvalid() && "Loop not in a valid state!");
175
11.1M
  // Keep track of nodes outside the loop branching to the header...
176
11.1M
  BlockT *Out = getLoopPredecessor();
177
11.1M
  if (!Out)
178
19.1k
    return nullptr;
179
11.1M
180
11.1M
  // Make sure we are allowed to hoist instructions into the predecessor.
181
11.1M
  if (!Out->isLegalToHoistInto())
182
465
    return nullptr;
183
11.1M
184
11.1M
  // Make sure there is only one exit out of the preheader.
185
11.1M
  typedef GraphTraits<BlockT *> BlockTraits;
186
11.1M
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
187
11.1M
  ++SI;
188
11.1M
  if (SI != BlockTraits::child_end(Out))
189
475k
    return nullptr; // Multiple exits from the block, must not be a preheader.
190
10.6M
191
10.6M
  // The predecessor has exactly one successor, so it is a preheader.
192
10.6M
  return Out;
193
10.6M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPreheader() const
Line
Count
Source
173
305k
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
174
305k
  assert(!isInvalid() && "Loop not in a valid state!");
175
305k
  // Keep track of nodes outside the loop branching to the header...
176
305k
  BlockT *Out = getLoopPredecessor();
177
305k
  if (!Out)
178
1.49k
    return nullptr;
179
304k
180
304k
  // Make sure we are allowed to hoist instructions into the predecessor.
181
304k
  if (!Out->isLegalToHoistInto())
182
0
    return nullptr;
183
304k
184
304k
  // Make sure there is only one exit out of the preheader.
185
304k
  typedef GraphTraits<BlockT *> BlockTraits;
186
304k
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
187
304k
  ++SI;
188
304k
  if (SI != BlockTraits::child_end(Out))
189
20.4k
    return nullptr; // Multiple exits from the block, must not be a preheader.
190
283k
191
283k
  // The predecessor has exactly one successor, so it is a preheader.
192
283k
  return Out;
193
283k
}
194
195
/// getLoopPredecessor - If the given loop's header has exactly one unique
196
/// predecessor outside the loop, return it. Otherwise return null.
197
/// This is less strict that the loop "preheader" concept, which requires
198
/// the predecessor to have exactly one successor.
199
///
200
template <class BlockT, class LoopT>
201
12.9M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
12.9M
  assert(!isInvalid() && "Loop not in a valid state!");
203
12.9M
  // Keep track of nodes outside the loop branching to the header...
204
12.9M
  BlockT *Out = nullptr;
205
12.9M
206
12.9M
  // Loop over the predecessors of the header node...
207
12.9M
  BlockT *Header = getHeader();
208
25.8M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
25.8M
    if (!contains(Pred)) { // If the block is not in the loop...
210
12.9M
      if (Out && 
Out != Pred23.8k
)
211
23.6k
        return nullptr; // Multiple predecessors outside the loop
212
12.9M
      Out = Pred;
213
12.9M
    }
214
25.8M
  }
215
12.9M
216
12.9M
  // Make sure there is only one exit out of the preheader.
217
12.9M
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
12.9M
  return Out;
219
12.9M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPredecessor() const
Line
Count
Source
201
12.4M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
12.4M
  assert(!isInvalid() && "Loop not in a valid state!");
203
12.4M
  // Keep track of nodes outside the loop branching to the header...
204
12.4M
  BlockT *Out = nullptr;
205
12.4M
206
12.4M
  // Loop over the predecessors of the header node...
207
12.4M
  BlockT *Header = getHeader();
208
24.8M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
24.8M
    if (!contains(Pred)) { // If the block is not in the loop...
210
12.5M
      if (Out && 
Out != Pred19.3k
)
211
19.2k
        return nullptr; // Multiple predecessors outside the loop
212
12.4M
      Out = Pred;
213
12.4M
    }
214
24.8M
  }
215
12.4M
216
12.4M
  // Make sure there is only one exit out of the preheader.
217
12.4M
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
12.4M
  return Out;
219
12.4M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const
Line
Count
Source
201
480k
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
480k
  assert(!isInvalid() && "Loop not in a valid state!");
203
480k
  // Keep track of nodes outside the loop branching to the header...
204
480k
  BlockT *Out = nullptr;
205
480k
206
480k
  // Loop over the predecessors of the header node...
207
480k
  BlockT *Header = getHeader();
208
986k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
986k
    if (!contains(Pred)) { // If the block is not in the loop...
210
485k
      if (Out && 
Out != Pred4.47k
)
211
4.47k
        return nullptr; // Multiple predecessors outside the loop
212
480k
      Out = Pred;
213
480k
    }
214
986k
  }
215
480k
216
480k
  // Make sure there is only one exit out of the preheader.
217
480k
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
476k
  return Out;
219
480k
}
220
221
/// getLoopLatch - If there is a single latch block for this loop, return it.
222
/// A latch block is a block that contains a branch back to the header.
223
template <class BlockT, class LoopT>
224
14.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
225
14.5M
  assert(!isInvalid() && "Loop not in a valid state!");
226
14.5M
  BlockT *Header = getHeader();
227
14.5M
  BlockT *Latch = nullptr;
228
29.0M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
29.0M
    if (contains(Pred)) {
230
14.5M
      if (Latch)
231
7.17k
        return nullptr;
232
14.5M
      Latch = Pred;
233
14.5M
    }
234
29.0M
  }
235
14.5M
236
14.5M
  
return Latch14.5M
;
237
14.5M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const
Line
Count
Source
224
14.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
225
14.5M
  assert(!isInvalid() && "Loop not in a valid state!");
226
14.5M
  BlockT *Header = getHeader();
227
14.5M
  BlockT *Latch = nullptr;
228
29.0M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
29.0M
    if (contains(Pred)) {
230
14.5M
      if (Latch)
231
7.16k
        return nullptr;
232
14.5M
      Latch = Pred;
233
14.5M
    }
234
29.0M
  }
235
14.5M
236
14.5M
  
return Latch14.5M
;
237
14.5M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatch() const
Line
Count
Source
224
3.01k
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
225
3.01k
  assert(!isInvalid() && "Loop not in a valid state!");
226
3.01k
  BlockT *Header = getHeader();
227
3.01k
  BlockT *Latch = nullptr;
228
6.05k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
6.05k
    if (contains(Pred)) {
230
3.01k
      if (Latch)
231
4
        return nullptr;
232
3.01k
      Latch = Pred;
233
3.01k
    }
234
6.05k
  }
235
3.01k
236
3.01k
  
return Latch3.00k
;
237
3.01k
}
238
239
//===----------------------------------------------------------------------===//
240
// APIs for updating loop information after changing the CFG
241
//
242
243
/// addBasicBlockToLoop - This method is used by other analyses to update loop
244
/// information.  NewBB is set to be a new member of the current loop.
245
/// Because of this, it is added as a member of all parent loops, and is added
246
/// to the specified LoopInfo object as being in the current basic block.  It
247
/// is not valid to replace the loop header with this method.
248
///
249
template <class BlockT, class LoopT>
250
void LoopBase<BlockT, LoopT>::addBasicBlockToLoop(
251
809k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
809k
  assert(!isInvalid() && "Loop not in a valid state!");
253
809k
#ifndef NDEBUG
254
809k
  if (!Blocks.empty()) {
255
809k
    auto SameHeader = LIB[getHeader()];
256
809k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
809k
           "Incorrect LI specified for this loop!");
258
809k
  }
259
809k
#endif
260
809k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
809k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
809k
263
809k
  LoopT *L = static_cast<LoopT *>(this);
264
809k
265
809k
  // Add the loop mapping to the LoopInfo object...
266
809k
  LIB.BBMap[NewBB] = L;
267
809k
268
809k
  // Add the basic block to this loop and all parent loops...
269
2.02M
  while (L) {
270
1.21M
    L->addBlockEntry(NewBB);
271
1.21M
    L = L->getParentLoop();
272
1.21M
  }
273
809k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&)
Line
Count
Source
251
763k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
763k
  assert(!isInvalid() && "Loop not in a valid state!");
253
763k
#ifndef NDEBUG
254
763k
  if (!Blocks.empty()) {
255
763k
    auto SameHeader = LIB[getHeader()];
256
763k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
763k
           "Incorrect LI specified for this loop!");
258
763k
  }
259
763k
#endif
260
763k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
763k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
763k
263
763k
  LoopT *L = static_cast<LoopT *>(this);
264
763k
265
763k
  // Add the loop mapping to the LoopInfo object...
266
763k
  LIB.BBMap[NewBB] = L;
267
763k
268
763k
  // Add the basic block to this loop and all parent loops...
269
1.91M
  while (L) {
270
1.14M
    L->addBlockEntry(NewBB);
271
1.14M
    L = L->getParentLoop();
272
1.14M
  }
273
763k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&)
Line
Count
Source
251
46.1k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
46.1k
  assert(!isInvalid() && "Loop not in a valid state!");
253
46.1k
#ifndef NDEBUG
254
46.1k
  if (!Blocks.empty()) {
255
46.1k
    auto SameHeader = LIB[getHeader()];
256
46.1k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
46.1k
           "Incorrect LI specified for this loop!");
258
46.1k
  }
259
46.1k
#endif
260
46.1k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
46.1k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
46.1k
263
46.1k
  LoopT *L = static_cast<LoopT *>(this);
264
46.1k
265
46.1k
  // Add the loop mapping to the LoopInfo object...
266
46.1k
  LIB.BBMap[NewBB] = L;
267
46.1k
268
46.1k
  // Add the basic block to this loop and all parent loops...
269
116k
  while (L) {
270
70.7k
    L->addBlockEntry(NewBB);
271
70.7k
    L = L->getParentLoop();
272
70.7k
  }
273
46.1k
}
274
275
/// replaceChildLoopWith - This is used when splitting loops up.  It replaces
276
/// the OldChild entry in our children list with NewChild, and updates the
277
/// parent pointer of OldChild to be null and the NewChild to be this loop.
278
/// This updates the loop depth of the new child.
279
template <class BlockT, class LoopT>
280
void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild,
281
59
                                                   LoopT *NewChild) {
282
59
  assert(!isInvalid() && "Loop not in a valid state!");
283
59
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
284
59
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
285
59
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
286
59
  assert(I != SubLoops.end() && "OldChild not in loop!");
287
59
  *I = NewChild;
288
59
  OldChild->ParentLoop = nullptr;
289
59
  NewChild->ParentLoop = static_cast<LoopT *>(this);
290
59
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::replaceChildLoopWith(llvm::Loop*, llvm::Loop*)
Line
Count
Source
281
59
                                                   LoopT *NewChild) {
282
59
  assert(!isInvalid() && "Loop not in a valid state!");
283
59
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
284
59
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
285
59
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
286
59
  assert(I != SubLoops.end() && "OldChild not in loop!");
287
59
  *I = NewChild;
288
59
  OldChild->ParentLoop = nullptr;
289
59
  NewChild->ParentLoop = static_cast<LoopT *>(this);
290
59
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::replaceChildLoopWith(llvm::MachineLoop*, llvm::MachineLoop*)
291
292
/// verifyLoop - Verify loop structure
293
template <class BlockT, class LoopT>
294
2.89M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
295
2.89M
  assert(!isInvalid() && "Loop not in a valid state!");
296
2.89M
#ifndef NDEBUG
297
2.89M
  assert(!Blocks.empty() && "Loop header is missing");
298
2.89M
299
2.89M
  // Setup for using a depth-first iterator to visit every block in the loop.
300
2.89M
  SmallVector<BlockT *, 8> ExitBBs;
301
2.89M
  getExitBlocks(ExitBBs);
302
2.89M
  df_iterator_default_set<BlockT *> VisitSet;
303
2.89M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
304
2.89M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
305
2.89M
      BI = df_ext_begin(getHeader(), VisitSet),
306
2.89M
      BE = df_ext_end(getHeader(), VisitSet);
307
2.89M
308
2.89M
  // Keep track of the BBs visited.
309
2.89M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
310
2.89M
311
2.89M
  // Check the individual blocks.
312
2.89M
  for (; BI != BE; ++BI) {
313
2.89M
    BlockT *BB = *BI;
314
2.89M
315
2.89M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
316
2.89M
                       GraphTraits<BlockT *>::child_end(BB),
317
2.89M
                       [&](BlockT *B) { return contains(B); }) &&
318
2.89M
           "Loop block has no in-loop successors!");
319
2.89M
320
2.89M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
321
2.89M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
322
2.89M
                       [&](BlockT *B) { return contains(B); }) &&
323
2.89M
           "Loop block has no in-loop predecessors!");
324
2.89M
325
2.89M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
326
2.89M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
327
2.89M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
328
2.89M
                  [&](BlockT *B) {
329
2.89M
                    if (!contains(B))
330
2.89M
                      OutsideLoopPreds.push_back(B);
331
2.89M
                  });
332
2.89M
333
2.89M
    if (BB == getHeader()) {
334
2.89M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
335
2.89M
    } else if (!OutsideLoopPreds.empty()) {
336
2.89M
      // A non-header loop shouldn't be reachable from outside the loop,
337
2.89M
      // though it is permitted if the predecessor is not itself actually
338
2.89M
      // reachable.
339
2.89M
      BlockT *EntryBB = &BB->getParent()->front();
340
2.89M
      for (BlockT *CB : depth_first(EntryBB))
341
2.89M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
342
2.89M
          assert(CB != OutsideLoopPreds[i] &&
343
2.89M
                 "Loop has multiple entry points!");
344
2.89M
    }
345
2.89M
    assert(BB != &getHeader()->getParent()->front() &&
346
2.89M
           "Loop contains function entry block!");
347
2.89M
348
2.89M
    VisitedBBs.insert(BB);
349
2.89M
  }
350
2.89M
351
2.89M
  if (VisitedBBs.size() != getNumBlocks()) {
352
2.89M
    dbgs() << "The following blocks are unreachable in the loop: ";
353
2.89M
    for (auto BB : Blocks) {
354
2.89M
      if (!VisitedBBs.count(BB)) {
355
2.89M
        dbgs() << *BB << "\n";
356
2.89M
      }
357
2.89M
    }
358
2.89M
    assert(false && "Unreachable block in loop");
359
2.89M
  }
360
2.89M
361
2.89M
  // Check the subloops.
362
2.89M
  for (iterator I = begin(), E = end(); I != E; ++I)
363
2.89M
    // Each block in each subloop should be contained within this loop.
364
2.89M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
365
2.89M
         BI != BE; ++BI) {
366
2.89M
      assert(contains(*BI) &&
367
2.89M
             "Loop does not contain all the blocks of a subloop!");
368
2.89M
    }
369
2.89M
370
2.89M
  // Check the parent loop pointer.
371
2.89M
  if (ParentLoop) {
372
2.89M
    assert(is_contained(*ParentLoop, this) &&
373
2.89M
           "Loop is not a subloop of its parent!");
374
2.89M
  }
375
2.89M
#endif
376
2.89M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoop() const
Line
Count
Source
294
2.89M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
295
2.89M
  assert(!isInvalid() && "Loop not in a valid state!");
296
2.89M
#ifndef NDEBUG
297
2.89M
  assert(!Blocks.empty() && "Loop header is missing");
298
2.89M
299
2.89M
  // Setup for using a depth-first iterator to visit every block in the loop.
300
2.89M
  SmallVector<BlockT *, 8> ExitBBs;
301
2.89M
  getExitBlocks(ExitBBs);
302
2.89M
  df_iterator_default_set<BlockT *> VisitSet;
303
2.89M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
304
2.89M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
305
2.89M
      BI = df_ext_begin(getHeader(), VisitSet),
306
2.89M
      BE = df_ext_end(getHeader(), VisitSet);
307
2.89M
308
2.89M
  // Keep track of the BBs visited.
309
2.89M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
310
2.89M
311
2.89M
  // Check the individual blocks.
312
2.89M
  for (; BI != BE; ++BI) {
313
2.89M
    BlockT *BB = *BI;
314
2.89M
315
2.89M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
316
2.89M
                       GraphTraits<BlockT *>::child_end(BB),
317
2.89M
                       [&](BlockT *B) { return contains(B); }) &&
318
2.89M
           "Loop block has no in-loop successors!");
319
2.89M
320
2.89M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
321
2.89M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
322
2.89M
                       [&](BlockT *B) { return contains(B); }) &&
323
2.89M
           "Loop block has no in-loop predecessors!");
324
2.89M
325
2.89M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
326
2.89M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
327
2.89M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
328
2.89M
                  [&](BlockT *B) {
329
2.89M
                    if (!contains(B))
330
2.89M
                      OutsideLoopPreds.push_back(B);
331
2.89M
                  });
332
2.89M
333
2.89M
    if (BB == getHeader()) {
334
2.89M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
335
2.89M
    } else if (!OutsideLoopPreds.empty()) {
336
2.89M
      // A non-header loop shouldn't be reachable from outside the loop,
337
2.89M
      // though it is permitted if the predecessor is not itself actually
338
2.89M
      // reachable.
339
2.89M
      BlockT *EntryBB = &BB->getParent()->front();
340
2.89M
      for (BlockT *CB : depth_first(EntryBB))
341
2.89M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
342
2.89M
          assert(CB != OutsideLoopPreds[i] &&
343
2.89M
                 "Loop has multiple entry points!");
344
2.89M
    }
345
2.89M
    assert(BB != &getHeader()->getParent()->front() &&
346
2.89M
           "Loop contains function entry block!");
347
2.89M
348
2.89M
    VisitedBBs.insert(BB);
349
2.89M
  }
350
2.89M
351
2.89M
  if (VisitedBBs.size() != getNumBlocks()) {
352
2.89M
    dbgs() << "The following blocks are unreachable in the loop: ";
353
2.89M
    for (auto BB : Blocks) {
354
2.89M
      if (!VisitedBBs.count(BB)) {
355
2.89M
        dbgs() << *BB << "\n";
356
2.89M
      }
357
2.89M
    }
358
2.89M
    assert(false && "Unreachable block in loop");
359
2.89M
  }
360
2.89M
361
2.89M
  // Check the subloops.
362
2.89M
  for (iterator I = begin(), E = end(); I != E; ++I)
363
2.89M
    // Each block in each subloop should be contained within this loop.
364
2.89M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
365
2.89M
         BI != BE; ++BI) {
366
2.89M
      assert(contains(*BI) &&
367
2.89M
             "Loop does not contain all the blocks of a subloop!");
368
2.89M
    }
369
2.89M
370
2.89M
  // Check the parent loop pointer.
371
2.89M
  if (ParentLoop) {
372
2.89M
    assert(is_contained(*ParentLoop, this) &&
373
2.89M
           "Loop is not a subloop of its parent!");
374
2.89M
  }
375
2.89M
#endif
376
2.89M
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoop() const
377
378
/// verifyLoop - Verify loop structure of this loop and all nested loops.
379
template <class BlockT, class LoopT>
380
void LoopBase<BlockT, LoopT>::verifyLoopNest(
381
284
    DenseSet<const LoopT *> *Loops) const {
382
284
  assert(!isInvalid() && "Loop not in a valid state!");
383
284
  Loops->insert(static_cast<const LoopT *>(this));
384
284
  // Verify this loop.
385
284
  verifyLoop();
386
284
  // Verify the subloops.
387
381
  for (iterator I = begin(), E = end(); I != E; 
++I97
)
388
97
    (*I)->verifyLoopNest(Loops);
389
284
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoopNest(llvm::DenseSet<llvm::Loop const*, llvm::DenseMapInfo<llvm::Loop const*> >*) const
Line
Count
Source
381
284
    DenseSet<const LoopT *> *Loops) const {
382
284
  assert(!isInvalid() && "Loop not in a valid state!");
383
284
  Loops->insert(static_cast<const LoopT *>(this));
384
284
  // Verify this loop.
385
284
  verifyLoop();
386
284
  // Verify the subloops.
387
381
  for (iterator I = begin(), E = end(); I != E; 
++I97
)
388
97
    (*I)->verifyLoopNest(Loops);
389
284
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoopNest(llvm::DenseSet<llvm::MachineLoop const*, llvm::DenseMapInfo<llvm::MachineLoop const*> >*) const
390
391
template <class BlockT, class LoopT>
392
void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth,
393
1.34k
                                    bool Verbose) const {
394
1.34k
  OS.indent(Depth * 2);
395
1.34k
  if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
396
4
    OS << "Parallel ";
397
1.34k
  OS << "Loop at depth " << getLoopDepth() << " containing: ";
398
1.34k
399
1.34k
  BlockT *H = getHeader();
400
12.4k
  for (unsigned i = 0; i < getBlocks().size(); 
++i11.1k
) {
401
11.1k
    BlockT *BB = getBlocks()[i];
402
11.1k
    if (!Verbose) {
403
11.1k
      if (i)
404
9.76k
        OS << ",";
405
11.1k
      BB->printAsOperand(OS, false);
406
11.1k
    } else
407
0
      OS << "\n";
408
11.1k
409
11.1k
    if (BB == H)
410
1.34k
      OS << "<header>";
411
11.1k
    if (isLoopLatch(BB))
412
1.34k
      OS << "<latch>";
413
11.1k
    if (isLoopExiting(BB))
414
1.59k
      OS << "<exiting>";
415
11.1k
    if (Verbose)
416
0
      BB->print(OS);
417
11.1k
  }
418
1.34k
  OS << "\n";
419
1.34k
420
1.84k
  for (iterator I = begin(), E = end(); I != E; 
++I503
)
421
503
    (*I)->print(OS, Depth + 2);
422
1.34k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&, unsigned int, bool) const
Line
Count
Source
393
1.34k
                                    bool Verbose) const {
394
1.34k
  OS.indent(Depth * 2);
395
1.34k
  if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
396
4
    OS << "Parallel ";
397
1.34k
  OS << "Loop at depth " << getLoopDepth() << " containing: ";
398
1.34k
399
1.34k
  BlockT *H = getHeader();
400
12.4k
  for (unsigned i = 0; i < getBlocks().size(); 
++i11.1k
) {
401
11.1k
    BlockT *BB = getBlocks()[i];
402
11.1k
    if (!Verbose) {
403
11.1k
      if (i)
404
9.76k
        OS << ",";
405
11.1k
      BB->printAsOperand(OS, false);
406
11.1k
    } else
407
0
      OS << "\n";
408
11.1k
409
11.1k
    if (BB == H)
410
1.34k
      OS << "<header>";
411
11.1k
    if (isLoopLatch(BB))
412
1.34k
      OS << "<latch>";
413
11.1k
    if (isLoopExiting(BB))
414
1.59k
      OS << "<exiting>";
415
11.1k
    if (Verbose)
416
0
      BB->print(OS);
417
11.1k
  }
418
1.34k
  OS << "\n";
419
1.34k
420
1.84k
  for (iterator I = begin(), E = end(); I != E; 
++I503
)
421
503
    (*I)->print(OS, Depth + 2);
422
1.34k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&, unsigned int, bool) const
423
424
//===----------------------------------------------------------------------===//
425
/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
426
/// result does / not depend on use list (block predecessor) order.
427
///
428
429
/// Discover a subloop with the specified backedges such that: All blocks within
430
/// this loop are mapped to this loop or a subloop. And all subloops within this
431
/// loop have their parent loop set to this loop or a subloop.
432
template <class BlockT, class LoopT>
433
static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
434
                                  LoopInfoBase<BlockT, LoopT> *LI,
435
4.09M
                                  const DomTreeBase<BlockT> &DomTree) {
436
4.09M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
4.09M
438
4.09M
  unsigned NumBlocks = 0;
439
4.09M
  unsigned NumSubloops = 0;
440
4.09M
441
4.09M
  // Perform a backward CFG traversal using a worklist.
442
4.09M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
22.8M
  while (!ReverseCFGWorklist.empty()) {
444
18.7M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
18.7M
    ReverseCFGWorklist.pop_back();
446
18.7M
447
18.7M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
18.7M
    if (!Subloop) {
449
13.1M
      if (!DomTree.isReachableFromEntry(PredBB))
450
50
        continue;
451
13.1M
452
13.1M
      // This is an undiscovered block. Map it to the current loop.
453
13.1M
      LI->changeLoopFor(PredBB, L);
454
13.1M
      ++NumBlocks;
455
13.1M
      if (PredBB == L->getHeader())
456
4.09M
        continue;
457
9.09M
      // Push all block predecessors on the worklist.
458
9.09M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
9.09M
                                InvBlockTraits::child_begin(PredBB),
460
9.09M
                                InvBlockTraits::child_end(PredBB));
461
9.09M
    } else {
462
5.51M
      // This is a discovered block. Find its outermost discovered loop.
463
5.73M
      while (LoopT *Parent = Subloop->getParentLoop())
464
212k
        Subloop = Parent;
465
5.51M
466
5.51M
      // If it is already discovered to be a subloop of this loop, continue.
467
5.51M
      if (Subloop == L)
468
4.43M
        continue;
469
1.08M
470
1.08M
      // Discover a subloop of this loop.
471
1.08M
      Subloop->setParentLoop(L);
472
1.08M
      ++NumSubloops;
473
1.08M
      NumBlocks += Subloop->getBlocksVector().capacity();
474
1.08M
      PredBB = Subloop->getHeader();
475
1.08M
      // Continue traversal along predecessors that are not loop-back edges from
476
1.08M
      // within this subloop tree itself. Note that a predecessor may directly
477
1.08M
      // reach another subloop that is not yet discovered to be a subloop of
478
1.08M
      // this loop, which we must traverse.
479
2.19M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
480
2.19M
        if (LI->getLoopFor(Pred) != Subloop)
481
1.09M
          ReverseCFGWorklist.push_back(Pred);
482
2.19M
      }
483
1.08M
    }
484
18.7M
  }
485
4.09M
  L->getSubLoopsVector().reserve(NumSubloops);
486
4.09M
  L->reserveBlocks(NumBlocks);
487
4.09M
}
LoopInfo.cpp:void llvm::discoverAndMapSubloop<llvm::BasicBlock, llvm::Loop>(llvm::Loop*, llvm::ArrayRef<llvm::BasicBlock*>, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>*, llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
435
3.24M
                                  const DomTreeBase<BlockT> &DomTree) {
436
3.24M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
3.24M
438
3.24M
  unsigned NumBlocks = 0;
439
3.24M
  unsigned NumSubloops = 0;
440
3.24M
441
3.24M
  // Perform a backward CFG traversal using a worklist.
442
3.24M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
18.1M
  while (!ReverseCFGWorklist.empty()) {
444
14.9M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
14.9M
    ReverseCFGWorklist.pop_back();
446
14.9M
447
14.9M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
14.9M
    if (!Subloop) {
449
10.4M
      if (!DomTree.isReachableFromEntry(PredBB))
450
50
        continue;
451
10.4M
452
10.4M
      // This is an undiscovered block. Map it to the current loop.
453
10.4M
      LI->changeLoopFor(PredBB, L);
454
10.4M
      ++NumBlocks;
455
10.4M
      if (PredBB == L->getHeader())
456
3.24M
        continue;
457
7.24M
      // Push all block predecessors on the worklist.
458
7.24M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
7.24M
                                InvBlockTraits::child_begin(PredBB),
460
7.24M
                                InvBlockTraits::child_end(PredBB));
461
7.24M
    } else {
462
4.41M
      // This is a discovered block. Find its outermost discovered loop.
463
4.58M
      while (LoopT *Parent = Subloop->getParentLoop())
464
161k
        Subloop = Parent;
465
4.41M
466
4.41M
      // If it is already discovered to be a subloop of this loop, continue.
467
4.41M
      if (Subloop == L)
468
3.55M
        continue;
469
867k
470
867k
      // Discover a subloop of this loop.
471
867k
      Subloop->setParentLoop(L);
472
867k
      ++NumSubloops;
473
867k
      NumBlocks += Subloop->getBlocksVector().capacity();
474
867k
      PredBB = Subloop->getHeader();
475
867k
      // Continue traversal along predecessors that are not loop-back edges from
476
867k
      // within this subloop tree itself. Note that a predecessor may directly
477
867k
      // reach another subloop that is not yet discovered to be a subloop of
478
867k
      // this loop, which we must traverse.
479
1.74M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
480
1.74M
        if (LI->getLoopFor(Pred) != Subloop)
481
874k
          ReverseCFGWorklist.push_back(Pred);
482
1.74M
      }
483
867k
    }
484
14.9M
  }
485
3.24M
  L->getSubLoopsVector().reserve(NumSubloops);
486
3.24M
  L->reserveBlocks(NumBlocks);
487
3.24M
}
MachineLoopInfo.cpp:void llvm::discoverAndMapSubloop<llvm::MachineBasicBlock, llvm::MachineLoop>(llvm::MachineLoop*, llvm::ArrayRef<llvm::MachineBasicBlock*>, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>*, llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
435
849k
                                  const DomTreeBase<BlockT> &DomTree) {
436
849k
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
849k
438
849k
  unsigned NumBlocks = 0;
439
849k
  unsigned NumSubloops = 0;
440
849k
441
849k
  // Perform a backward CFG traversal using a worklist.
442
849k
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
4.65M
  while (!ReverseCFGWorklist.empty()) {
444
3.80M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
3.80M
    ReverseCFGWorklist.pop_back();
446
3.80M
447
3.80M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
3.80M
    if (!Subloop) {
449
2.70M
      if (!DomTree.isReachableFromEntry(PredBB))
450
0
        continue;
451
2.70M
452
2.70M
      // This is an undiscovered block. Map it to the current loop.
453
2.70M
      LI->changeLoopFor(PredBB, L);
454
2.70M
      ++NumBlocks;
455
2.70M
      if (PredBB == L->getHeader())
456
849k
        continue;
457
1.85M
      // Push all block predecessors on the worklist.
458
1.85M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
1.85M
                                InvBlockTraits::child_begin(PredBB),
460
1.85M
                                InvBlockTraits::child_end(PredBB));
461
1.85M
    } else {
462
1.10M
      // This is a discovered block. Find its outermost discovered loop.
463
1.15M
      while (LoopT *Parent = Subloop->getParentLoop())
464
51.1k
        Subloop = Parent;
465
1.10M
466
1.10M
      // If it is already discovered to be a subloop of this loop, continue.
467
1.10M
      if (Subloop == L)
468
878k
        continue;
469
221k
470
221k
      // Discover a subloop of this loop.
471
221k
      Subloop->setParentLoop(L);
472
221k
      ++NumSubloops;
473
221k
      NumBlocks += Subloop->getBlocksVector().capacity();
474
221k
      PredBB = Subloop->getHeader();
475
221k
      // Continue traversal along predecessors that are not loop-back edges from
476
221k
      // within this subloop tree itself. Note that a predecessor may directly
477
221k
      // reach another subloop that is not yet discovered to be a subloop of
478
221k
      // this loop, which we must traverse.
479
446k
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
480
446k
        if (LI->getLoopFor(Pred) != Subloop)
481
223k
          ReverseCFGWorklist.push_back(Pred);
482
446k
      }
483
221k
    }
484
3.80M
  }
485
849k
  L->getSubLoopsVector().reserve(NumSubloops);
486
849k
  L->reserveBlocks(NumBlocks);
487
849k
}
VPlanHCFGBuilder.cpp:void llvm::discoverAndMapSubloop<llvm::VPBlockBase, llvm::VPLoop>(llvm::VPLoop*, llvm::ArrayRef<llvm::VPBlockBase*>, llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>*, llvm::DominatorTreeBase<llvm::VPBlockBase, false> const&)
Line
Count
Source
435
4
                                  const DomTreeBase<BlockT> &DomTree) {
436
4
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
4
438
4
  unsigned NumBlocks = 0;
439
4
  unsigned NumSubloops = 0;
440
4
441
4
  // Perform a backward CFG traversal using a worklist.
442
4
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
15
  while (!ReverseCFGWorklist.empty()) {
444
11
    BlockT *PredBB = ReverseCFGWorklist.back();
445
11
    ReverseCFGWorklist.pop_back();
446
11
447
11
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
11
    if (!Subloop) {
449
8
      if (!DomTree.isReachableFromEntry(PredBB))
450
0
        continue;
451
8
452
8
      // This is an undiscovered block. Map it to the current loop.
453
8
      LI->changeLoopFor(PredBB, L);
454
8
      ++NumBlocks;
455
8
      if (PredBB == L->getHeader())
456
4
        continue;
457
4
      // Push all block predecessors on the worklist.
458
4
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
4
                                InvBlockTraits::child_begin(PredBB),
460
4
                                InvBlockTraits::child_end(PredBB));
461
4
    } else {
462
3
      // This is a discovered block. Find its outermost discovered loop.
463
3
      while (LoopT *Parent = Subloop->getParentLoop())
464
0
        Subloop = Parent;
465
3
466
3
      // If it is already discovered to be a subloop of this loop, continue.
467
3
      if (Subloop == L)
468
1
        continue;
469
2
470
2
      // Discover a subloop of this loop.
471
2
      Subloop->setParentLoop(L);
472
2
      ++NumSubloops;
473
2
      NumBlocks += Subloop->getBlocksVector().capacity();
474
2
      PredBB = Subloop->getHeader();
475
2
      // Continue traversal along predecessors that are not loop-back edges from
476
2
      // within this subloop tree itself. Note that a predecessor may directly
477
2
      // reach another subloop that is not yet discovered to be a subloop of
478
2
      // this loop, which we must traverse.
479
4
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
480
4
        if (LI->getLoopFor(Pred) != Subloop)
481
2
          ReverseCFGWorklist.push_back(Pred);
482
4
      }
483
2
    }
484
11
  }
485
4
  L->getSubLoopsVector().reserve(NumSubloops);
486
4
  L->reserveBlocks(NumBlocks);
487
4
}
488
489
/// Populate all loop data in a stable order during a single forward DFS.
490
template <class BlockT, class LoopT> class PopulateLoopsDFS {
491
  typedef GraphTraits<BlockT *> BlockTraits;
492
  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
493
494
  LoopInfoBase<BlockT, LoopT> *LI;
495
496
public:
497
9.17M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>*)
Line
Count
Source
497
6.98M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>*)
Line
Count
Source
497
2.18M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>*)
Line
Count
Source
497
20
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
498
499
  void traverse(BlockT *EntryBlock);
500
501
protected:
502
  void insertIntoLoop(BlockT *Block);
503
};
504
505
/// Top-level driver for the forward DFS within the loop.
506
template <class BlockT, class LoopT>
507
9.17M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
9.17M
  for (BlockT *BB : post_order(EntryBlock))
509
53.3M
    insertIntoLoop(BB);
510
9.17M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*)
Line
Count
Source
507
6.98M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
6.98M
  for (BlockT *BB : post_order(EntryBlock))
509
41.9M
    insertIntoLoop(BB);
510
6.98M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*)
Line
Count
Source
507
2.18M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
2.18M
  for (BlockT *BB : post_order(EntryBlock))
509
11.3M
    insertIntoLoop(BB);
510
2.18M
}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::traverse(llvm::VPBlockBase*)
Line
Count
Source
507
20
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
20
  for (BlockT *BB : post_order(EntryBlock))
509
86
    insertIntoLoop(BB);
510
20
}
511
512
/// Add a single Block to its ancestor loops in PostOrder. If the block is a
513
/// subloop header, add the subloop to its parent in PostOrder, then reverse the
514
/// Block and Subloop vectors of the now complete subloop to achieve RPO.
515
template <class BlockT, class LoopT>
516
53.3M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
53.3M
  LoopT *Subloop = LI->getLoopFor(Block);
518
53.3M
  if (Subloop && 
Block == Subloop->getHeader()13.1M
) {
519
4.09M
    // We reach this point once per subloop after processing all the blocks in
520
4.09M
    // the subloop.
521
4.09M
    if (Subloop->getParentLoop())
522
1.08M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
3.00M
    else
524
3.00M
      LI->addTopLevelLoop(Subloop);
525
4.09M
526
4.09M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
4.09M
    // the lists, except for the loop header, which is always at the beginning.
528
4.09M
    Subloop->reverseBlock(1);
529
4.09M
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
4.09M
                 Subloop->getSubLoopsVector().end());
531
4.09M
532
4.09M
    Subloop = Subloop->getParentLoop();
533
4.09M
  }
534
66.7M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()13.4M
)
535
13.4M
    Subloop->addBlockEntry(Block);
536
53.3M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*)
Line
Count
Source
516
41.9M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
41.9M
  LoopT *Subloop = LI->getLoopFor(Block);
518
41.9M
  if (Subloop && 
Block == Subloop->getHeader()10.4M
) {
519
3.24M
    // We reach this point once per subloop after processing all the blocks in
520
3.24M
    // the subloop.
521
3.24M
    if (Subloop->getParentLoop())
522
867k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
2.37M
    else
524
2.37M
      LI->addTopLevelLoop(Subloop);
525
3.24M
526
3.24M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
3.24M
    // the lists, except for the loop header, which is always at the beginning.
528
3.24M
    Subloop->reverseBlock(1);
529
3.24M
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
3.24M
                 Subloop->getSubLoopsVector().end());
531
3.24M
532
3.24M
    Subloop = Subloop->getParentLoop();
533
3.24M
  }
534
52.6M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()10.6M
)
535
10.6M
    Subloop->addBlockEntry(Block);
536
41.9M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::insertIntoLoop(llvm::MachineBasicBlock*)
Line
Count
Source
516
11.3M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
11.3M
  LoopT *Subloop = LI->getLoopFor(Block);
518
11.3M
  if (Subloop && 
Block == Subloop->getHeader()2.70M
) {
519
849k
    // We reach this point once per subloop after processing all the blocks in
520
849k
    // the subloop.
521
849k
    if (Subloop->getParentLoop())
522
221k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
628k
    else
524
628k
      LI->addTopLevelLoop(Subloop);
525
849k
526
849k
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
849k
    // the lists, except for the loop header, which is always at the beginning.
528
849k
    Subloop->reverseBlock(1);
529
849k
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
849k
                 Subloop->getSubLoopsVector().end());
531
849k
532
849k
    Subloop = Subloop->getParentLoop();
533
849k
  }
534
14.1M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()2.77M
)
535
2.77M
    Subloop->addBlockEntry(Block);
536
11.3M
}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::insertIntoLoop(llvm::VPBlockBase*)
Line
Count
Source
516
86
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
86
  LoopT *Subloop = LI->getLoopFor(Block);
518
86
  if (Subloop && 
Block == Subloop->getHeader()46
) {
519
24
    // We reach this point once per subloop after processing all the blocks in
520
24
    // the subloop.
521
24
    if (Subloop->getParentLoop())
522
4
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
20
    else
524
20
      LI->addTopLevelLoop(Subloop);
525
24
526
24
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
24
    // the lists, except for the loop header, which is always at the beginning.
528
24
    Subloop->reverseBlock(1);
529
24
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
24
                 Subloop->getSubLoopsVector().end());
531
24
532
24
    Subloop = Subloop->getParentLoop();
533
24
  }
534
120
  for (; Subloop; 
Subloop = Subloop->getParentLoop()34
)
535
34
    Subloop->addBlockEntry(Block);
536
86
}
537
538
/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
539
/// interleaved with backward CFG traversals within each subloop
540
/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
541
/// this part of the algorithm is linear in the number of CFG edges. Subloop and
542
/// Block vectors are then populated during a single forward CFG traversal
543
/// (PopulateLoopDFS).
544
///
545
/// During the two CFG traversals each block is seen three times:
546
/// 1) Discovered and mapped by a reverse CFG traversal.
547
/// 2) Visited during a forward DFS CFG traversal.
548
/// 3) Reverse-inserted in the loop in postorder following forward DFS.
549
///
550
/// The Block vectors are inclusive, so step 3 requires loop-depth number of
551
/// insertions per block.
552
template <class BlockT, class LoopT>
553
9.17M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
9.17M
  // Postorder traversal of the dominator tree.
555
9.17M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
53.3M
  for (auto DomNode : post_order(DomRoot)) {
557
53.3M
558
53.3M
    BlockT *Header = DomNode->getBlock();
559
53.3M
    SmallVector<BlockT *, 4> Backedges;
560
53.3M
561
53.3M
    // Check each predecessor of the potential loop header.
562
69.0M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
69.0M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
69.0M
      if (DomTree.dominates(Header, Backedge) &&
565
69.0M
          
DomTree.isReachableFromEntry(Backedge)4.14M
) {
566
4.14M
        Backedges.push_back(Backedge);
567
4.14M
      }
568
69.0M
    }
569
53.3M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
53.3M
    if (!Backedges.empty()) {
571
4.09M
      LoopT *L = AllocateLoop(Header);
572
4.09M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
4.09M
    }
574
53.3M
  }
575
9.17M
  // Perform a single forward CFG traversal to populate block and subloop
576
9.17M
  // vectors for all loops.
577
9.17M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
9.17M
  DFS.traverse(DomRoot->getBlock());
579
9.17M
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
553
6.98M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
6.98M
  // Postorder traversal of the dominator tree.
555
6.98M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
41.9M
  for (auto DomNode : post_order(DomRoot)) {
557
41.9M
558
41.9M
    BlockT *Header = DomNode->getBlock();
559
41.9M
    SmallVector<BlockT *, 4> Backedges;
560
41.9M
561
41.9M
    // Check each predecessor of the potential loop header.
562
55.0M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
55.0M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
55.0M
      if (DomTree.dominates(Header, Backedge) &&
565
55.0M
          
DomTree.isReachableFromEntry(Backedge)3.26M
) {
566
3.26M
        Backedges.push_back(Backedge);
567
3.26M
      }
568
55.0M
    }
569
41.9M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
41.9M
    if (!Backedges.empty()) {
571
3.24M
      LoopT *L = AllocateLoop(Header);
572
3.24M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
3.24M
    }
574
41.9M
  }
575
6.98M
  // Perform a single forward CFG traversal to populate block and subloop
576
6.98M
  // vectors for all loops.
577
6.98M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
6.98M
  DFS.traverse(DomRoot->getBlock());
579
6.98M
}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
553
2.18M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
2.18M
  // Postorder traversal of the dominator tree.
555
2.18M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
11.3M
  for (auto DomNode : post_order(DomRoot)) {
557
11.3M
558
11.3M
    BlockT *Header = DomNode->getBlock();
559
11.3M
    SmallVector<BlockT *, 4> Backedges;
560
11.3M
561
11.3M
    // Check each predecessor of the potential loop header.
562
13.9M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
13.9M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
13.9M
      if (DomTree.dominates(Header, Backedge) &&
565
13.9M
          
DomTree.isReachableFromEntry(Backedge)876k
) {
566
876k
        Backedges.push_back(Backedge);
567
876k
      }
568
13.9M
    }
569
11.3M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
11.3M
    if (!Backedges.empty()) {
571
849k
      LoopT *L = AllocateLoop(Header);
572
849k
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
849k
    }
574
11.3M
  }
575
2.18M
  // Perform a single forward CFG traversal to populate block and subloop
576
2.18M
  // vectors for all loops.
577
2.18M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
2.18M
  DFS.traverse(DomRoot->getBlock());
579
2.18M
}
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::analyze(llvm::DominatorTreeBase<llvm::VPBlockBase, false> const&)
Line
Count
Source
553
20
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
20
  // Postorder traversal of the dominator tree.
555
20
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
86
  for (auto DomNode : post_order(DomRoot)) {
557
86
558
86
    BlockT *Header = DomNode->getBlock();
559
86
    SmallVector<BlockT *, 4> Backedges;
560
86
561
86
    // Check each predecessor of the potential loop header.
562
97
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
97
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
97
      if (DomTree.dominates(Header, Backedge) &&
565
97
          
DomTree.isReachableFromEntry(Backedge)24
) {
566
24
        Backedges.push_back(Backedge);
567
24
      }
568
97
    }
569
86
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
86
    if (!Backedges.empty()) {
571
24
      LoopT *L = AllocateLoop(Header);
572
24
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
24
    }
574
86
  }
575
20
  // Perform a single forward CFG traversal to populate block and subloop
576
20
  // vectors for all loops.
577
20
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
20
  DFS.traverse(DomRoot->getBlock());
579
20
}
580
581
template <class BlockT, class LoopT>
582
277k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
583
277k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
584
277k
  // The outer-most loop actually goes into the result in the same relative
585
277k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
586
277k
  // program order so for here we reverse it to get forward program order.
587
277k
  // FIXME: If we change the order of LoopInfo we will want to remove the
588
277k
  // reverse here.
589
277k
  for (LoopT *RootL : reverse(*this)) {
590
133k
    assert(PreOrderWorklist.empty() &&
591
133k
           "Must start with an empty preorder walk worklist.");
592
133k
    PreOrderWorklist.push_back(RootL);
593
183k
    do {
594
183k
      LoopT *L = PreOrderWorklist.pop_back_val();
595
183k
      // Sub-loops are stored in forward program order, but will process the
596
183k
      // worklist backwards so append them in reverse order.
597
183k
      PreOrderWorklist.append(L->rbegin(), L->rend());
598
183k
      PreOrderLoops.push_back(L);
599
183k
    } while (!PreOrderWorklist.empty());
600
133k
  }
601
277k
602
277k
  return PreOrderLoops;
603
277k
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder()
Line
Count
Source
582
277k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
583
277k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
584
277k
  // The outer-most loop actually goes into the result in the same relative
585
277k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
586
277k
  // program order so for here we reverse it to get forward program order.
587
277k
  // FIXME: If we change the order of LoopInfo we will want to remove the
588
277k
  // reverse here.
589
277k
  for (LoopT *RootL : reverse(*this)) {
590
133k
    assert(PreOrderWorklist.empty() &&
591
133k
           "Must start with an empty preorder walk worklist.");
592
133k
    PreOrderWorklist.push_back(RootL);
593
183k
    do {
594
183k
      LoopT *L = PreOrderWorklist.pop_back_val();
595
183k
      // Sub-loops are stored in forward program order, but will process the
596
183k
      // worklist backwards so append them in reverse order.
597
183k
      PreOrderWorklist.append(L->rbegin(), L->rend());
598
183k
      PreOrderLoops.push_back(L);
599
183k
    } while (!PreOrderWorklist.empty());
600
133k
  }
601
277k
602
277k
  return PreOrderLoops;
603
277k
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder()
604
605
template <class BlockT, class LoopT>
606
SmallVector<LoopT *, 4>
607
707
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
608
707
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
609
707
  // The outer-most loop actually goes into the result in the same relative
610
707
  // order as we walk it. LoopInfo stores the top level loops in reverse
611
707
  // program order so we walk in order here.
612
707
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
613
707
  // here.
614
1.01k
  for (LoopT *RootL : *this) {
615
1.01k
    assert(PreOrderWorklist.empty() &&
616
1.01k
           "Must start with an empty preorder walk worklist.");
617
1.01k
    PreOrderWorklist.push_back(RootL);
618
1.57k
    do {
619
1.57k
      LoopT *L = PreOrderWorklist.pop_back_val();
620
1.57k
      // Sub-loops are stored in forward program order, but will process the
621
1.57k
      // worklist backwards so we can just append them in order.
622
1.57k
      PreOrderWorklist.append(L->begin(), L->end());
623
1.57k
      PreOrderLoops.push_back(L);
624
1.57k
    } while (!PreOrderWorklist.empty());
625
1.01k
  }
626
707
627
707
  return PreOrderLoops;
628
707
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder()
Line
Count
Source
607
707
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
608
707
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
609
707
  // The outer-most loop actually goes into the result in the same relative
610
707
  // order as we walk it. LoopInfo stores the top level loops in reverse
611
707
  // program order so we walk in order here.
612
707
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
613
707
  // here.
614
1.01k
  for (LoopT *RootL : *this) {
615
1.01k
    assert(PreOrderWorklist.empty() &&
616
1.01k
           "Must start with an empty preorder walk worklist.");
617
1.01k
    PreOrderWorklist.push_back(RootL);
618
1.57k
    do {
619
1.57k
      LoopT *L = PreOrderWorklist.pop_back_val();
620
1.57k
      // Sub-loops are stored in forward program order, but will process the
621
1.57k
      // worklist backwards so we can just append them in order.
622
1.57k
      PreOrderWorklist.append(L->begin(), L->end());
623
1.57k
      PreOrderLoops.push_back(L);
624
1.57k
    } while (!PreOrderWorklist.empty());
625
1.01k
  }
626
707
627
707
  return PreOrderLoops;
628
707
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInReverseSiblingPreorder()
629
630
// Debugging
631
template <class BlockT, class LoopT>
632
34
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
633
264
  for (unsigned i = 0; i < TopLevelLoops.size(); 
++i230
)
634
230
    TopLevelLoops[i]->print(OS);
635
34
#if 0
636
34
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
637
34
         E = BBMap.end(); I != E; ++I)
638
34
    OS << "BB '" << I->first->getName() << "' level = "
639
34
       << I->second->getLoopDepth() << "\n";
640
34
#endif
641
34
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&) const
Line
Count
Source
632
34
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
633
264
  for (unsigned i = 0; i < TopLevelLoops.size(); 
++i230
)
634
230
    TopLevelLoops[i]->print(OS);
635
34
#if 0
636
34
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
637
34
         E = BBMap.end(); I != E; ++I)
638
34
    OS << "BB '" << I->first->getName() << "' level = "
639
34
       << I->second->getLoopDepth() << "\n";
640
34
#endif
641
34
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&) const
642
643
template <typename T>
644
bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
645
  llvm::sort(BB1);
646
  llvm::sort(BB2);
647
  return BB1 == BB2;
648
}
649
650
template <class BlockT, class LoopT>
651
void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
652
                               const LoopInfoBase<BlockT, LoopT> &LI,
653
                               const LoopT &L) {
654
  LoopHeaders[L.getHeader()] = &L;
655
  for (LoopT *SL : L)
656
    addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
657
}
658
659
#ifndef NDEBUG
660
template <class BlockT, class LoopT>
661
static void compareLoops(const LoopT *L, const LoopT *OtherL,
662
                         DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
663
  BlockT *H = L->getHeader();
664
  BlockT *OtherH = OtherL->getHeader();
665
  assert(H == OtherH &&
666
         "Mismatched headers even though found in the same map entry!");
667
668
  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
669
         "Mismatched loop depth!");
670
  const LoopT *ParentL = L, *OtherParentL = OtherL;
671
  do {
672
    assert(ParentL->getHeader() == OtherParentL->getHeader() &&
673
           "Mismatched parent loop headers!");
674
    ParentL = ParentL->getParentLoop();
675
    OtherParentL = OtherParentL->getParentLoop();
676
  } while (ParentL);
677
678
  for (const LoopT *SubL : *L) {
679
    BlockT *SubH = SubL->getHeader();
680
    const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
681
    assert(OtherSubL && "Inner loop is missing in computed loop info!");
682
    OtherLoopHeaders.erase(SubH);
683
    compareLoops(SubL, OtherSubL, OtherLoopHeaders);
684
  }
685
686
  std::vector<BlockT *> BBs = L->getBlocks();
687
  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
688
  assert(compareVectors(BBs, OtherBBs) &&
689
         "Mismatched basic blocks in the loops!");
690
691
  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
692
  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = L->getBlocksSet();
693
  assert(BlocksSet.size() == OtherBlocksSet.size() &&
694
         std::all_of(BlocksSet.begin(), BlocksSet.end(),
695
                     [&OtherBlocksSet](const BlockT *BB) {
696
                       return OtherBlocksSet.count(BB);
697
                     }) &&
698
         "Mismatched basic blocks in BlocksSets!");
699
}
700
#endif
701
702
template <class BlockT, class LoopT>
703
void LoopInfoBase<BlockT, LoopT>::verify(
704
137
    const DomTreeBase<BlockT> &DomTree) const {
705
137
  DenseSet<const LoopT *> Loops;
706
324
  for (iterator I = begin(), E = end(); I != E; 
++I187
) {
707
187
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
708
187
    (*I)->verifyLoopNest(&Loops);
709
187
  }
710
137
711
137
// Verify that blocks are mapped to valid loops.
712
137
#ifndef NDEBUG
713
137
  for (auto &Entry : BBMap) {
714
137
    const BlockT *BB = Entry.first;
715
137
    LoopT *L = Entry.second;
716
137
    assert(Loops.count(L) && "orphaned loop");
717
137
    assert(L->contains(BB) && "orphaned block");
718
137
    for (LoopT *ChildLoop : *L)
719
137
      assert(!ChildLoop->contains(BB) &&
720
137
             "BBMap should point to the innermost loop containing BB");
721
137
  }
722
137
723
137
  // Recompute LoopInfo to verify loops structure.
724
137
  LoopInfoBase<BlockT, LoopT> OtherLI;
725
137
  OtherLI.analyze(DomTree);
726
137
727
137
  // Build a map we can use to move from our LI to the computed one. This
728
137
  // allows us to ignore the particular order in any layer of the loop forest
729
137
  // while still comparing the structure.
730
137
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
731
137
  for (LoopT *L : OtherLI)
732
137
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
733
137
734
137
  // Walk the top level loops and ensure there is a corresponding top-level
735
137
  // loop in the computed version and then recursively compare those loop
736
137
  // nests.
737
137
  for (LoopT *L : *this) {
738
137
    BlockT *Header = L->getHeader();
739
137
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
740
137
    assert(OtherL && "Top level loop is missing in computed loop info!");
741
137
    // Now that we've matched this loop, erase its header from the map.
742
137
    OtherLoopHeaders.erase(Header);
743
137
    // And recursively compare these loops.
744
137
    compareLoops(L, OtherL, OtherLoopHeaders);
745
137
  }
746
137
747
137
  // Any remaining entries in the map are loops which were found when computing
748
137
  // a fresh LoopInfo but not present in the current one.
749
137
  if (!OtherLoopHeaders.empty()) {
750
137
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
751
137
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
752
137
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
753
137
  }
754
137
#endif
755
137
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) const
Line
Count
Source
704
137
    const DomTreeBase<BlockT> &DomTree) const {
705
137
  DenseSet<const LoopT *> Loops;
706
324
  for (iterator I = begin(), E = end(); I != E; 
++I187
) {
707
187
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
708
187
    (*I)->verifyLoopNest(&Loops);
709
187
  }
710
137
711
137
// Verify that blocks are mapped to valid loops.
712
137
#ifndef NDEBUG
713
137
  for (auto &Entry : BBMap) {
714
137
    const BlockT *BB = Entry.first;
715
137
    LoopT *L = Entry.second;
716
137
    assert(Loops.count(L) && "orphaned loop");
717
137
    assert(L->contains(BB) && "orphaned block");
718
137
    for (LoopT *ChildLoop : *L)
719
137
      assert(!ChildLoop->contains(BB) &&
720
137
             "BBMap should point to the innermost loop containing BB");
721
137
  }
722
137
723
137
  // Recompute LoopInfo to verify loops structure.
724
137
  LoopInfoBase<BlockT, LoopT> OtherLI;
725
137
  OtherLI.analyze(DomTree);
726
137
727
137
  // Build a map we can use to move from our LI to the computed one. This
728
137
  // allows us to ignore the particular order in any layer of the loop forest
729
137
  // while still comparing the structure.
730
137
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
731
137
  for (LoopT *L : OtherLI)
732
137
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
733
137
734
137
  // Walk the top level loops and ensure there is a corresponding top-level
735
137
  // loop in the computed version and then recursively compare those loop
736
137
  // nests.
737
137
  for (LoopT *L : *this) {
738
137
    BlockT *Header = L->getHeader();
739
137
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
740
137
    assert(OtherL && "Top level loop is missing in computed loop info!");
741
137
    // Now that we've matched this loop, erase its header from the map.
742
137
    OtherLoopHeaders.erase(Header);
743
137
    // And recursively compare these loops.
744
137
    compareLoops(L, OtherL, OtherLoopHeaders);
745
137
  }
746
137
747
137
  // Any remaining entries in the map are loops which were found when computing
748
137
  // a fresh LoopInfo but not present in the current one.
749
137
  if (!OtherLoopHeaders.empty()) {
750
137
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
751
137
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
752
137
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
753
137
  }
754
137
#endif
755
137
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) const
756
757
} // End llvm namespace
758
759
#endif