Coverage Report

Created: 2019-03-24 22:13

/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.11M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
7.11M
  assert(!isInvalid() && "Loop not in a valid state!");
37
7.11M
  for (const auto BB : blocks())
38
28.5M
    for (const auto &Succ : children<BlockT *>(BB))
39
43.3M
      if (!contains(Succ)) {
40
9.38M
        // Not in current loop? It must be an exit block.
41
9.38M
        ExitingBlocks.push_back(BB);
42
9.38M
        break;
43
9.38M
      }
44
7.11M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
35
7.07M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
7.07M
  assert(!isInvalid() && "Loop not in a valid state!");
37
7.07M
  for (const auto BB : blocks())
38
26.3M
    for (const auto &Succ : children<BlockT *>(BB))
39
39.9M
      if (!contains(Succ)) {
40
9.21M
        // Not in current loop? It must be an exit block.
41
9.21M
        ExitingBlocks.push_back(BB);
42
9.21M
        break;
43
9.21M
      }
44
7.07M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
35
44.2k
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36
44.2k
  assert(!isInvalid() && "Loop not in a valid state!");
37
44.2k
  for (const auto BB : blocks())
38
2.15M
    for (const auto &Succ : children<BlockT *>(BB))
39
3.48M
      if (!contains(Succ)) {
40
163k
        // Not in current loop? It must be an exit block.
41
163k
        ExitingBlocks.push_back(BB);
42
163k
        break;
43
163k
      }
44
44.2k
}
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.74M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
50
3.74M
  assert(!isInvalid() && "Loop not in a valid state!");
51
3.74M
  SmallVector<BlockT *, 8> ExitingBlocks;
52
3.74M
  getExitingBlocks(ExitingBlocks);
53
3.74M
  if (ExitingBlocks.size() == 1)
54
3.17M
    return ExitingBlocks[0];
55
562k
  return nullptr;
56
562k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const
Line
Count
Source
49
3.74M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
50
3.74M
  assert(!isInvalid() && "Loop not in a valid state!");
51
3.74M
  SmallVector<BlockT *, 8> ExitingBlocks;
52
3.74M
  getExitingBlocks(ExitingBlocks);
53
3.74M
  if (ExitingBlocks.size() == 1)
54
3.17M
    return ExitingBlocks[0];
55
562k
  return nullptr;
56
562k
}
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.62M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
64
8.62M
  assert(!isInvalid() && "Loop not in a valid state!");
65
8.62M
  for (const auto BB : blocks())
66
47.7M
    for (const auto &Succ : children<BlockT *>(BB))
67
80.1M
      if (!contains(Succ))
68
12.1M
        // Not in current loop? It must be an exit block.
69
12.1M
        ExitBlocks.push_back(Succ);
70
8.62M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
63
8.31M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
64
8.31M
  assert(!isInvalid() && "Loop not in a valid state!");
65
8.31M
  for (const auto BB : blocks())
66
46.4M
    for (const auto &Succ : children<BlockT *>(BB))
67
77.8M
      if (!contains(Succ))
68
11.7M
        // Not in current loop? It must be an exit block.
69
11.7M
        ExitBlocks.push_back(Succ);
70
8.31M
}
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.1k
  return nullptr;
82
54.1k
}
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.1k
  return nullptr;
82
54.1k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const
83
84
template <class BlockT, class LoopT>
85
4.67M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
86
4.67M
  // Each predecessor of each exit block of a normal loop is contained
87
4.67M
  // within the loop.
88
4.67M
  SmallVector<BlockT *, 4> ExitBlocks;
89
4.67M
  getExitBlocks(ExitBlocks);
90
4.67M
  for (BlockT *EB : ExitBlocks)
91
6.40M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
92
12.5M
      if (!contains(Predecessor))
93
83
        return false;
94
4.67M
  // All the requirements are met.
95
4.67M
  
return true4.67M
;
96
4.67M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::hasDedicatedExits() const
Line
Count
Source
85
4.67M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
86
4.67M
  // Each predecessor of each exit block of a normal loop is contained
