Coverage Report

Created: 2018-07-18 22:01

/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
6.95M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
6.95M
  assert(!isInvalid() && "Loop not in a valid state!");
38
6.95M
  for (const auto BB : blocks())
39
27.5M
    for (const auto &Succ : children<BlockT *>(BB))
40
41.9M
      if (!contains(Succ)) {
41
9.09M
        // Not in current loop? It must be an exit block.
42
9.09M
        ExitingBlocks.push_back(BB);
43
9.09M
        break;
44
9.09M
      }
45
6.95M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
36
6.91M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
6.91M
  assert(!isInvalid() && "Loop not in a valid state!");
38
6.91M
  for (const auto BB : blocks())
39
25.5M
    for (const auto &Succ : children<BlockT *>(BB))
40
38.6M
      if (!contains(Succ)) {
41
8.95M
        // Not in current loop? It must be an exit block.
42
8.95M
        ExitingBlocks.push_back(BB);
43
8.95M
        break;
44
8.95M
      }
45
6.91M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
36
46.3k
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
46.3k
  assert(!isInvalid() && "Loop not in a valid state!");
38
46.3k
  for (const auto BB : blocks())
39
2.02M
    for (const auto &Succ : children<BlockT *>(BB))
40
3.28M
      if (!contains(Succ)) {
41
142k
        // Not in current loop? It must be an exit block.
42
142k
        ExitingBlocks.push_back(BB);
43
142k
        break;
44
142k
      }
45
46.3k
}
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.64M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
3.64M
  assert(!isInvalid() && "Loop not in a valid state!");
52
3.64M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
3.64M
  getExitingBlocks(ExitingBlocks);
54
3.64M
  if (ExitingBlocks.size() == 1)
55
3.09M
    return ExitingBlocks[0];
56
554k
  return nullptr;
57
554k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const
Line
Count
Source
50
3.64M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
3.64M
  assert(!isInvalid() && "Loop not in a valid state!");
52
3.64M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
3.64M
  getExitingBlocks(ExitingBlocks);
54
3.64M
  if (ExitingBlocks.size() == 1)
55
3.09M
    return ExitingBlocks[0];
56
554k
  return nullptr;
57
554k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlock() const
Line
Count
Source
50
38
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
38
  assert(!isInvalid() && "Loop not in a valid state!");
52
38
  SmallVector<BlockT *, 8> ExitingBlocks;
53
38
  getExitingBlocks(ExitingBlocks);
54
38
  if (ExitingBlocks.size() == 1)
55
16
    return ExitingBlocks[0];
56
22
  return nullptr;
57
22
}
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.55M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
8.55M
  assert(!isInvalid() && "Loop not in a valid state!");
66
8.55M
  for (const auto BB : blocks())
67
45.4M
    for (const auto &Succ : children<BlockT *>(BB))
68
76.4M
      if (!contains(Succ))
69
11.9M
        // Not in current loop? It must be an exit block.
70
11.9M
        ExitBlocks.push_back(Succ);
71
8.55M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
64
8.25M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
8.25M
  assert(!isInvalid() && "Loop not in a valid state!");
66
8.25M
  for (const auto BB : blocks())
67
44.1M
    for (const auto &Succ : children<BlockT *>(BB))
68
74.2M
      if (!contains(Succ))
69
11.5M
        // Not in current loop? It must be an exit block.
70
11.5M
        ExitBlocks.push_back(Succ);
71
8.25M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
64
299k
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
299k
  assert(!isInvalid() && "Loop not in a valid state!");
66
299k
  for (const auto BB : blocks())
67
1.32M
    for (const auto &Succ : children<BlockT *>(BB))
68
2.25M
      if (!contains(Succ))
69
398k
        // Not in current loop? It must be an exit block.
70
398k
        ExitBlocks.push_back(Succ);
71
299k
}
72
73
/// getExitBlock - If getExitBlocks would return exactly one block,
74
/// return that block. Otherwise return null.
75
template <class BlockT, class LoopT>
76
249k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
249k
  assert(!isInvalid() && "Loop not in a valid state!");
78
249k
  SmallVector<BlockT *, 8> ExitBlocks;
79
249k
  getExitBlocks(ExitBlocks);
80
249k
  if (ExitBlocks.size() == 1)
81
195k
    return ExitBlocks[0];
82
53.6k
  return nullptr;
83
53.6k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlock() const
Line
Count
Source
76
249k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
249k
  assert(!isInvalid() && "Loop not in a valid state!");
78
249k
  SmallVector<BlockT *, 8> ExitBlocks;
79
249k
  getExitBlocks(ExitBlocks);
80
249k
  if (ExitBlocks.size() == 1)
81
195k
    return ExitBlocks[0];
82
53.6k
  return nullptr;
83
53.6k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const
84
85
template <class BlockT, class LoopT>
86
4.54M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
87
4.54M
  // Each predecessor of each exit block of a normal loop is contained
88
4.54M
  // within the loop.
89
4.54M
  SmallVector<BlockT *, 4> ExitBlocks;
90
4.54M
  getExitBlocks(ExitBlocks);
91
4.54M
  for (BlockT *EB : ExitBlocks)
92
6.18M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
93
12.3M
      if (!contains(Predecessor))
94
80
        return false;
95
4.54M
  // All the requirements are met.
96
4.54M
  
return true4.54M
;
97
4.54M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::hasDedicatedExits() const
Line
Count
Source
86
4.54M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
87
4.54M
  // Each predecessor of each exit block of a normal loop is contained
88
4.54M
  // within the loop.
89
4.54M
  SmallVector<BlockT *, 4> ExitBlocks;
90
4.54M
  getExitBlocks(ExitBlocks);
