Coverage Report

Created: 2018-09-23 03:40

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