87
4.67M
  // within the loop.
88
4.67M
  SmallVector<BlockT *, 4> ExitBlocks;
89
4.67M
  getExitBlocks(ExitBlocks);
90
4.67M
  for (BlockT *EB : ExitBlocks)
91
6.40M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
92
12.5M
      if (!contains(Predecessor))
93
83
        return false;
94
4.67M
  // All the requirements are met.
95
4.67M
  
return true4.67M
;
96
4.67M
}
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.09M
  for (BlockT *Block : this->blocks()) {
109
6.09M
    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.38M
        continue;
114
2.00M
115
2.00M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
116
2.00M
117
2.00M
      // If current basic block is this exit block's first predecessor then only
118
2.00M
      // insert exit block in to the output ExitBlocks vector. This ensures that
119
2.00M
      // same exit block is not inserted twice into ExitBlocks vector.
120
2.00M
      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.09M
  }
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.09M
  for (BlockT *Block : this->blocks()) {
109
6.09M
    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.38M
        continue;
114
2.00M
115
2.00M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
116
2.00M
117
2.00M
      // If current basic block is this exit block's first predecessor then only
118
2.00M
      // insert exit block in to the output ExitBlocks vector. This ensures that
119
2.00M
      // same exit block is not inserted twice into ExitBlocks vector.
120
2.00M
      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.09M
  }
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
484k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
145
484k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
146
484k
  getUniqueExitBlocks(UniqueExitBlocks);
147
484k
  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
484k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
145
484k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
146
484k
  getUniqueExitBlocks(UniqueExitBlocks);
147
484k
  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.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
174
11.5M
  assert(!isInvalid() && "Loop not in a valid state!");
175
11.5M
  // Keep track of nodes outside the loop branching to the header...
176
11.5M
  BlockT *Out = getLoopPredecessor();
177
11.5M
  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
497k
    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.2M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
174
11.2M
  assert(!isInvalid() && "Loop not in a valid state!");
175
11.2M
  // Keep track of nodes outside the loop branching to the header...
176
11.2M
  BlockT *Out = getLoopPredecessor();
177
11.2M
  if (!Out)
178
19.2k
    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
477k
    return nullptr; // Multiple exits from the block, must not be a preheader.
190
10.7M
191
10.7M
  // The predecessor has exactly one successor, so it is a preheader.
192
10.7M
  return Out;
193
10.7M
}
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.6k
    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
13.0M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
13.0M
  assert(!isInvalid() && "Loop not in a valid state!");
203
13.0M
  // Keep track of nodes outside the loop branching to the header...
204
13.0M
  BlockT *Out = nullptr;
205
13.0M
206
13.0M
  // Loop over the predecessors of the header node...
207
13.0M
  BlockT *Header = getHeader();
208
25.9M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
25.9M
    if (!contains(Pred)) { // If the block is not in the loop...
210
13.0M
      if (Out && 
Out != Pred23.9k
)
211
23.7k
        return nullptr; // Multiple predecessors outside the loop
212
13.0M
      Out = Pred;
213
13.0M
    }
214
25.9M
  }
215
13.0M
216
13.0M
  // Make sure there is only one exit out of the preheader.
217
13.0M
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
12.9M
  return Out;
219
13.0M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPredecessor() const
Line
Count
Source
201
12.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
12.5M
  assert(!isInvalid() && "Loop not in a valid state!");
203
12.5M
  // Keep track of nodes outside the loop branching to the header...
204
12.5M
  BlockT *Out = nullptr;
205
12.5M
206
12.5M
  // Loop over the predecessors of the header node...
207
12.5M
  BlockT *Header = getHeader();
208
24.9M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
24.9M
    if (!contains(Pred)) { // If the block is not in the loop...
210
12.5M
      if (Out && 
Out != Pred19.4k
)
211
19.2k
        return nullptr; // Multiple predecessors outside the loop
212
12.5M
      Out = Pred;
213
12.5M
    }