91
4.54M
  for (BlockT *EB : ExitBlocks)
92
6.18M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
93
12.3M
      if (!contains(Predecessor))
94
80
        return false;
95
4.54M
  // All the requirements are met.
96
4.54M
  
return true4.54M
;
97
4.54M
}
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.55M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
102
1.55M
  typedef GraphTraits<BlockT *> BlockTraits;
103
1.55M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
104
1.55M
105
1.55M
  assert(hasDedicatedExits() &&
106
1.55M
         "getUniqueExitBlocks assumes the loop has canonical form exits!");
107
1.55M
108
1.55M
  SmallVector<BlockT *, 32> SwitchExitBlocks;
109
5.89M
  for (BlockT *Block : this->blocks()) {
110
5.89M
    SwitchExitBlocks.clear();
111
10.0M
    for (BlockT *Successor : children<BlockT *>(Block)) {
112
10.0M
      // If block is inside the loop then it is not an exit block.
113
10.0M
      if (contains(Successor))
114
8.11M
        continue;
115
1.94M
116
1.94M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
117
1.94M
118
1.94M
      // If current basic block is this exit block's first predecessor then only
119
1.94M
      // insert exit block in to the output ExitBlocks vector. This ensures that
120
1.94M
      // same exit block is not inserted twice into ExitBlocks vector.
121
1.94M
      if (Block != FirstPred)
122
106k
        continue;
123
1.83M
124
1.83M
      // If a terminator has more then two successors, for example SwitchInst,
125
1.83M
      // then it is possible that there are multiple edges from current block to
126
1.83M
      // one exit block.
127
1.83M
      if (std::distance(BlockTraits::child_begin(Block),
128
1.83M
                        BlockTraits::child_end(Block)) <= 2) {
129
1.80M
        ExitBlocks.push_back(Successor);
130
1.80M
        continue;
131
1.80M
      }
132
33.8k
133
33.8k
      // In case of multiple edges from current block to exit block, collect
134
33.8k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
135
33.8k
      // duplicate edges.
136
33.8k
      if (!is_contained(SwitchExitBlocks, Successor)) {
137
27.0k
        SwitchExitBlocks.push_back(Successor);
138
27.0k
        ExitBlocks.push_back(Successor);
139
27.0k
      }
140
33.8k
    }
141
5.89M
  }
142
1.55M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getUniqueExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
101
1.55M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
102
1.55M
  typedef GraphTraits<BlockT *> BlockTraits;
103
1.55M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
104
1.55M
105
1.55M
  assert(hasDedicatedExits() &&
106
1.55M
         "getUniqueExitBlocks assumes the loop has canonical form exits!");
107
1.55M
108
1.55M
  SmallVector<BlockT *, 32> SwitchExitBlocks;
109
5.89M
  for (BlockT *Block : this->blocks()) {
110
5.89M
    SwitchExitBlocks.clear();
111
10.0M
    for (BlockT *Successor : children<BlockT *>(Block)) {
112
10.0M
      // If block is inside the loop then it is not an exit block.
113
10.0M
      if (contains(Successor))
114
8.11M
        continue;
115
1.94M
116
1.94M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
117
1.94M
118
1.94M
      // If current basic block is this exit block's first predecessor then only
119
1.94M
      // insert exit block in to the output ExitBlocks vector. This ensures that
120
1.94M
      // same exit block is not inserted twice into ExitBlocks vector.
121
1.94M
      if (Block != FirstPred)
122
106k
        continue;
123
1.83M
124
1.83M
      // If a terminator has more then two successors, for example SwitchInst,
125
1.83M
      // then it is possible that there are multiple edges from current block to
126
1.83M
      // one exit block.
127
1.83M
      if (std::distance(BlockTraits::child_begin(Block),
128
1.83M
                        BlockTraits::child_end(Block)) <= 2) {
129
1.80M
        ExitBlocks.push_back(Successor);
130
1.80M
        continue;
131
1.80M
      }
132
33.8k
133
33.8k
      // In case of multiple edges from current block to exit block, collect
134
33.8k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
135
33.8k
      // duplicate edges.
136
33.8k
      if (!is_contained(SwitchExitBlocks, Successor)) {
137
27.0k
        SwitchExitBlocks.push_back(Successor);
138
27.0k
        ExitBlocks.push_back(Successor);
139
27.0k
      }
140
33.8k
    }
141
5.89M
  }
142
1.55M
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getUniqueExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
143
144
template <class BlockT, class LoopT>
145
471k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
146
471k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
147
471k
  getUniqueExitBlocks(UniqueExitBlocks);
148
471k
  if (UniqueExitBlocks.size() == 1)
149
442k
    return UniqueExitBlocks[0];
150
29.1k
  return nullptr;
151
29.1k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getUniqueExitBlock() const
Line
Count
Source
145
471k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
146
471k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
147
471k
  getUniqueExitBlocks(UniqueExitBlocks);
148
471k
  if (UniqueExitBlocks.size() == 1)
149
442k
    return UniqueExitBlocks[0];
150
29.1k
  return nullptr;
151
29.1k
}
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.1M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
175
11.1M
  assert(!isInvalid() && "Loop not in a valid state!");
176
11.1M
  // Keep track of nodes outside the loop branching to the header...
177
11.1M
  BlockT *Out = getLoopPredecessor();
178
11.1M
  if (!Out)
179
19.8k
    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
397
    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
480k
    return nullptr; // Multiple exits from the block, must not be a preheader.
191
10.6M
192
10.6M
  // The predecessor has exactly one successor, so it is a preheader.
193
10.6M
  return Out;
194
10.6M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPreheader() const
Line
Count
Source
174
10.8M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
175
10.8M
  assert(!isInvalid() && "Loop not in a valid state!");