214
24.9M
  }
215
12.5M
216
12.5M
  // Make sure there is only one exit out of the preheader.
217
12.5M
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
12.5M
  return Out;
219
12.5M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const
Line
Count
Source
201
481k
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
202
481k
  assert(!isInvalid() && "Loop not in a valid state!");
203
481k
  // Keep track of nodes outside the loop branching to the header...
204
481k
  BlockT *Out = nullptr;
205
481k
206
481k
  // Loop over the predecessors of the header node...
207
481k
  BlockT *Header = getHeader();
208
987k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
209
987k
    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
481k
      Out = Pred;
213
481k
    }
214
987k
  }
215
481k
216
481k
  // Make sure there is only one exit out of the preheader.
217
481k
  assert(Out && "Header of loop has no predecessors from outside loop?");
218
476k
  return Out;
219
481k
}
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.1M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
29.1M
    if (contains(Pred)) {
230
14.5M
      if (Latch)
231
7.14k
        return nullptr;
232
14.5M
      Latch = Pred;
233
14.5M
    }
234
29.1M
  }
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.1M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
29.1M
    if (contains(Pred)) {
230
14.5M
      if (Latch)
231
7.13k
        return nullptr;
232
14.5M
      Latch = Pred;
233
14.5M
    }
234
29.1M
  }
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.00k
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
225
3.00k
  assert(!isInvalid() && "Loop not in a valid state!");
226
3.00k
  BlockT *Header = getHeader();
227
3.00k
  BlockT *Latch = nullptr;
228
6.04k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
229
6.04k
    if (contains(Pred)) {
230
3.01k
      if (Latch)
231
4
        return nullptr;
232
3.00k
      Latch = Pred;
233
3.00k
    }
234
6.04k
  }
235
3.00k
236
3.00k
  
return Latch3.00k
;
237
3.00k
}
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
811k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
811k
  assert(!isInvalid() && "Loop not in a valid state!");
253
811k
#ifndef NDEBUG
254
811k
  if (!Blocks.empty()) {
255
811k
    auto SameHeader = LIB[getHeader()];
256
811k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
811k
           "Incorrect LI specified for this loop!");
258
811k
  }
259
811k
#endif
260
811k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
811k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
811k
263
811k
  LoopT *L = static_cast<LoopT *>(this);
264
811k
265
811k
  // Add the loop mapping to the LoopInfo object...
266
811k
  LIB.BBMap[NewBB] = L;
267
811k
268
811k
  // Add the basic block to this loop and all parent loops...
269
2.03M
  while (L) {
270
1.22M
    L->addBlockEntry(NewBB);
271
1.22M
    L = L->getParentLoop();
272
1.22M
  }
273
811k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&)
Line
Count
Source
251
767k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
767k
  assert(!isInvalid() && "Loop not in a valid state!");
253
767k
#ifndef NDEBUG
254
767k
  if (!Blocks.empty()) {
255
767k
    auto SameHeader = LIB[getHeader()];
256
767k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
767k
           "Incorrect LI specified for this loop!");
258
767k
  }
259
767k
#endif
260
767k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
767k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
767k
263
767k
  LoopT *L = static_cast<LoopT *>(this);
264
767k
265
767k
  // Add the loop mapping to the LoopInfo object...
266
767k
  LIB.BBMap[NewBB] = L;
267
767k
268
767k
  // Add the basic block to this loop and all parent loops...
269
1.92M
  while (L) {
270
1.15M
    L->addBlockEntry(NewBB);
271
1.15M
    L = L->getParentLoop();
272
1.15M
  }
273
767k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&)
Line
Count
Source
251
44.8k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
252
44.8k
  assert(!isInvalid() && "Loop not in a valid state!");
253
44.8k
#ifndef NDEBUG
254
44.8k
  if (!Blocks.empty()) {
255
44.8k
    auto SameHeader = LIB[getHeader()];
256
44.8k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
257
44.8k
           "Incorrect LI specified for this loop!");
258
44.8k
  }
259
44.8k
#endif
260
44.8k
  assert(NewBB && "Cannot add a null basic block to the loop!");
261
44.8k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
262
44.8k
263
44.8k
  LoopT *L = static_cast<LoopT *>(this);
264
44.8k
265
44.8k
  // Add the loop mapping to the LoopInfo object...
266
44.8k
  LIB.BBMap[NewBB] = L;
267
44.8k
268
44.8k
  // Add the basic block to this loop and all parent loops...
269
110k
  while (L) {
270
65.5k
    L->addBlockEntry(NewBB);
271
65.5k
    L = L->getParentLoop();
272
65.5k
  }
273
44.8k
}
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.10M
                                  const DomTreeBase<BlockT> &DomTree) {
436
4.10M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
4.10M
438
4.10M
  unsigned NumBlocks = 0;
439
4.10M
  unsigned NumSubloops = 0;
440
4.10M
441
4.10M
  // Perform a backward CFG traversal using a worklist.
442
4.10M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
22.7M
  while (!ReverseCFGWorklist.empty()) {
444
18.6M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
18.6M
    ReverseCFGWorklist.pop_back();
446
18.6M
447
18.6M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
18.6M
    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.10M
        continue;
457
9.07M
      // Push all block predecessors on the worklist.
458
9.07M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
9.07M
                                InvBlockTraits::child_begin(PredBB),
460
9.07M
                                InvBlockTraits::child_end(PredBB));
461
9.07M
    } else {
462
5.50M
      // This is a discovered block. Find its outermost discovered loop.
463
5.72M
      while (LoopT *Parent = Subloop->getParentLoop())
464
212k
        Subloop = Parent;
465
5.50M
466
5.50M
      // If it is already discovered to be a subloop of this loop, continue.
467
5.50M
      if (Subloop == L)
468
4.41M
        continue;
469
1.09M
470
1.09M
      // Discover a subloop of this loop.
471
1.09M
      Subloop->setParentLoop(L);
472
1.09M
      ++NumSubloops;
473
1.09M
      NumBlocks += Subloop->getBlocksVector().capacity();
474
1.09M
      PredBB = Subloop->getHeader();
475
1.09M
      // Continue traversal along predecessors that are not loop-back edges from
476
1.09M
      // within this subloop tree itself. Note that a predecessor may directly
477
1.09M
      // reach another subloop that is not yet discovered to be a subloop of
478
1.09M
      // 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.10M
          ReverseCFGWorklist.push_back(Pred);
482
2.19M
      }
483
1.09M
    }
484
18.6M
  }
485
4.10M
  L->getSubLoopsVector().reserve(NumSubloops);
486
4.10M
  L->reserveBlocks(NumBlocks);
487
4.10M
}
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.8M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
14.8M
    ReverseCFGWorklist.pop_back();
446
14.8M
447
14.8M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
14.8M
    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.22M
      // Push all block predecessors on the worklist.
458
7.22M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
7.22M
                                InvBlockTraits::child_begin(PredBB),
460
7.22M
                                InvBlockTraits::child_end(PredBB));
461
7.22M
    } else {
462
4.40M
      // This is a discovered block. Find its outermost discovered loop.
463
4.57M
      while (LoopT *Parent = Subloop->getParentLoop())
464
161k
        Subloop = Parent;
465
4.40M
466
4.40M
      // If it is already discovered to be a subloop of this loop, continue.
467
4.40M
      if (Subloop == L)
468
3.53M
        continue;
469
870k
470
870k
      // Discover a subloop of this loop.
471
870k
      Subloop->setParentLoop(L);
472
870k
      ++NumSubloops;
473
870k
      NumBlocks += Subloop->getBlocksVector().capacity();
474
870k
      PredBB = Subloop->getHeader();
475
870k
      // Continue traversal along predecessors that are not loop-back edges from
476
870k
      // within this subloop tree itself. Note that a predecessor may directly
477
870k
      // reach another subloop that is not yet discovered to be a subloop of
478
870k
      // 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
877k
          ReverseCFGWorklist.push_back(Pred);
482
1.74M
      }