176
10.8M
  // Keep track of nodes outside the loop branching to the header...
177
10.8M
  BlockT *Out = getLoopPredecessor();
178
10.8M
  if (!Out)
179
18.4k
    return nullptr;
180
10.7M
181
10.7M
  // Make sure we are allowed to hoist instructions into the predecessor.
182
10.7M
  if (!Out->isLegalToHoistInto())
183
397
    return nullptr;
184
10.7M
185
10.7M
  // Make sure there is only one exit out of the preheader.
186
10.7M
  typedef GraphTraits<BlockT *> BlockTraits;
187
10.7M
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
188
10.7M
  ++SI;
189
10.7M
  if (SI != BlockTraits::child_end(Out))
190
462k
    return nullptr; // Multiple exits from the block, must not be a preheader.
191
10.3M
192
10.3M
  // The predecessor has exactly one successor, so it is a preheader.
193
10.3M
  return Out;
194
10.3M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPreheader() const
Line
Count
Source
174
300k
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
175
300k
  assert(!isInvalid() && "Loop not in a valid state!");
176
300k
  // Keep track of nodes outside the loop branching to the header...
177
300k
  BlockT *Out = getLoopPredecessor();
178
300k
  if (!Out)
179
1.44k
    return nullptr;
180
299k
181
299k
  // Make sure we are allowed to hoist instructions into the predecessor.
182
299k
  if (!Out->isLegalToHoistInto())
183
0
    return nullptr;
184
299k
185
299k
  // Make sure there is only one exit out of the preheader.
186
299k
  typedef GraphTraits<BlockT *> BlockTraits;
187
299k
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
188
299k
  ++SI;
189
299k
  if (SI != BlockTraits::child_end(Out))
190
17.9k
    return nullptr; // Multiple exits from the block, must not be a preheader.
191
281k
192
281k
  // The predecessor has exactly one successor, so it is a preheader.
193
281k
  return Out;
194
281k
}
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.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
203
12.5M
  assert(!isInvalid() && "Loop not in a valid state!");
204
12.5M
  // Keep track of nodes outside the loop branching to the header...
205
12.5M
  BlockT *Out = nullptr;
206
12.5M
207
12.5M
  // Loop over the predecessors of the header node...
208
12.5M
  BlockT *Header = getHeader();
209
24.9M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
210
24.9M
    if (!contains(Pred)) { // If the block is not in the loop...
211
12.5M
      if (Out && 
Out != Pred23.0k
)
212
22.8k
        return nullptr; // Multiple predecessors outside the loop
213
12.5M
      Out = Pred;
214
12.5M
    }
215
24.9M
  }
216
12.5M
217
12.5M
  // Make sure there is only one exit out of the preheader.
218
12.5M
  assert(Out && "Header of loop has no predecessors from outside loop?");
219
12.5M
  return Out;
220
12.5M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPredecessor() const
Line
Count
Source
202
12.0M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
203
12.0M
  assert(!isInvalid() && "Loop not in a valid state!");
204
12.0M
  // Keep track of nodes outside the loop branching to the header...
205
12.0M
  BlockT *Out = nullptr;
206
12.0M
207
12.0M
  // Loop over the predecessors of the header node...
208
12.0M
  BlockT *Header = getHeader();
209
24.0M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
210
24.0M
    if (!contains(Pred)) { // If the block is not in the loop...
211
12.0M
      if (Out && 
Out != Pred18.6k
)
212
18.5k
        return nullptr; // Multiple predecessors outside the loop
213
12.0M
      Out = Pred;
214
12.0M
    }
215
24.0M
  }
216
12.0M
217
12.0M
  // Make sure there is only one exit out of the preheader.
218
12.0M
  assert(Out && "Header of loop has no predecessors from outside loop?");
219
12.0M
  return Out;
220
12.0M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const
Line
Count
Source
202
470k
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
203
470k
  assert(!isInvalid() && "Loop not in a valid state!");
204
470k
  // Keep track of nodes outside the loop branching to the header...
205
470k
  BlockT *Out = nullptr;
206
470k
207
470k
  // Loop over the predecessors of the header node...
208
470k
  BlockT *Header = getHeader();
209
970k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
210
970k
    if (!contains(Pred)) { // If the block is not in the loop...
211
475k
      if (Out && 
Out != Pred4.35k
)
212
4.35k
        return nullptr; // Multiple predecessors outside the loop
213
470k
      Out = Pred;
214
470k
    }
215
970k
  }
216
470k
217
470k
  // Make sure there is only one exit out of the preheader.
218
470k
  assert(Out && "Header of loop has no predecessors from outside loop?");
219
466k
  return Out;
220
470k
}
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
17.0M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
17.0M
  assert(!isInvalid() && "Loop not in a valid state!");
227
17.0M
  BlockT *Header = getHeader();
228
17.0M
  BlockT *Latch = nullptr;
229
34.1M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
34.1M
    if (contains(Pred)) {
231
17.0M
      if (Latch)
232
7.39k
        return nullptr;
233
17.0M
      Latch = Pred;
234
17.0M
    }
235
34.1M
  }
236
17.0M
237
17.0M
  
return Latch17.0M
;
238
17.0M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const
Line
Count
Source
225
17.0M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
17.0M
  assert(!isInvalid() && "Loop not in a valid state!");
227
17.0M
  BlockT *Header = getHeader();
228
17.0M
  BlockT *Latch = nullptr;
229
34.1M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
34.1M
    if (contains(Pred)) {
231
17.0M
      if (Latch)
232
7.38k
        return nullptr;
233
17.0M
      Latch = Pred;
234
17.0M
    }
235
34.1M
  }
236
17.0M
237
17.0M
  