483
870k
    }
484
14.8M
  }
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
851k
                                  const DomTreeBase<BlockT> &DomTree) {
436
851k
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
437
851k
438
851k
  unsigned NumBlocks = 0;
439
851k
  unsigned NumSubloops = 0;
440
851k
441
851k
  // Perform a backward CFG traversal using a worklist.
442
851k
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
443
4.64M
  while (!ReverseCFGWorklist.empty()) {
444
3.79M
    BlockT *PredBB = ReverseCFGWorklist.back();
445
3.79M
    ReverseCFGWorklist.pop_back();
446
3.79M
447
3.79M
    LoopT *Subloop = LI->getLoopFor(PredBB);
448
3.79M
    if (!Subloop) {
449
2.69M
      if (!DomTree.isReachableFromEntry(PredBB))
450
0
        continue;
451
2.69M
452
2.69M
      // This is an undiscovered block. Map it to the current loop.
453
2.69M
      LI->changeLoopFor(PredBB, L);
454
2.69M
      ++NumBlocks;
455
2.69M
      if (PredBB == L->getHeader())
456
851k
        continue;
457
1.84M
      // Push all block predecessors on the worklist.
458
1.84M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
459
1.84M
                                InvBlockTraits::child_begin(PredBB),
460
1.84M
                                InvBlockTraits::child_end(PredBB));
461
1.84M
    } else {
462
1.09M
      // This is a discovered block. Find its outermost discovered loop.
463
1.14M
      while (LoopT *Parent = Subloop->getParentLoop())
464
51.1k
        Subloop = Parent;
465
1.09M
466
1.09M
      // If it is already discovered to be a subloop of this loop, continue.
467
1.09M
      if (Subloop == L)
468
875k
        continue;
469
222k
470
222k
      // Discover a subloop of this loop.
471
222k
      Subloop->setParentLoop(L);
472
222k
      ++NumSubloops;
473
222k
      NumBlocks += Subloop->getBlocksVector().capacity();
474
222k
      PredBB = Subloop->getHeader();
475
222k
      // Continue traversal along predecessors that are not loop-back edges from
476
222k
      // within this subloop tree itself. Note that a predecessor may directly
477
222k
      // reach another subloop that is not yet discovered to be a subloop of
478
222k
      // this loop, which we must traverse.
479
449k
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
480
449k
        if (LI->getLoopFor(Pred) != Subloop)
481
224k
          ReverseCFGWorklist.push_back(Pred);
482
449k
      }
483
222k
    }
484
3.79M
  }
485
851k
  L->getSubLoopsVector().reserve(NumSubloops);
486
851k
  L->reserveBlocks(NumBlocks);
487
851k
}
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.18M
  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.99M
  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.19M
  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.18M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
9.18M
  for (BlockT *BB : post_order(EntryBlock))
509
52.6M
    insertIntoLoop(BB);
510
9.18M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*)
Line
Count
Source
507
6.99M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
6.99M
  for (BlockT *BB : post_order(EntryBlock))
509
41.4M
    insertIntoLoop(BB);
510
6.99M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*)
Line
Count
Source
507
2.19M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
508
2.19M
  for (BlockT *BB : post_order(EntryBlock))
509
11.1M
    insertIntoLoop(BB);
510
2.19M
}
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
52.6M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
52.6M
  LoopT *Subloop = LI->getLoopFor(Block);
518
52.6M
  if (Subloop && 
Block == Subloop->getHeader()13.1M
) {
519
4.10M
    // We reach this point once per subloop after processing all the blocks in
520
4.10M
    // the subloop.
521
4.10M
    if (Subloop->getParentLoop())
522
1.09M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
3.00M
    else
524
3.00M
      LI->addTopLevelLoop(Subloop);
525
4.10M
526
4.10M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
4.10M
    // the lists, except for the loop header, which is always at the beginning.
528
4.10M
    Subloop->reverseBlock(1);
529
4.10M
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
4.10M
                 Subloop->getSubLoopsVector().end());