return Latch17.0M
;
238
17.0M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatch() const
Line
Count
Source
225
3.03k
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
3.03k
  assert(!isInvalid() && "Loop not in a valid state!");
227
3.03k
  BlockT *Header = getHeader();
228
3.03k
  BlockT *Latch = nullptr;
229
6.06k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
6.06k
    if (contains(Pred)) {
231
3.03k
      if (Latch)
232
5
        return nullptr;
233
3.03k
      Latch = Pred;
234
3.03k
    }
235
6.06k
  }
236
3.03k
237
3.03k
  
return Latch3.02k
;
238
3.03k
}
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
793k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
793k
  assert(!isInvalid() && "Loop not in a valid state!");
254
793k
#ifndef NDEBUG
255
793k
  if (!Blocks.empty()) {
256
793k
    auto SameHeader = LIB[getHeader()];
257
793k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
793k
           "Incorrect LI specified for this loop!");
259
793k
  }
260
793k
#endif
261
793k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
793k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
793k
264
793k
  LoopT *L = static_cast<LoopT *>(this);
265
793k
266
793k
  // Add the loop mapping to the LoopInfo object...
267
793k
  LIB.BBMap[NewBB] = L;
268
793k
269
793k
  // Add the basic block to this loop and all parent loops...
270
1.99M
  while (L) {
271
1.19M
    L->addBlockEntry(NewBB);
272
1.19M
    L = L->getParentLoop();
273
1.19M
  }
274
793k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&)
Line
Count
Source
252
740k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
740k
  assert(!isInvalid() && "Loop not in a valid state!");
254
740k
#ifndef NDEBUG
255
740k
  if (!Blocks.empty()) {
256
740k
    auto SameHeader = LIB[getHeader()];
257
740k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
740k
           "Incorrect LI specified for this loop!");
259
740k
  }
260
740k
#endif
261
740k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
740k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
740k
264
740k
  LoopT *L = static_cast<LoopT *>(this);
265
740k
266
740k
  // Add the loop mapping to the LoopInfo object...
267
740k
  LIB.BBMap[NewBB] = L;
268
740k
269
740k
  // Add the basic block to this loop and all parent loops...
270
1.85M
  while (L) {
271
1.11M
    L->addBlockEntry(NewBB);
272
1.11M
    L = L->getParentLoop();
273
1.11M
  }
274
740k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&)
Line
Count
Source
252
53.0k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
53.0k
  assert(!isInvalid() && "Loop not in a valid state!");
254
53.0k
#ifndef NDEBUG
255
53.0k
  if (!Blocks.empty()) {
256
53.0k
    auto SameHeader = LIB[getHeader()];
257
53.0k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
53.0k
           "Incorrect LI specified for this loop!");
259
53.0k
  }
260
53.0k
#endif
261
53.0k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
53.0k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
53.0k
264
53.0k
  LoopT *L = static_cast<LoopT *>(this);
265
53.0k
266
53.0k
  // Add the loop mapping to the LoopInfo object...
267
53.0k
  LIB.BBMap[NewBB] = L;
268
53.0k
269
53.0k
  // Add the basic block to this loop and all parent loops...
270
136k
  while (L) {
271
83.3k
    L->addBlockEntry(NewBB);
272
83.3k
    L = L->getParentLoop();
273
83.3k
  }
274
53.0k
}
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
57
                                                   LoopT *NewChild) {
283
57
  assert(!isInvalid() && "Loop not in a valid state!");
284
57
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
285
57
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
286
57
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
287
57
  assert(I != SubLoops.end() && "OldChild not in loop!");
288
57
  *I = NewChild;
289
57
  OldChild->ParentLoop = nullptr;
290
57
  NewChild->ParentLoop = static_cast<LoopT *>(this);
291
57
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::replaceChildLoopWith(llvm::Loop*, llvm::Loop*)
Line
Count
Source
282
57
                                                   LoopT *NewChild) {
283
57
  assert(!isInvalid() && "Loop not in a valid state!");
284
57
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
285
57
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
286
57
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
287
57
  assert(I != SubLoops.end() && "OldChild not in loop!");
288
57
  *I = NewChild;
289
57
  OldChild->ParentLoop = nullptr;
290
57
  NewChild->ParentLoop = static_cast<LoopT *>(this);
291
57
}
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.82M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
296
2.82M
  assert(!isInvalid() && "Loop not in a valid state!");
297
2.82M
#ifndef NDEBUG
298
2.82M
  assert(!Blocks.empty() && "Loop header is missing");
299
2.82M
300
2.82M
  // Setup for using a depth-first iterator to visit every block in the loop.
301
2.82M
  SmallVector<BlockT *, 8> ExitBBs;
302
2.82M
  getExitBlocks(ExitBBs);
303
2.82M
  df_iterator_default_set<BlockT *> VisitSet;
304
2.82M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
305
2.82M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
306
2.82M
      BI = df_ext_begin(getHeader(), VisitSet),
307
2.82M
      BE = df_ext_end(getHeader(), VisitSet);
308
2.82M
309
2.82M
  // Keep track of the BBs visited.
310
2.82M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
311
2.82M
312
2.82M
  // Check the individual blocks.
313
2.82M
  for (; BI != BE; ++BI) {
314
2.82M
    BlockT *BB = *BI;
315
2.82M
316
2.82M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
317
2.82M
                       GraphTraits<BlockT *>::child_end(BB),
318
2.82M
                       [&](BlockT *B) { return contains(B); }) &&
319
2.82M
           "Loop block has no in-loop successors!");
320
2.82M
321
2.82M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
322
2.82M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
323
2.82M
                       [&](BlockT *B) { return contains(B); }) &&
324
2.82M
           "Loop block has no in-loop predecessors!");
325
2.82M
326
2.82M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
327
2.82M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
328
2.82M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
329
2.82M
                  [&](BlockT *B) {
330
2.82M
                    if (!contains(B))
331
2.82M
                      OutsideLoopPreds.push_back(B);
332
2.82M
                  });
333
2.82M
334
2.82M
    if (BB == getHeader()) {
335
2.82M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
336
2.82M
    } else if (!OutsideLoopPreds.empty()) {
337
2.82M
      // A non-header loop shouldn't be reachable from outside the loop,
338
2.82M
      // though it is permitted if the predecessor is not itself actually
339
2.82M
      // reachable.
340
2.82M
      BlockT *EntryBB = &BB->getParent()->front();
341
2.82M
      for (BlockT *CB : depth_first(EntryBB))
342
2.82M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
343
2.82M
          assert(CB != OutsideLoopPreds[i] &&
344
2.82M
                 "Loop has multiple entry points!");
345
2.82M
    }
346
2.82M
    assert(BB != &getHeader()->getParent()->front() &&
347
2.82M
           "Loop contains function entry block!");
348
2.82M
349
2.82M
    VisitedBBs.insert(BB);
350
2.82M
  }
351
2.82M
352
2.82M
  if (VisitedBBs.size() != getNumBlocks()) {
353
2.82M
    dbgs() << "The following blocks are unreachable in the loop: ";
354
2.82M
    for (auto BB : Blocks) {
355
2.82M
      if (!VisitedBBs.count(BB)) {
356
2.82M
        dbgs() << *BB << "\n";
357
2.82M
      }
358
2.82M
    }
359
2.82M
    assert(false && "Unreachable block in loop");
360
2.82M
  }
361
2.82M
362
2.82M
  // Check the subloops.
363
2.82M
  for (iterator I = begin(), E = end(); I != E; ++I)
364
2.82M
    // Each block in each subloop should be contained within this loop.
365
2.82M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
366
2.82M
         BI != BE; ++BI) {
367
2.82M
      assert(contains(*BI) &&
368
2.82M
             "Loop does not contain all the blocks of a subloop!");
369
2.82M
    }
370
2.82M
371
2.82M
  // Check the parent loop pointer.
372
2.82M
  if (ParentLoop) {
373
2.82M
    assert(is_contained(*ParentLoop, this) &&
374
2.82M
           "Loop is not a subloop of its parent!");
375
2.82M
  }
376
2.82M
#endif
377
2.82M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoop() const
Line
Count
Source
295
2.82M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
296
2.82M
  assert(!isInvalid() && "Loop not in a valid state!");
297
2.82M
#ifndef NDEBUG
298
2.82M
  assert(!Blocks.empty() && "Loop header is missing");
299
2.82M
300
2.82M
  // Setup for using a depth-first iterator to visit every block in the loop.
301
2.82M
  SmallVector<BlockT *, 8> ExitBBs;
302
2.82M
  getExitBlocks(ExitBBs);
303
2.82M
  df_iterator_default_set<BlockT *> VisitSet;
304
2.82M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
305
2.82M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
306
2.82M
      BI = df_ext_begin(getHeader(), VisitSet),
307
2.82M
      BE = df_ext_end(getHeader(), VisitSet);
308
2.82M
309
2.82M
  // Keep track of the BBs visited.
310
2.82M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
311
2.82M
312
2.82M
  // Check the individual blocks.
313
2.82M
  for (; BI != BE; ++BI) {
314
2.82M
    BlockT *BB = *BI;
315
2.82M
316
2.82M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
317
2.82M
                       GraphTraits<BlockT *>::child_end(BB),
318
2.82M
                       [&](BlockT *B) { return contains(B); }) &&
319
2.82M
           "Loop block has no in-loop successors!");
320
2.82M
321
2.82M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
322
2.82M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
323
2.82M
                       [&](BlockT *B) { return contains(B); }) &&
324
2.82M
           "Loop block has no in-loop predecessors!");
325
2.82M
326
2.82M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
327
2.82M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
328
2.82M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
329
2.82M
                  [&](BlockT *B) {
330
2.82M
                    if (!contains(B))
331
2.82M
                      OutsideLoopPreds.push_back(B);
332
2.82M
                  });
333
2.82M
334
2.82M
    if (BB == getHeader()) {
335
2.82M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
336
2.82M
    } else if (!OutsideLoopPreds.empty()) {
337
2.82M
      // A non-header loop shouldn't be reachable from outside the loop,
338
2.82M
      // though it is permitted if the predecessor is not itself actually
339
2.82M
      // reachable.
340
2.82M
      BlockT *EntryBB = &BB->getParent()->front();
341
2.82M
      for (BlockT *CB : depth_first(EntryBB))
342
2.82M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
343
2.82M
          assert(CB != OutsideLoopPreds[i] &&
344
2.82M
                 "Loop has multiple entry points!");
345
2.82M
    }
346
2.82M
    assert(BB != &getHeader()->getParent()->front() &&
347
2.82M
           "Loop contains function entry block!");
348
2.82M
349
2.82M
    VisitedBBs.insert(BB);
350
2.82M
  }
351
2.82M
352
2.82M
  if (VisitedBBs.size() != getNumBlocks()) {
353
2.82M
    dbgs() << "The following blocks are unreachable in the loop: ";
354
2.82M
    for (auto BB : Blocks) {
355
2.82M
      if (!VisitedBBs.count(BB)) {
356
2.82M
        dbgs() << *BB << "\n";
357
2.82M
      }
358
2.82M
    }
359
2.82M
    assert(false && "Unreachable block in loop");
360
2.82M
  }
361
2.82M
362
2.82M
  // Check the subloops.