531
4.10M
532
4.10M
    Subloop = Subloop->getParentLoop();
533
4.10M
  }
534
66.0M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()13.4M
)
535
13.4M
    Subloop->addBlockEntry(Block);
536
52.6M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*)
Line
Count
Source
516
41.4M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
41.4M
  LoopT *Subloop = LI->getLoopFor(Block);
518
41.4M
  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
870k
      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.1M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()10.6M
)
535
10.6M
    Subloop->addBlockEntry(Block);
536
41.4M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::insertIntoLoop(llvm::MachineBasicBlock*)
Line
Count
Source
516
11.1M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
517
11.1M
  LoopT *Subloop = LI->getLoopFor(Block);
518
11.1M
  if (Subloop && 
Block == Subloop->getHeader()2.69M
) {
519
851k
    // We reach this point once per subloop after processing all the blocks in
520
851k
    // the subloop.
521
851k
    if (Subloop->getParentLoop())
522
222k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
523
628k
    else
524
628k
      LI->addTopLevelLoop(Subloop);
525
851k
526
851k
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
527
851k
    // the lists, except for the loop header, which is always at the beginning.
528
851k
    Subloop->reverseBlock(1);
529
851k
    std::reverse(Subloop->getSubLoopsVector().begin(),
530
851k
                 Subloop->getSubLoopsVector().end());
531
851k
532
851k
    Subloop = Subloop->getParentLoop();
533
851k
  }
534
13.9M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()2.76M
)
535
2.76M
    Subloop->addBlockEntry(Block);
536
11.1M
}
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.18M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
9.18M
  // Postorder traversal of the dominator tree.
555
9.18M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
52.6M
  for (auto DomNode : post_order(DomRoot)) {
557
52.6M
558
52.6M
    BlockT *Header = DomNode->getBlock();
559
52.6M
    SmallVector<BlockT *, 4> Backedges;
560
52.6M
561
52.6M
    // Check each predecessor of the potential loop header.
562
67.8M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
67.8M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
67.8M
      if (DomTree.dominates(Header, Backedge) &&
565
67.8M
          
DomTree.isReachableFromEntry(Backedge)4.14M
) {
566
4.14M
        Backedges.push_back(Backedge);
567
4.14M
      }
568
67.8M
    }
569
52.6M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
52.6M
    if (!Backedges.empty()) {
571
4.10M
      LoopT *L = AllocateLoop(Header);
572
4.10M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
4.10M
    }
574
52.6M
  }
575
9.18M
  // Perform a single forward CFG traversal to populate block and subloop
576
9.18M
  // vectors for all loops.
577
9.18M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
9.18M
  DFS.traverse(DomRoot->getBlock());
579
9.18M
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
553
6.99M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
6.99M
  // Postorder traversal of the dominator tree.
555
6.99M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
41.4M
  for (auto DomNode : post_order(DomRoot)) {
557
41.4M
558
41.4M
    BlockT *Header = DomNode->getBlock();
559
41.4M
    SmallVector<BlockT *, 4> Backedges;
560
41.4M
561
41.4M
    // Check each predecessor of the potential loop header.
562
54.2M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
54.2M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
54.2M
      if (DomTree.dominates(Header, Backedge) &&
565
54.2M
          
DomTree.isReachableFromEntry(Backedge)3.27M
) {
566
3.27M
        Backedges.push_back(Backedge);
567
3.27M
      }
568
54.2M
    }
569
41.4M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
41.4M
    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.4M
  }
575
6.99M
  // Perform a single forward CFG traversal to populate block and subloop
576
6.99M
  // vectors for all loops.
577
6.99M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
6.99M
  DFS.traverse(DomRoot->getBlock());
579
6.99M
}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
553
2.19M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
554
2.19M
  // Postorder traversal of the dominator tree.