363
2.82M
  for (iterator I = begin(), E = end(); I != E; ++I)
364
2.82M
    // Each block in each subloop should be contained within this loop.
365
2.82M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
366
2.82M
         BI != BE; ++BI) {
367
2.82M
      assert(contains(*BI) &&
368
2.82M
             "Loop does not contain all the blocks of a subloop!");
369
2.82M
    }
370
2.82M
371
2.82M
  // Check the parent loop pointer.
372
2.82M
  if (ParentLoop) {
373
2.82M
    assert(is_contained(*ParentLoop, this) &&
374
2.82M
           "Loop is not a subloop of its parent!");
375
2.82M
  }
376
2.82M
#endif
377
2.82M
}
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.00M
                                  const DomTreeBase<BlockT> &DomTree) {
434
4.00M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
4.00M
436
4.00M
  unsigned NumBlocks = 0;
437
4.00M
  unsigned NumSubloops = 0;
438
4.00M
439
4.00M
  // Perform a backward CFG traversal using a worklist.
440
4.00M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
22.2M
  while (!ReverseCFGWorklist.empty()) {
442
18.2M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
18.2M
    ReverseCFGWorklist.pop_back();
444
18.2M
445
18.2M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
18.2M
    if (!Subloop) {
447
12.8M
      if (!DomTree.isReachableFromEntry(PredBB))
448
25
        continue;
449
12.8M
450
12.8M
      // This is an undiscovered block. Map it to the current loop.
451
12.8M
      LI->changeLoopFor(PredBB, L);
452
12.8M
      ++NumBlocks;
453
12.8M
      if (PredBB == L->getHeader())
454
4.00M
        continue;
455
8.87M
      // Push all block predecessors on the worklist.
456
8.87M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
8.87M
                                InvBlockTraits::child_begin(PredBB),
458
8.87M
                                InvBlockTraits::child_end(PredBB));
459
8.87M
    } else {
460
5.39M
      // This is a discovered block. Find its outermost discovered loop.
461
5.59M
      while (LoopT *Parent = Subloop->getParentLoop())
462
206k
        Subloop = Parent;
463
5.39M
464
5.39M
      // If it is already discovered to be a subloop of this loop, continue.
465
5.39M
      if (Subloop == L)
466
4.33M
        continue;
467
1.05M
468
1.05M
      // Discover a subloop of this loop.
469
1.05M
      Subloop->setParentLoop(L);
470
1.05M
      ++NumSubloops;
471
1.05M
      NumBlocks += Subloop->getBlocksVector().capacity();
472
1.05M
      PredBB = Subloop->getHeader();
473
1.05M
      // Continue traversal along predecessors that are not loop-back edges from
474
1.05M
      // within this subloop tree itself. Note that a predecessor may directly
475
1.05M
      // reach another subloop that is not yet discovered to be a subloop of
476
1.05M
      // this loop, which we must traverse.
477
2.12M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
478
2.12M
        if (LI->getLoopFor(Pred) != Subloop)
479
1.06M
          ReverseCFGWorklist.push_back(Pred);
480
2.12M
      }
481
1.05M
    }
482
18.2M
  }
483
4.00M
  L->getSubLoopsVector().reserve(NumSubloops);
484
4.00M
  L->reserveBlocks(NumBlocks);
485
4.00M
}
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.17M
                                  const DomTreeBase<BlockT> &DomTree) {
434
3.17M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
3.17M
436
3.17M
  unsigned NumBlocks = 0;
437
3.17M
  unsigned NumSubloops = 0;
438
3.17M
439
3.17M
  // Perform a backward CFG traversal using a worklist.
440
3.17M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
17.6M
  while (!ReverseCFGWorklist.empty()) {
442
14.5M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
14.5M
    ReverseCFGWorklist.pop_back();
444
14.5M
445
14.5M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
14.5M
    if (!Subloop) {
447
10.2M
      if (!DomTree.isReachableFromEntry(PredBB))
448
25
        continue;
449
10.2M
450
10.2M
      // This is an undiscovered block. Map it to the current loop.
451
10.2M
      LI->changeLoopFor(PredBB, L);
452
10.2M
      ++NumBlocks;
453
10.2M
      if (PredBB == L->getHeader())
454
3.17M
        continue;
455
7.04M
      // Push all block predecessors on the worklist.
456
7.04M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
7.04M
                                InvBlockTraits::child_begin(PredBB),
458
7.04M
                                InvBlockTraits::child_end(PredBB));
459
7.04M
    } else {
460
4.30M
      // This is a discovered block. Find its outermost discovered loop.
461
4.46M
      while (LoopT *Parent = Subloop->getParentLoop())
462
156k
        Subloop = Parent;
463
4.30M
464
4.30M
      // If it is already discovered to be a subloop of this loop, continue.
465
4.30M
      if (Subloop == L)
466
3.46M
        continue;
467
840k
468
840k
      // Discover a subloop of this loop.
469
840k
      Subloop->setParentLoop(L);
470
840k
      ++NumSubloops;
471
840k
      NumBlocks += Subloop->getBlocksVector().capacity();
472
840k
      PredBB = Subloop->getHeader();
473
840k
      // Continue traversal along predecessors that are not loop-back edges from
474
840k
      // within this subloop tree itself. Note that a predecessor may directly
475
840k
      // reach another subloop that is not yet discovered to be a subloop of
476
840k
      // this loop, which we must traverse.
477
1.68M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
478
1.68M
        if (LI->getLoopFor(Pred) != Subloop)
479
847k
          ReverseCFGWorklist.push_back(Pred);
480
1.68M
      }
481
840k
    }
482
14.5M
  }
483
3.17M
  L->getSubLoopsVector().reserve(NumSubloops);
484
3.17M
  L->reserveBlocks(NumBlocks);
485
3.17M
}
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
833k
                                  const DomTreeBase<BlockT> &DomTree) {
434
833k
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
833k
436
833k
  unsigned NumBlocks = 0;
437
833k
  unsigned NumSubloops = 0;
438
833k
439
833k
  // Perform a backward CFG traversal using a worklist.
440
833k
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
4.57M
  while (!ReverseCFGWorklist.empty()) {
442
3.74M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
3.74M
    ReverseCFGWorklist.pop_back();
444
3.74M
445
3.74M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
3.74M
    if (!Subloop) {
447
2.66M
      if (!DomTree.isReachableFromEntry(PredBB))
448
0
        continue;
449
2.66M
450
2.66M
      // This is an undiscovered block. Map it to the current loop.
451
2.66M
      LI->changeLoopFor(PredBB, L);
452
2.66M
      ++NumBlocks;
453
2.66M
      if (PredBB == L->getHeader())
454
833k
        continue;
455
1.82M
      // Push all block predecessors on the worklist.
456
1.82M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
1.82M
                                InvBlockTraits::child_begin(PredBB),
458
1.82M
                                InvBlockTraits::child_end(PredBB));
459
1.82M
    } else {
460
1.08M
      // This is a discovered block. Find its outermost discovered loop.
461
1.13M
      while (LoopT *Parent = Subloop->getParentLoop())
462
49.7k
        Subloop = Parent;
463
1.08M
464
1.08M
      // If it is already discovered to be a subloop of this loop, continue.
465
1.08M
      if (Subloop == L)
466
866k
        continue;
467
214k
468
214k
      // Discover a subloop of this loop.
469
214k
      Subloop->setParentLoop(L);
470
214k
      ++NumSubloops;
471
214k
      NumBlocks += Subloop->getBlocksVector().capacity();
472
214k
      PredBB = Subloop->getHeader();
473
214k
      // Continue traversal along predecessors that are not loop-back edges from
474
214k
      // within this subloop tree itself. Note that a predecessor may directly
475
214k
      // reach another subloop that is not yet discovered to be a subloop of
476
214k
      // this loop, which we must traverse.
477
433k
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
478
433k
        if (LI->getLoopFor(Pred) != Subloop)
479
216k
          ReverseCFGWorklist.push_back(Pred);
480
433k
      }
481
214k
    }
482
3.74M
  }
483
833k
  L->getSubLoopsVector().reserve(NumSubloops);
484
833k
  L->reserveBlocks(NumBlocks);
485
833k
}
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
8.78M
  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.67M
  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.11M
  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
8.78M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
8.78M
  for (BlockT *BB : post_order(EntryBlock))
507
51.8M
    insertIntoLoop(BB);
508
8.78M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*)
Line
Count
Source
505
6.67M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
6.67M
  for (BlockT *BB : post_order(EntryBlock))
507
40.7M
    insertIntoLoop(BB);
508
6.67M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*)
Line
Count
Source
505
2.11M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
2.11M
  for (BlockT *BB : post_order(EntryBlock))
507
11.1M
    insertIntoLoop(BB);
508
2.11M
}
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
51.8M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
51.8M
  LoopT *Subloop = LI->getLoopFor(Block);
516
51.8M
  if (Subloop && 
Block == Subloop->getHeader()12.8M
) {
517
4.00M
    // We reach this point once per subloop after processing all the blocks in
518
4.00M
    // the subloop.
519
4.00M
    if (Subloop->getParentLoop())
520
1.05M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
2.94M
    else
522
2.94M
      LI->addTopLevelLoop(Subloop);
523
4.00M
524
4.00M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
4.00M
    // the lists, except for the loop header, which is always at the beginning.
526
4.00M
    Subloop->reverseBlock(1);
527
4.00M
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
4.00M
                 Subloop->getSubLoopsVector().end());
529
4.00M
530
4.00M
    Subloop = Subloop->getParentLoop();
531
4.00M
  }
532
64.8M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()13.0M
)
533
13.0M
    Subloop->addBlockEntry(Block);
534
51.8M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*)
Line
Count
Source
514
40.7M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
40.7M
  LoopT *Subloop = LI->getLoopFor(Block);
516
40.7M
  if (Subloop && 
Block == Subloop->getHeader()10.2M
) {
517
3.17M
    // We reach this point once per subloop after processing all the blocks in
518
3.17M
    // the subloop.
519
3.17M
    if (Subloop->getParentLoop())
520
840k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
2.33M
    else
522
2.33M
      LI->addTopLevelLoop(Subloop);
523
3.17M
524
3.17M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
3.17M
    // the lists, except for the loop header, which is always at the beginning.
526
3.17M
    Subloop->reverseBlock(1);
527
3.17M
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
3.17M
                 Subloop->getSubLoopsVector().end());
529
3.17M
530
3.17M
    Subloop = Subloop->getParentLoop();
531
3.17M
  }
532
51.0M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()10.3M
)
533
10.3M
    Subloop->addBlockEntry(Block);
534
40.7M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::insertIntoLoop(llvm::MachineBasicBlock*)
Line
Count
Source
514
11.1M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
11.1M
  LoopT *Subloop = LI->getLoopFor(Block);
516
11.1M
  if (Subloop && 
Block == Subloop->getHeader()2.66M
) {
517
833k
    // We reach this point once per subloop after processing all the blocks in
518
833k
    // the subloop.
519
833k
    if (Subloop->getParentLoop())
520
214k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
618k
    else
522
618k
      LI->addTopLevelLoop(Subloop);
523
833k
524
833k
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
833k
    // the lists, except for the loop header, which is always at the beginning.
526
833k
    Subloop->reverseBlock(1);
527
833k
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
833k
                 Subloop->getSubLoopsVector().end());