555
2.19M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
556
11.1M
  for (auto DomNode : post_order(DomRoot)) {
557
11.1M
558
11.1M
    BlockT *Header = DomNode->getBlock();
559
11.1M
    SmallVector<BlockT *, 4> Backedges;
560
11.1M
561
11.1M
    // Check each predecessor of the potential loop header.
562
13.6M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
563
13.6M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
564
13.6M
      if (DomTree.dominates(Header, Backedge) &&
565
13.6M
          
DomTree.isReachableFromEntry(Backedge)877k
) {
566
877k
        Backedges.push_back(Backedge);
567
877k
      }
568
13.6M
    }
569
11.1M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
570
11.1M
    if (!Backedges.empty()) {
571
851k
      LoopT *L = AllocateLoop(Header);
572
851k
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
573
851k
    }
574
11.1M
  }
575
2.19M
  // Perform a single forward CFG traversal to populate block and subloop
576
2.19M
  // vectors for all loops.
577
2.19M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
578
2.19M
  DFS.traverse(DomRoot->getBlock());
579
2.19M
}
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
278k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
583
278k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
584
278k
  // The outer-most loop actually goes into the result in the same relative
585
278k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
586
278k
  // program order so for here we reverse it to get forward program order.
587
278k
  // FIXME: If we change the order of LoopInfo we will want to remove the
588
278k
  // reverse here.
589
278k
  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
278k
602
278k
  return PreOrderLoops;
603
278k
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder()
Line
Count
Source
582
278k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
583
278k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
584
278k
  // The outer-most loop actually goes into the result in the same relative
585
278k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
586
278k
  // program order so for here we reverse it to get forward program order.
587
278k
  // FIXME: If we change the order of LoopInfo we will want to remove the
588
278k
  // reverse here.
589
278k
  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
278k
602
278k
  return PreOrderLoops;
603
278k
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder()
604
605
template <class BlockT, class LoopT>
606
SmallVector<LoopT *, 4>
607
724
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
608
724
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
609
724
  // The outer-most loop actually goes into the result in the same relative
610
724
  // order as we walk it. LoopInfo stores the top level loops in reverse
611
724
  // program order so we walk in order here.
612
724
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
613
724
  // here.
614
1.02k
  for (LoopT *RootL : *this) {
615
1.02k
    assert(PreOrderWorklist.empty() &&
616
1.02k
           "Must start with an empty preorder walk worklist.");
617
1.02k
    PreOrderWorklist.push_back(RootL);
618
1.58k
    do {
619
1.58k
      LoopT *L = PreOrderWorklist.pop_back_val();
620
1.58k
      // Sub-loops are stored in forward program order, but will process the
621
1.58k
      // worklist backwards so we can just append them in order.
622
1.58k
      PreOrderWorklist.append(L->begin(), L->end());
623
1.58k
      PreOrderLoops.push_back(L);
624
1.58k
    } while (!PreOrderWorklist.empty());
625
1.02k
  }
626
724
627
724
  return PreOrderLoops;
628
724
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder()
Line
Count
Source
607
724
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
608
724
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
609
724
  // The outer-most loop actually goes into the result in the same relative
610
724
  // order as we walk it. LoopInfo stores the top level loops in reverse
611
724
  // program order so we walk in order here.
612
724
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
613
724
  // here.
614
1.02k
  for (LoopT *RootL : *this) {
615
1.02k
    assert(PreOrderWorklist.empty() &&
616
1.02k
           "Must start with an empty preorder walk worklist.");
617
1.02k
    PreOrderWorklist.push_back(RootL);
618
1.58k
    do {
619
1.58k
      LoopT *L = PreOrderWorklist.pop_back_val();
620
1.58k
      // Sub-loops are stored in forward program order, but will process the
621
1.58k
      // worklist backwards so we can just append them in order.
622
1.58k
      PreOrderWorklist.append(L->begin(), L->end());
623
1.58k
      PreOrderLoops.push_back(L);
624
1.58k
    } while (!PreOrderWorklist.empty());
625
1.02k
  }
626
724
627
724
  return PreOrderLoops;
628
724
}
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