529
833k
530
833k
    Subloop = Subloop->getParentLoop();
531
833k
  }
532
13.8M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()2.72M
)
533
2.72M
    Subloop->addBlockEntry(Block);
534
11.1M
}
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
8.78M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
8.78M
  // Postorder traversal of the dominator tree.
553
8.78M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
51.8M
  for (auto DomNode : post_order(DomRoot)) {
555
51.8M
556
51.8M
    BlockT *Header = DomNode->getBlock();
557
51.8M
    SmallVector<BlockT *, 4> Backedges;
558
51.8M
559
51.8M
    // Check each predecessor of the potential loop header.
560
67.2M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
67.2M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
67.2M
      if (DomTree.dominates(Header, Backedge) &&
563
67.2M
          
DomTree.isReachableFromEntry(Backedge)4.05M
) {
564
4.05M
        Backedges.push_back(Backedge);
565
4.05M
      }
566
67.2M
    }
567
51.8M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
51.8M
    if (!Backedges.empty()) {
569
4.00M
      LoopT *L = AllocateLoop(Header);
570
4.00M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
4.00M
    }
572
51.8M
  }
573
8.78M
  // Perform a single forward CFG traversal to populate block and subloop
574
8.78M
  // vectors for all loops.
575
8.78M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
8.78M
  DFS.traverse(DomRoot->getBlock());
577
8.78M
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
551
6.67M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
6.67M
  // Postorder traversal of the dominator tree.
553
6.67M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
40.7M
  for (auto DomNode : post_order(DomRoot)) {
555
40.7M
556
40.7M
    BlockT *Header = DomNode->getBlock();
557
40.7M
    SmallVector<BlockT *, 4> Backedges;
558
40.7M
559
40.7M
    // Check each predecessor of the potential loop header.
560
53.5M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
53.5M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
53.5M
      if (DomTree.dominates(Header, Backedge) &&
563
53.5M
          
DomTree.isReachableFromEntry(Backedge)3.19M
) {
564
3.19M
        Backedges.push_back(Backedge);
565
3.19M
      }
566
53.5M
    }
567
40.7M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
40.7M
    if (!Backedges.empty()) {
569
3.17M
      LoopT *L = AllocateLoop(Header);
570
3.17M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
3.17M
    }
572
40.7M
  }
573
6.67M
  // Perform a single forward CFG traversal to populate block and subloop
574
6.67M
  // vectors for all loops.
575
6.67M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
6.67M
  DFS.traverse(DomRoot->getBlock());
577
6.67M
}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
551
2.11M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
2.11M
  // Postorder traversal of the dominator tree.
553
2.11M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
11.1M
  for (auto DomNode : post_order(DomRoot)) {
555
11.1M
556
11.1M
    BlockT *Header = DomNode->getBlock();
557
11.1M
    SmallVector<BlockT *, 4> Backedges;
558
11.1M
559
11.1M
    // Check each predecessor of the potential loop header.
560
13.6M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
13.6M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
13.6M
      if (DomTree.dominates(Header, Backedge) &&
563
13.6M
          
DomTree.isReachableFromEntry(Backedge)865k
) {
564
865k
        Backedges.push_back(Backedge);
565
865k
      }
566
13.6M
    }
567
11.1M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
11.1M
    if (!Backedges.empty()) {
569
833k
      LoopT *L = AllocateLoop(Header);
570
833k
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
833k
    }
572
11.1M
  }
573
2.11M
  // Perform a single forward CFG traversal to populate block and subloop
574
2.11M
  // vectors for all loops.
575
2.11M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
2.11M
  DFS.traverse(DomRoot->getBlock());
577
2.11M
}
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
421
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
606
421
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
607
421
  // The outer-most loop actually goes into the result in the same relative
608
421
  // order as we walk it. LoopInfo stores the top level loops in reverse
609
421
  // program order so we walk in order here.
610
421
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
611
421
  // here.
612
519
  for (LoopT *RootL : *this) {
613
519
    assert(PreOrderWorklist.empty() &&
614
519
           "Must start with an empty preorder walk worklist.");
615
519
    PreOrderWorklist.push_back(RootL);
616
683
    do {
617
683
      LoopT *L = PreOrderWorklist.pop_back_val();
618
683
      // Sub-loops are stored in forward program order, but will process the
619
683
      // worklist backwards so we can just append them in order.
620
683
      PreOrderWorklist.append(L->begin(), L->end());
621
683
      PreOrderLoops.push_back(L);
622
683
    } while (!PreOrderWorklist.empty());
623
519
  }
624
421
625
421
  return PreOrderLoops;
626
421
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder()
Line
Count
Source
605
421
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
606
421
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
607
421
  // The outer-most loop actually goes into the result in the same relative
608
421
  // order as we walk it. LoopInfo stores the top level loops in reverse
609
421
  // program order so we walk in order here.
610
421
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
611
421
  // here.
612
519
  for (LoopT *RootL : *this) {
613
519
    assert(PreOrderWorklist.empty() &&
614
519
           "Must start with an empty preorder walk worklist.");
615
519
    PreOrderWorklist.push_back(RootL);
616
683
    do {
617
683
      LoopT *L = PreOrderWorklist.pop_back_val();
618
683
      // Sub-loops are stored in forward program order, but will process the
619
683
      // worklist backwards so we can just append them in order.
620
683
      PreOrderWorklist.append(L->begin(), L->end());
621
683
      PreOrderLoops.push_back(L);
622
683
    } while (!PreOrderWorklist.empty());
623
519
  }
624
421
625
421
  return PreOrderLoops;
626
421
}
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