Coverage Report

Created: 2018-12-14 11:24

/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.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
28.2M
    for (const auto &Succ : children<BlockT *>(BB))
40
43.0M
      if (!contains(Succ)) {
41
9.32M
        // Not in current loop? It must be an exit block.
42
9.32M
        ExitingBlocks.push_back(BB);
43
9.32M
        break;
44
9.32M
      }
45
7.07M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
36
7.02M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
7.02M
  assert(!isInvalid() && "Loop not in a valid state!");
38
7.02M
  for (const auto BB : blocks())
39
26.2M
    for (const auto &Succ : children<BlockT *>(BB))
40
39.7M
      if (!contains(Succ)) {
41
9.15M
        // Not in current loop? It must be an exit block.
42
9.15M
        ExitingBlocks.push_back(BB);
43
9.15M
        break;
44
9.15M
      }
45
7.02M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
36
46.1k
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
46.1k
  assert(!isInvalid() && "Loop not in a valid state!");
38
46.1k
  for (const auto BB : blocks())
39
2.05M
    for (const auto &Succ : children<BlockT *>(BB))
40
3.33M
      if (!contains(Succ)) {
41
169k
        // Not in current loop? It must be an exit block.
42
169k
        ExitingBlocks.push_back(BB);
43
169k
        break;
44
169k
      }
45
46.1k
}
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.72M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
3.72M
  assert(!isInvalid() && "Loop not in a valid state!");
52
3.72M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
3.72M
  getExitingBlocks(ExitingBlocks);
54
3.72M
  if (ExitingBlocks.size() == 1)
55
3.16M
    return ExitingBlocks[0];
56
558k
  return nullptr;
57
558k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const
Line
Count
Source
50
3.72M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
3.72M
  assert(!isInvalid() && "Loop not in a valid state!");
52
3.72M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
3.72M
  getExitingBlocks(ExitingBlocks);
54
3.72M
  if (ExitingBlocks.size() == 1)
55
3.16M
    return ExitingBlocks[0];
56
558k
  return nullptr;
57
558k
}
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.74M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
8.74M
  assert(!isInvalid() && "Loop not in a valid state!");
66
8.74M
  for (const auto BB : blocks())
67
48.2M
    for (const auto &Succ : children<BlockT *>(BB))
68
80.9M
      if (!contains(Succ))
69
12.3M
        // Not in current loop? It must be an exit block.
70
12.3M
        ExitBlocks.push_back(Succ);
71
8.74M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
64
8.44M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
8.44M
  assert(!isInvalid() && "Loop not in a valid state!");
66
8.44M
  for (const auto BB : blocks())
67
46.8M
    for (const auto &Succ : children<BlockT *>(BB))
68
78.6M
      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.44M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
64
302k
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
302k
  assert(!isInvalid() && "Loop not in a valid state!");
66
302k
  for (const auto BB : blocks())
67
1.34M
    for (const auto &Succ : children<BlockT *>(BB))
68
2.29M
      if (!contains(Succ))
69
405k
        // Not in current loop? It must be an exit block.
70
405k
        ExitBlocks.push_back(Succ);
71
302k
}
72
73
/// getExitBlock - If getExitBlocks would return exactly one block,
74
/// return that block. Otherwise return null.
75
template <class BlockT, class LoopT>
76
254k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
254k
  assert(!isInvalid() && "Loop not in a valid state!");
78
254k
  SmallVector<BlockT *, 8> ExitBlocks;
79
254k
  getExitBlocks(ExitBlocks);
80
254k
  if (ExitBlocks.size() == 1)
81
200k
    return ExitBlocks[0];
82
53.8k
  return nullptr;
83
53.8k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlock() const
Line
Count
Source
76
254k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
254k
  assert(!isInvalid() && "Loop not in a valid state!");
78
254k
  SmallVector<BlockT *, 8> ExitBlocks;
79
254k
  getExitBlocks(ExitBlocks);
80
254k
  if (ExitBlocks.size() == 1)
81
200k
    return ExitBlocks[0];
82
53.8k
  return nullptr;
83
53.8k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const
84
85
template <class BlockT, class LoopT>
86
4.63M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
87
4.63M
  // Each predecessor of each exit block of a normal loop is contained
88
4.63M
  // within the loop.
89
4.63M
  SmallVector<BlockT *, 4> ExitBlocks;
90
4.63M
  getExitBlocks(ExitBlocks);
91
4.63M
  for (BlockT *EB : ExitBlocks)
92
6.34M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
93
12.9M
      if (!contains(Predecessor))
94
85
        return false;
95
4.63M
  // All the requirements are met.
96
4.63M
  
return true4.63M
;
97
4.63M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::hasDedicatedExits() const
Line
Count
Source
86
4.63M
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
87
4.63M
  // Each predecessor of each exit block of a normal loop is contained
88
4.63M
  // within the loop.
89
4.63M
  SmallVector<BlockT *, 4> ExitBlocks;
90
4.63M
  getExitBlocks(ExitBlocks);
91
4.63M
  for (BlockT *EB : ExitBlocks)
92
6.34M
    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
93
12.9M
      if (!contains(Predecessor))
94
85
        return false;
95
4.63M
  // All the requirements are met.
96
4.63M
  
return true4.63M
;
97
4.63M
}
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.36M
        continue;
115
1.98M
116
1.98M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
117
1.98M
118
1.98M
      // If current basic block is this exit block's first predecessor then only
119
1.98M
      // insert exit block in to the output ExitBlocks vector. This ensures that
120
1.98M
      // same exit block is not inserted twice into ExitBlocks vector.
121
1.98M
      if (Block != FirstPred)
122
112k
        continue;
123
1.87M
124
1.87M
      // If a terminator has more then two successors, for example SwitchInst,
125
1.87M
      // then it is possible that there are multiple edges from current block to
126
1.87M
      // one exit block.
127
1.87M
      if (std::distance(BlockTraits::child_begin(Block),
128
1.87M
                        BlockTraits::child_end(Block)) <= 2) {
129
1.84M
        ExitBlocks.push_back(Successor);
130
1.84M
        continue;
131
1.84M
      }
132
33.1k
133
33.1k
      // In case of multiple edges from current block to exit block, collect
134
33.1k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
135
33.1k
      // duplicate edges.
136
33.1k
      if (!is_contained(SwitchExitBlocks, Successor)) {
137
26.4k
        SwitchExitBlocks.push_back(Successor);
138
26.4k
        ExitBlocks.push_back(Successor);
139
26.4k
      }
140
33.1k
    }
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.36M
        continue;
115
1.98M
116
1.98M
      BlockT *FirstPred = *InvBlockTraits::child_begin(Successor);
117
1.98M
118
1.98M
      // If current basic block is this exit block's first predecessor then only
119
1.98M
      // insert exit block in to the output ExitBlocks vector. This ensures that
120
1.98M
      // same exit block is not inserted twice into ExitBlocks vector.
121
1.98M
      if (Block != FirstPred)
122
112k
        continue;
123
1.87M
124
1.87M
      // If a terminator has more then two successors, for example SwitchInst,
125
1.87M
      // then it is possible that there are multiple edges from current block to
126
1.87M
      // one exit block.
127
1.87M
      if (std::distance(BlockTraits::child_begin(Block),
128
1.87M
                        BlockTraits::child_end(Block)) <= 2) {
129
1.84M
        ExitBlocks.push_back(Successor);
130
1.84M
        continue;
131
1.84M
      }
132
33.1k
133
33.1k
      // In case of multiple edges from current block to exit block, collect
134
33.1k
      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
135
33.1k
      // duplicate edges.
136
33.1k
      if (!is_contained(SwitchExitBlocks, Successor)) {
137
26.4k
        SwitchExitBlocks.push_back(Successor);
138
26.4k
        ExitBlocks.push_back(Successor);
139
26.4k
      }
140
33.1k
    }
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
481k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
146
481k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
147
481k
  getUniqueExitBlocks(UniqueExitBlocks);
148
481k
  if (UniqueExitBlocks.size() == 1)
149
452k
    return UniqueExitBlocks[0];
150
29.2k
  return nullptr;
151
29.2k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getUniqueExitBlock() const
Line
Count
Source
145
481k
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
146
481k
  SmallVector<BlockT *, 8> UniqueExitBlocks;
147
481k
  getUniqueExitBlocks(UniqueExitBlocks);
148
481k
  if (UniqueExitBlocks.size() == 1)
149
452k
    return UniqueExitBlocks[0];
150
29.2k
  return nullptr;
151
29.2k
}
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.4M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
175
11.4M
  assert(!isInvalid() && "Loop not in a valid state!");
176
11.4M
  // Keep track of nodes outside the loop branching to the header...
177
11.4M
  BlockT *Out = getLoopPredecessor();
178
11.4M
  if (!Out)
179
20.5k
    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
465
    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
491k
    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.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.0k
    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
465
    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
473k
    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::MachineBasicBlock, llvm::MachineLoop>::getLoopPreheader() const
Line
Count
Source
174
304k
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
175
304k
  assert(!isInvalid() && "Loop not in a valid state!");
176
304k
  // Keep track of nodes outside the loop branching to the header...
177
304k
  BlockT *Out = getLoopPredecessor();
178
304k
  if (!Out)
179
1.47k
    return nullptr;
180
302k
181
302k
  // Make sure we are allowed to hoist instructions into the predecessor.
182
302k
  if (!Out->isLegalToHoistInto())
183
0
    return nullptr;
184
302k
185
302k
  // Make sure there is only one exit out of the preheader.
186
302k
  typedef GraphTraits<BlockT *> BlockTraits;
187
302k
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
188
302k
  ++SI;
189
302k
  if (SI != BlockTraits::child_end(Out))
190
18.2k
    return nullptr; // Multiple exits from the block, must not be a preheader.
191
284k
192
284k
  // The predecessor has exactly one successor, so it is a preheader.
193
284k
  return Out;
194
284k
}
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.7k
)
212
23.5k
        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.3k
)
212
19.1k
        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.4M
  return Out;
220
12.4M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const
Line
Count
Source
202
476k
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
203
476k
  assert(!isInvalid() && "Loop not in a valid state!");
204
476k
  // Keep track of nodes outside the loop branching to the header...
205
476k
  BlockT *Out = nullptr;
206
476k
207
476k
  // Loop over the predecessors of the header node...
208
476k
  BlockT *Header = getHeader();
209
982k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
210
982k
    if (!contains(Pred)) { // If the block is not in the loop...
211
480k
      if (Out && 
Out != Pred4.43k
)
212
4.43k
        return nullptr; // Multiple predecessors outside the loop
213
476k
      Out = Pred;
214
476k
    }
215
982k
  }
216
476k
217
476k
  // Make sure there is only one exit out of the preheader.
218
476k
  assert(Out && "Header of loop has no predecessors from outside loop?");
219
471k
  return Out;
220
476k
}
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.4M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
14.4M
  assert(!isInvalid() && "Loop not in a valid state!");
227
14.4M
  BlockT *Header = getHeader();
228
14.4M
  BlockT *Latch = nullptr;
229
28.9M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
28.9M
    if (contains(Pred)) {
231
14.4M
      if (Latch)
232
7.27k
        return nullptr;
233
14.4M
      Latch = Pred;
234
14.4M
    }
235
28.9M
  }
236
14.4M
237
14.4M
  
return Latch14.4M
;
238
14.4M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const
Line
Count
Source
225
14.4M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
14.4M
  assert(!isInvalid() && "Loop not in a valid state!");
227
14.4M
  BlockT *Header = getHeader();
228
14.4M
  BlockT *Latch = nullptr;
229
28.9M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
28.9M
    if (contains(Pred)) {
231
14.4M
      if (Latch)
232
7.26k
        return nullptr;
233
14.4M
      Latch = Pred;
234
14.4M
    }
235
28.9M
  }
236
14.4M
237
14.4M
  
return Latch14.4M
;
238
14.4M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatch() const
Line
Count
Source
225
3.01k
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
226
3.01k
  assert(!isInvalid() && "Loop not in a valid state!");
227
3.01k
  BlockT *Header = getHeader();
228
3.01k
  BlockT *Latch = nullptr;
229
6.05k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
230
6.05k
    if (contains(Pred)) {
231
3.01k
      if (Latch)
232
4
        return nullptr;
233
3.01k
      Latch = Pred;
234
3.01k
    }
235
6.05k
  }
236
3.01k
237
3.01k
  
return Latch3.00k
;
238
3.01k
}
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
815k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
815k
  assert(!isInvalid() && "Loop not in a valid state!");
254
815k
#ifndef NDEBUG
255
815k
  if (!Blocks.empty()) {
256
815k
    auto SameHeader = LIB[getHeader()];
257
815k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
815k
           "Incorrect LI specified for this loop!");
259
815k
  }
260
815k
#endif
261
815k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
815k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
815k
264
815k
  LoopT *L = static_cast<LoopT *>(this);
265
815k
266
815k
  // Add the loop mapping to the LoopInfo object...
267
815k
  LIB.BBMap[NewBB] = L;
268
815k
269
815k
  // Add the basic block to this loop and all parent loops...
270
2.04M
  while (L) {
271
1.23M
    L->addBlockEntry(NewBB);
272
1.23M
    L = L->getParentLoop();
273
1.23M
  }
274
815k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&)
Line
Count
Source
252
761k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
761k
  assert(!isInvalid() && "Loop not in a valid state!");
254
761k
#ifndef NDEBUG
255
761k
  if (!Blocks.empty()) {
256
761k
    auto SameHeader = LIB[getHeader()];
257
761k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
761k
           "Incorrect LI specified for this loop!");
259
761k
  }
260
761k
#endif
261
761k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
761k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
761k
264
761k
  LoopT *L = static_cast<LoopT *>(this);
265
761k
266
761k
  // Add the loop mapping to the LoopInfo object...
267
761k
  LIB.BBMap[NewBB] = L;
268
761k
269
761k
  // Add the basic block to this loop and all parent loops...
270
1.90M
  while (L) {
271
1.14M
    L->addBlockEntry(NewBB);
272
1.14M
    L = L->getParentLoop();
273
1.14M
  }
274
761k
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&)
Line
Count
Source
252
54.2k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
253
54.2k
  assert(!isInvalid() && "Loop not in a valid state!");
254
54.2k
#ifndef NDEBUG
255
54.2k
  if (!Blocks.empty()) {
256
54.2k
    auto SameHeader = LIB[getHeader()];
257
54.2k
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
258
54.2k
           "Incorrect LI specified for this loop!");
259
54.2k
  }
260
54.2k
#endif
261
54.2k
  assert(NewBB && "Cannot add a null basic block to the loop!");
262
54.2k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
263
54.2k
264
54.2k
  LoopT *L = static_cast<LoopT *>(this);
265
54.2k
266
54.2k
  // Add the loop mapping to the LoopInfo object...
267
54.2k
  LIB.BBMap[NewBB] = L;
268
54.2k
269
54.2k
  // Add the basic block to this loop and all parent loops...
270
139k
  while (L) {
271
85.3k
    L->addBlockEntry(NewBB);
272
85.3k
    L = L->getParentLoop();
273
85.3k
  }
274
54.2k
}
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
59
                                                   LoopT *NewChild) {
283
59
  assert(!isInvalid() && "Loop not in a valid state!");
284
59
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
285
59
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
286
59
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
287
59
  assert(I != SubLoops.end() && "OldChild not in loop!");
288
59
  *I = NewChild;
289
59
  OldChild->ParentLoop = nullptr;
290
59
  NewChild->ParentLoop = static_cast<LoopT *>(this);
291
59
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::replaceChildLoopWith(llvm::Loop*, llvm::Loop*)
Line
Count
Source
282
59
                                                   LoopT *NewChild) {
283
59
  assert(!isInvalid() && "Loop not in a valid state!");
284
59
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
285
59
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
286
59
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
287
59
  assert(I != SubLoops.end() && "OldChild not in loop!");
288
59
  *I = NewChild;
289
59
  OldChild->ParentLoop = nullptr;
290
59
  NewChild->ParentLoop = static_cast<LoopT *>(this);
291
59
}
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.88M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
296
2.88M
  assert(!isInvalid() && "Loop not in a valid state!");
297
2.88M
#ifndef NDEBUG
298
2.88M
  assert(!Blocks.empty() && "Loop header is missing");
299
2.88M
300
2.88M
  // Setup for using a depth-first iterator to visit every block in the loop.
301
2.88M
  SmallVector<BlockT *, 8> ExitBBs;
302
2.88M
  getExitBlocks(ExitBBs);
303
2.88M
  df_iterator_default_set<BlockT *> VisitSet;
304
2.88M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
305
2.88M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
306
2.88M
      BI = df_ext_begin(getHeader(), VisitSet),
307
2.88M
      BE = df_ext_end(getHeader(), VisitSet);
308
2.88M
309
2.88M
  // Keep track of the BBs visited.
310
2.88M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
311
2.88M
312
2.88M
  // Check the individual blocks.
313
2.88M
  for (; BI != BE; ++BI) {
314
2.88M
    BlockT *BB = *BI;
315
2.88M
316
2.88M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
317
2.88M
                       GraphTraits<BlockT *>::child_end(BB),
318
2.88M
                       [&](BlockT *B) { return contains(B); }) &&
319
2.88M
           "Loop block has no in-loop successors!");
320
2.88M
321
2.88M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
322
2.88M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
323
2.88M
                       [&](BlockT *B) { return contains(B); }) &&
324
2.88M
           "Loop block has no in-loop predecessors!");
325
2.88M
326
2.88M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
327
2.88M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
328
2.88M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
329
2.88M
                  [&](BlockT *B) {
330
2.88M
                    if (!contains(B))
331
2.88M
                      OutsideLoopPreds.push_back(B);
332
2.88M
                  });
333
2.88M
334
2.88M
    if (BB == getHeader()) {
335
2.88M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
336
2.88M
    } else if (!OutsideLoopPreds.empty()) {
337
2.88M
      // A non-header loop shouldn't be reachable from outside the loop,
338
2.88M
      // though it is permitted if the predecessor is not itself actually
339
2.88M
      // reachable.
340
2.88M
      BlockT *EntryBB = &BB->getParent()->front();
341
2.88M
      for (BlockT *CB : depth_first(EntryBB))
342
2.88M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
343
2.88M
          assert(CB != OutsideLoopPreds[i] &&
344
2.88M
                 "Loop has multiple entry points!");
345
2.88M
    }
346
2.88M
    assert(BB != &getHeader()->getParent()->front() &&
347
2.88M
           "Loop contains function entry block!");
348
2.88M
349
2.88M
    VisitedBBs.insert(BB);
350
2.88M
  }
351
2.88M
352
2.88M
  if (VisitedBBs.size() != getNumBlocks()) {
353
2.88M
    dbgs() << "The following blocks are unreachable in the loop: ";
354
2.88M
    for (auto BB : Blocks) {
355
2.88M
      if (!VisitedBBs.count(BB)) {
356
2.88M
        dbgs() << *BB << "\n";
357
2.88M
      }
358
2.88M
    }
359
2.88M
    assert(false && "Unreachable block in loop");
360
2.88M
  }
361
2.88M
362
2.88M
  // Check the subloops.
363
2.88M
  for (iterator I = begin(), E = end(); I != E; ++I)
364
2.88M
    // Each block in each subloop should be contained within this loop.
365
2.88M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
366
2.88M
         BI != BE; ++BI) {
367
2.88M
      assert(contains(*BI) &&
368
2.88M
             "Loop does not contain all the blocks of a subloop!");
369
2.88M
    }
370
2.88M
371
2.88M
  // Check the parent loop pointer.
372
2.88M
  if (ParentLoop) {
373
2.88M
    assert(is_contained(*ParentLoop, this) &&
374
2.88M
           "Loop is not a subloop of its parent!");
375
2.88M
  }
376
2.88M
#endif
377
2.88M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoop() const
Line
Count
Source
295
2.88M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
296
2.88M
  assert(!isInvalid() && "Loop not in a valid state!");
297
2.88M
#ifndef NDEBUG
298
2.88M
  assert(!Blocks.empty() && "Loop header is missing");
299
2.88M
300
2.88M
  // Setup for using a depth-first iterator to visit every block in the loop.
301
2.88M
  SmallVector<BlockT *, 8> ExitBBs;
302
2.88M
  getExitBlocks(ExitBBs);
303
2.88M
  df_iterator_default_set<BlockT *> VisitSet;
304
2.88M
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
305
2.88M
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
306
2.88M
      BI = df_ext_begin(getHeader(), VisitSet),
307
2.88M
      BE = df_ext_end(getHeader(), VisitSet);
308
2.88M
309
2.88M
  // Keep track of the BBs visited.
310
2.88M
  SmallPtrSet<BlockT *, 8> VisitedBBs;
311
2.88M
312
2.88M
  // Check the individual blocks.
313
2.88M
  for (; BI != BE; ++BI) {
314
2.88M
    BlockT *BB = *BI;
315
2.88M
316
2.88M
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
317
2.88M
                       GraphTraits<BlockT *>::child_end(BB),
318
2.88M
                       [&](BlockT *B) { return contains(B); }) &&
319
2.88M
           "Loop block has no in-loop successors!");
320
2.88M
321
2.88M
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
322
2.88M
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
323
2.88M
                       [&](BlockT *B) { return contains(B); }) &&
324
2.88M
           "Loop block has no in-loop predecessors!");
325
2.88M
326
2.88M
    SmallVector<BlockT *, 2> OutsideLoopPreds;
327
2.88M
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
328
2.88M
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
329
2.88M
                  [&](BlockT *B) {
330
2.88M
                    if (!contains(B))
331
2.88M
                      OutsideLoopPreds.push_back(B);
332
2.88M
                  });
333
2.88M
334
2.88M
    if (BB == getHeader()) {
335
2.88M
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
336
2.88M
    } else if (!OutsideLoopPreds.empty()) {
337
2.88M
      // A non-header loop shouldn't be reachable from outside the loop,
338
2.88M
      // though it is permitted if the predecessor is not itself actually
339
2.88M
      // reachable.
340
2.88M
      BlockT *EntryBB = &BB->getParent()->front();
341
2.88M
      for (BlockT *CB : depth_first(EntryBB))
342
2.88M
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
343
2.88M
          assert(CB != OutsideLoopPreds[i] &&
344
2.88M
                 "Loop has multiple entry points!");
345
2.88M
    }
346
2.88M
    assert(BB != &getHeader()->getParent()->front() &&
347
2.88M
           "Loop contains function entry block!");
348
2.88M
349
2.88M
    VisitedBBs.insert(BB);
350
2.88M
  }
351
2.88M
352
2.88M
  if (VisitedBBs.size() != getNumBlocks()) {
353
2.88M
    dbgs() << "The following blocks are unreachable in the loop: ";
354
2.88M
    for (auto BB : Blocks) {
355
2.88M
      if (!VisitedBBs.count(BB)) {
356
2.88M
        dbgs() << *BB << "\n";
357
2.88M
      }
358
2.88M
    }
359
2.88M
    assert(false && "Unreachable block in loop");
360
2.88M
  }
361
2.88M
362
2.88M
  // Check the subloops.
363
2.88M
  for (iterator I = begin(), E = end(); I != E; ++I)
364
2.88M
    // Each block in each subloop should be contained within this loop.
365
2.88M
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
366
2.88M
         BI != BE; ++BI) {
367
2.88M
      assert(contains(*BI) &&
368
2.88M
             "Loop does not contain all the blocks of a subloop!");
369
2.88M
    }
370
2.88M
371
2.88M
  // Check the parent loop pointer.
372
2.88M
  if (ParentLoop) {
373
2.88M
    assert(is_contained(*ParentLoop, this) &&
374
2.88M
           "Loop is not a subloop of its parent!");
375
2.88M
  }
376
2.88M
#endif
377
2.88M
}
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
284
    DenseSet<const LoopT *> *Loops) const {
383
284
  assert(!isInvalid() && "Loop not in a valid state!");
384
284
  Loops->insert(static_cast<const LoopT *>(this));
385
284
  // Verify this loop.
386
284
  verifyLoop();
387
284
  // Verify the subloops.
388
381
  for (iterator I = begin(), E = end(); I != E; 
++I97
)
389
97
    (*I)->verifyLoopNest(Loops);
390
284
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoopNest(llvm::DenseSet<llvm::Loop const*, llvm::DenseMapInfo<llvm::Loop const*> >*) const
Line
Count
Source
382
284
    DenseSet<const LoopT *> *Loops) const {
383
284
  assert(!isInvalid() && "Loop not in a valid state!");
384
284
  Loops->insert(static_cast<const LoopT *>(this));
385
284
  // Verify this loop.
386
284
  verifyLoop();
387
284
  // Verify the subloops.
388
381
  for (iterator I = begin(), E = end(); I != E; 
++I97
)
389
97
    (*I)->verifyLoopNest(Loops);
390
284
}
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
1.32k
                                    bool Verbose) const {
395
1.32k
  OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: ";
396
1.32k
397
1.32k
  BlockT *H = getHeader();
398
12.3k
  for (unsigned i = 0; i < getBlocks().size(); 
++i11.0k
) {
399
11.0k
    BlockT *BB = getBlocks()[i];
400
11.0k
    if (!Verbose) {
401
11.0k
      if (i)
402
9.72k
        OS << ",";
403
11.0k
      BB->printAsOperand(OS, false);
404
11.0k
    } else
405
0
      OS << "\n";
406
11.0k
407
11.0k
    if (BB == H)
408
1.32k
      OS << "<header>";
409
11.0k
    if (isLoopLatch(BB))
410
1.32k
      OS << "<latch>";
411
11.0k
    if (isLoopExiting(BB))
412
1.55k
      OS << "<exiting>";
413
11.0k
    if (Verbose)
414
0
      BB->print(OS);
415
11.0k
  }
416
1.32k
  OS << "\n";
417
1.32k
418
1.82k
  for (iterator I = begin(), E = end(); I != E; 
++I500
)
419
500
    (*I)->print(OS, Depth + 2);
420
1.32k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&, unsigned int, bool) const
Line
Count
Source
394
1.32k
                                    bool Verbose) const {
395
1.32k
  OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: ";
396
1.32k
397
1.32k
  BlockT *H = getHeader();
398
12.3k
  for (unsigned i = 0; i < getBlocks().size(); 
++i11.0k
) {
399
11.0k
    BlockT *BB = getBlocks()[i];
400
11.0k
    if (!Verbose) {
401
11.0k
      if (i)
402
9.72k
        OS << ",";
403
11.0k
      BB->printAsOperand(OS, false);
404
11.0k
    } else
405
0
      OS << "\n";
406
11.0k
407
11.0k
    if (BB == H)
408
1.32k
      OS << "<header>";
409
11.0k
    if (isLoopLatch(BB))
410
1.32k
      OS << "<latch>";
411
11.0k
    if (isLoopExiting(BB))
412
1.55k
      OS << "<exiting>";
413
11.0k
    if (Verbose)
414
0
      BB->print(OS);
415
11.0k
  }
416
1.32k
  OS << "\n";
417
1.32k
418
1.82k
  for (iterator I = begin(), E = end(); I != E; 
++I500
)
419
500
    (*I)->print(OS, Depth + 2);
420
1.32k
}
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.07M
                                  const DomTreeBase<BlockT> &DomTree) {
434
4.07M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
4.07M
436
4.07M
  unsigned NumBlocks = 0;
437
4.07M
  unsigned NumSubloops = 0;
438
4.07M
439
4.07M
  // Perform a backward CFG traversal using a worklist.
440
4.07M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
22.7M
  while (!ReverseCFGWorklist.empty()) {
442
18.6M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
18.6M
    ReverseCFGWorklist.pop_back();
444
18.6M
445
18.6M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
18.6M
    if (!Subloop) {
447
13.1M
      if (!DomTree.isReachableFromEntry(PredBB))
448
50
        continue;
449
13.1M
450
13.1M
      // This is an undiscovered block. Map it to the current loop.
451
13.1M
      LI->changeLoopFor(PredBB, L);
452
13.1M
      ++NumBlocks;
453
13.1M
      if (PredBB == L->getHeader())
454
4.07M
        continue;
455
9.07M
      // Push all block predecessors on the worklist.
456
9.07M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
9.07M
                                InvBlockTraits::child_begin(PredBB),
458
9.07M
                                InvBlockTraits::child_end(PredBB));
459
9.07M
    } else {
460
5.50M
      // This is a discovered block. Find its outermost discovered loop.
461
5.71M
      while (LoopT *Parent = Subloop->getParentLoop())
462
211k
        Subloop = Parent;
463
5.50M
464
5.50M
      // If it is already discovered to be a subloop of this loop, continue.
465
5.50M
      if (Subloop == L)
466
4.41M
        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.6M
  }
483
4.07M
  L->getSubLoopsVector().reserve(NumSubloops);
484
4.07M
  L->reserveBlocks(NumBlocks);
485
4.07M
}
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.23M
                                  const DomTreeBase<BlockT> &DomTree) {
434
3.23M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
3.23M
436
3.23M
  unsigned NumBlocks = 0;
437
3.23M
  unsigned NumSubloops = 0;
438
3.23M
439
3.23M
  // Perform a backward CFG traversal using a worklist.
440
3.23M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
18.0M
  while (!ReverseCFGWorklist.empty()) {
442
14.8M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
14.8M
    ReverseCFGWorklist.pop_back();
444
14.8M
445
14.8M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
14.8M
    if (!Subloop) {
447
10.4M
      if (!DomTree.isReachableFromEntry(PredBB))
448
50
        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.23M
        continue;
455
7.20M
      // Push all block predecessors on the worklist.
456
7.20M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
7.20M
                                InvBlockTraits::child_begin(PredBB),
458
7.20M
                                InvBlockTraits::child_end(PredBB));
459
7.20M
    } else {
460
4.39M
      // This is a discovered block. Find its outermost discovered loop.
461
4.55M
      while (LoopT *Parent = Subloop->getParentLoop())
462
160k
        Subloop = Parent;
463
4.39M
464
4.39M
      // If it is already discovered to be a subloop of this loop, continue.
465
4.39M
      if (Subloop == L)
466
3.53M
        continue;
467
864k
468
864k
      // Discover a subloop of this loop.
469
864k
      Subloop->setParentLoop(L);
470
864k
      ++NumSubloops;
471
864k
      NumBlocks += Subloop->getBlocksVector().capacity();
472
864k
      PredBB = Subloop->getHeader();
473
864k
      // Continue traversal along predecessors that are not loop-back edges from
474
864k
      // within this subloop tree itself. Note that a predecessor may directly
475
864k
      // reach another subloop that is not yet discovered to be a subloop of
476
864k
      // this loop, which we must traverse.
477
1.73M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
478
1.73M
        if (LI->getLoopFor(Pred) != Subloop)
479
871k
          ReverseCFGWorklist.push_back(Pred);
480
1.73M
      }
481
864k
    }
482
14.8M
  }
483
3.23M
  L->getSubLoopsVector().reserve(NumSubloops);
484
3.23M
  L->reserveBlocks(NumBlocks);
485
3.23M
}
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
845k
                                  const DomTreeBase<BlockT> &DomTree) {
434
845k
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
435
845k
436
845k
  unsigned NumBlocks = 0;
437
845k
  unsigned NumSubloops = 0;
438
845k
439
845k
  // Perform a backward CFG traversal using a worklist.
440
845k
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
441
4.66M
  while (!ReverseCFGWorklist.empty()) {
442
3.81M
    BlockT *PredBB = ReverseCFGWorklist.back();
443
3.81M
    ReverseCFGWorklist.pop_back();
444
3.81M
445
3.81M
    LoopT *Subloop = LI->getLoopFor(PredBB);
446
3.81M
    if (!Subloop) {
447
2.71M
      if (!DomTree.isReachableFromEntry(PredBB))
448
0
        continue;
449
2.71M
450
2.71M
      // This is an undiscovered block. Map it to the current loop.
451
2.71M
      LI->changeLoopFor(PredBB, L);
452
2.71M
      ++NumBlocks;
453
2.71M
      if (PredBB == L->getHeader())
454
845k
        continue;
455
1.86M
      // Push all block predecessors on the worklist.
456
1.86M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
457
1.86M
                                InvBlockTraits::child_begin(PredBB),
458
1.86M
                                InvBlockTraits::child_end(PredBB));
459
1.86M
    } else {
460
1.10M
      // This is a discovered block. Find its outermost discovered loop.
461
1.15M
      while (LoopT *Parent = Subloop->getParentLoop())
462
50.8k
        Subloop = Parent;
463
1.10M
464
1.10M
      // If it is already discovered to be a subloop of this loop, continue.
465
1.10M
      if (Subloop == L)
466
882k
        continue;
467
220k
468
220k
      // Discover a subloop of this loop.
469
220k
      Subloop->setParentLoop(L);
470
220k
      ++NumSubloops;
471
220k
      NumBlocks += Subloop->getBlocksVector().capacity();
472
220k
      PredBB = Subloop->getHeader();
473
220k
      // Continue traversal along predecessors that are not loop-back edges from
474
220k
      // within this subloop tree itself. Note that a predecessor may directly
475
220k
      // reach another subloop that is not yet discovered to be a subloop of
476
220k
      // this loop, which we must traverse.
477
444k
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
478
444k
        if (LI->getLoopFor(Pred) != Subloop)
479
222k
          ReverseCFGWorklist.push_back(Pred);
480
444k
      }
481
220k
    }
482
3.81M
  }
483
845k
  L->getSubLoopsVector().reserve(NumSubloops);
484
845k
  L->reserveBlocks(NumBlocks);
485
845k
}
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.17M
  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.94M
  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.22M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>*)
Line
Count
Source
495
18
  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.17M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
9.17M
  for (BlockT *BB : post_order(EntryBlock))
507
53.0M
    insertIntoLoop(BB);
508
9.17M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*)
Line
Count
Source
505
6.94M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
6.94M
  for (BlockT *BB : post_order(EntryBlock))
507
41.6M
    insertIntoLoop(BB);
508
6.94M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*)
Line
Count
Source
505
2.22M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
2.22M
  for (BlockT *BB : post_order(EntryBlock))
507
11.3M
    insertIntoLoop(BB);
508
2.22M
}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::traverse(llvm::VPBlockBase*)
Line
Count
Source
505
18
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
506
18
  for (BlockT *BB : post_order(EntryBlock))
507
68
    insertIntoLoop(BB);
508
18
}
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.0M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
53.0M
  LoopT *Subloop = LI->getLoopFor(Block);
516
53.0M
  if (Subloop && 
Block == Subloop->getHeader()13.1M
) {
517
4.07M
    // We reach this point once per subloop after processing all the blocks in
518
4.07M
    // the subloop.
519
4.07M
    if (Subloop->getParentLoop())
520
1.08M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
2.99M
    else
522
2.99M
      LI->addTopLevelLoop(Subloop);
523
4.07M
524
4.07M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
4.07M
    // the lists, except for the loop header, which is always at the beginning.
526
4.07M
    Subloop->reverseBlock(1);
527
4.07M
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
4.07M
                 Subloop->getSubLoopsVector().end());
529
4.07M
530
4.07M
    Subloop = Subloop->getParentLoop();
531
4.07M
  }
532
66.4M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()13.3M
)
533
13.3M
    Subloop->addBlockEntry(Block);
534
53.0M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*)
Line
Count
Source
514
41.6M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
41.6M
  LoopT *Subloop = LI->getLoopFor(Block);
516
41.6M
  if (Subloop && 
Block == Subloop->getHeader()10.4M
) {
517
3.23M
    // We reach this point once per subloop after processing all the blocks in
518
3.23M
    // the subloop.
519
3.23M
    if (Subloop->getParentLoop())
520
864k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
2.36M
    else
522
2.36M
      LI->addTopLevelLoop(Subloop);
523
3.23M
524
3.23M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
3.23M
    // the lists, except for the loop header, which is always at the beginning.
526
3.23M
    Subloop->reverseBlock(1);
527
3.23M
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
3.23M
                 Subloop->getSubLoopsVector().end());
529
3.23M
530
3.23M
    Subloop = Subloop->getParentLoop();
531
3.23M
  }
532
52.2M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()10.5M
)
533
10.5M
    Subloop->addBlockEntry(Block);
534
41.6M
}
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.71M
) {
517
845k
    // We reach this point once per subloop after processing all the blocks in
518
845k
    // the subloop.
519
845k
    if (Subloop->getParentLoop())
520
220k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
625k
    else
522
625k
      LI->addTopLevelLoop(Subloop);
523
845k
524
845k
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
845k
    // the lists, except for the loop header, which is always at the beginning.
526
845k
    Subloop->reverseBlock(1);
527
845k
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
845k
                 Subloop->getSubLoopsVector().end());
529
845k
530
845k
    Subloop = Subloop->getParentLoop();
531
845k
  }
532
14.1M
  for (; Subloop; 
Subloop = Subloop->getParentLoop()2.79M
)
533
2.79M
    Subloop->addBlockEntry(Block);
534
11.3M
}
llvm::PopulateLoopsDFS<llvm::VPBlockBase, llvm::VPLoop>::insertIntoLoop(llvm::VPBlockBase*)
Line
Count
Source
514
68
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
515
68
  LoopT *Subloop = LI->getLoopFor(Block);
516
68
  if (Subloop && 
Block == Subloop->getHeader()32
) {
517
20
    // We reach this point once per subloop after processing all the blocks in
518
20
    // the subloop.
519
20
    if (Subloop->getParentLoop())
520
2
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
521
18
    else
522
18
      LI->addTopLevelLoop(Subloop);
523
20
524
20
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
525
20
    // the lists, except for the loop header, which is always at the beginning.
526
20
    Subloop->reverseBlock(1);
527
20
    std::reverse(Subloop->getSubLoopsVector().begin(),
528
20
                 Subloop->getSubLoopsVector().end());
529
20
530
20
    Subloop = Subloop->getParentLoop();
531
20
  }
532
82
  for (; Subloop; 
Subloop = Subloop->getParentLoop()14
)
533
14
    Subloop->addBlockEntry(Block);
534
68
}
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.17M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
9.17M
  // Postorder traversal of the dominator tree.
553
9.17M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
53.0M
  for (auto DomNode : post_order(DomRoot)) {
555
53.0M
556
53.0M
    BlockT *Header = DomNode->getBlock();
557
53.0M
    SmallVector<BlockT *, 4> Backedges;
558
53.0M
559
53.0M
    // Check each predecessor of the potential loop header.
560
68.5M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
68.5M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
68.5M
      if (DomTree.dominates(Header, Backedge) &&
563
68.5M
          
DomTree.isReachableFromEntry(Backedge)4.12M
) {
564
4.12M
        Backedges.push_back(Backedge);
565
4.12M
      }
566
68.5M
    }
567
53.0M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
53.0M
    if (!Backedges.empty()) {
569
4.07M
      LoopT *L = AllocateLoop(Header);
570
4.07M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
4.07M
    }
572
53.0M
  }
573
9.17M
  // Perform a single forward CFG traversal to populate block and subloop
574
9.17M
  // vectors for all loops.
575
9.17M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
9.17M
  DFS.traverse(DomRoot->getBlock());
577
9.17M
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
551
6.94M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
6.94M
  // Postorder traversal of the dominator tree.
553
6.94M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
41.6M
  for (auto DomNode : post_order(DomRoot)) {
555
41.6M
556
41.6M
    BlockT *Header = DomNode->getBlock();
557
41.6M
    SmallVector<BlockT *, 4> Backedges;
558
41.6M
559
41.6M
    // Check each predecessor of the potential loop header.
560
54.6M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
54.6M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
54.6M
      if (DomTree.dominates(Header, Backedge) &&
563
54.6M
          
DomTree.isReachableFromEntry(Backedge)3.25M
) {
564
3.25M
        Backedges.push_back(Backedge);
565
3.25M
      }
566
54.6M
    }
567
41.6M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
41.6M
    if (!Backedges.empty()) {
569
3.23M
      LoopT *L = AllocateLoop(Header);
570
3.23M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
3.23M
    }
572
41.6M
  }
573
6.94M
  // Perform a single forward CFG traversal to populate block and subloop
574
6.94M
  // vectors for all loops.
575
6.94M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
6.94M
  DFS.traverse(DomRoot->getBlock());
577
6.94M
}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
551
2.22M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
2.22M
  // Postorder traversal of the dominator tree.
553
2.22M
  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
13.8M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
13.8M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
13.8M
      if (DomTree.dominates(Header, Backedge) &&
563
13.8M
          
DomTree.isReachableFromEntry(Backedge)877k
) {
564
877k
        Backedges.push_back(Backedge);
565
877k
      }
566
13.8M
    }
567
11.3M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
11.3M
    if (!Backedges.empty()) {
569
845k
      LoopT *L = AllocateLoop(Header);
570
845k
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
845k
    }
572
11.3M
  }
573
2.22M
  // Perform a single forward CFG traversal to populate block and subloop
574
2.22M
  // vectors for all loops.
575
2.22M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
2.22M
  DFS.traverse(DomRoot->getBlock());
577
2.22M
}
llvm::LoopInfoBase<llvm::VPBlockBase, llvm::VPLoop>::analyze(llvm::DominatorTreeBase<llvm::VPBlockBase, false> const&)
Line
Count
Source
551
18
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
552
18
  // Postorder traversal of the dominator tree.
553
18
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
554
68
  for (auto DomNode : post_order(DomRoot)) {
555
68
556
68
    BlockT *Header = DomNode->getBlock();
557
68
    SmallVector<BlockT *, 4> Backedges;
558
68
559
68
    // Check each predecessor of the potential loop header.
560
73
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
561
73
      // If Header dominates predBB, this is a new loop. Collect the backedges.
562
73
      if (DomTree.dominates(Header, Backedge) &&
563
73
          
DomTree.isReachableFromEntry(Backedge)20
) {
564
20
        Backedges.push_back(Backedge);
565
20
      }
566
73
    }
567
68
    // Perform a backward CFG traversal to discover and map blocks in this loop.
568
68
    if (!Backedges.empty()) {
569
20
      LoopT *L = AllocateLoop(Header);
570
20
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
571
20
    }
572
68
  }
573
18
  // Perform a single forward CFG traversal to populate block and subloop
574
18
  // vectors for all loops.
575
18
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
576
18
  DFS.traverse(DomRoot->getBlock());
577
18
}
578
579
template <class BlockT, class LoopT>
580
276k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
581
276k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
582
276k
  // The outer-most loop actually goes into the result in the same relative
583
276k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
584
276k
  // program order so for here we reverse it to get forward program order.
585
276k
  // FIXME: If we change the order of LoopInfo we will want to remove the
586
276k
  // reverse here.
587
276k
  for (LoopT *RootL : reverse(*this)) {
588
132k
    assert(PreOrderWorklist.empty() &&
589
132k
           "Must start with an empty preorder walk worklist.");
590
132k
    PreOrderWorklist.push_back(RootL);
591
182k
    do {
592
182k
      LoopT *L = PreOrderWorklist.pop_back_val();
593
182k
      // Sub-loops are stored in forward program order, but will process the
594
182k
      // worklist backwards so append them in reverse order.
595
182k
      PreOrderWorklist.append(L->rbegin(), L->rend());
596
182k
      PreOrderLoops.push_back(L);
597
182k
    } while (!PreOrderWorklist.empty());
598
132k
  }
599
276k
600
276k
  return PreOrderLoops;
601
276k
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder()
Line
Count
Source
580
276k
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
581
276k
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
582
276k
  // The outer-most loop actually goes into the result in the same relative
583
276k
  // order as we walk it. But LoopInfo stores the top level loops in reverse
584
276k
  // program order so for here we reverse it to get forward program order.
585
276k
  // FIXME: If we change the order of LoopInfo we will want to remove the
586
276k
  // reverse here.
587
276k
  for (LoopT *RootL : reverse(*this)) {
588
132k
    assert(PreOrderWorklist.empty() &&
589
132k
           "Must start with an empty preorder walk worklist.");
590
132k
    PreOrderWorklist.push_back(RootL);
591
182k
    do {
592
182k
      LoopT *L = PreOrderWorklist.pop_back_val();
593
182k
      // Sub-loops are stored in forward program order, but will process the
594
182k
      // worklist backwards so append them in reverse order.
595
182k
      PreOrderWorklist.append(L->rbegin(), L->rend());
596
182k
      PreOrderLoops.push_back(L);
597
182k
    } while (!PreOrderWorklist.empty());
598
132k
  }
599
276k
600
276k
  return PreOrderLoops;
601
276k
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder()
602
603
template <class BlockT, class LoopT>
604
SmallVector<LoopT *, 4>
605
616
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
606
616
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
607
616
  // The outer-most loop actually goes into the result in the same relative
608
616
  // order as we walk it. LoopInfo stores the top level loops in reverse
609
616
  // program order so we walk in order here.
610
616
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
611
616
  // here.
612
921
  for (LoopT *RootL : *this) {
613
921
    assert(PreOrderWorklist.empty() &&
614
921
           "Must start with an empty preorder walk worklist.");
615
921
    PreOrderWorklist.push_back(RootL);
616
1.47k
    do {
617
1.47k
      LoopT *L = PreOrderWorklist.pop_back_val();
618
1.47k
      // Sub-loops are stored in forward program order, but will process the
619
1.47k
      // worklist backwards so we can just append them in order.
620
1.47k
      PreOrderWorklist.append(L->begin(), L->end());
621
1.47k
      PreOrderLoops.push_back(L);
622
1.47k
    } while (!PreOrderWorklist.empty());
623
921
  }
624
616
625
616
  return PreOrderLoops;
626
616
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder()
Line
Count
Source
605
616
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
606
616
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
607
616
  // The outer-most loop actually goes into the result in the same relative
608
616
  // order as we walk it. LoopInfo stores the top level loops in reverse
609
616
  // program order so we walk in order here.
610
616
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
611
616
  // here.
612
921
  for (LoopT *RootL : *this) {
613
921
    assert(PreOrderWorklist.empty() &&
614
921
           "Must start with an empty preorder walk worklist.");
615
921
    PreOrderWorklist.push_back(RootL);
616
1.47k
    do {
617
1.47k
      LoopT *L = PreOrderWorklist.pop_back_val();
618
1.47k
      // Sub-loops are stored in forward program order, but will process the
619
1.47k
      // worklist backwards so we can just append them in order.
620
1.47k
      PreOrderWorklist.append(L->begin(), L->end());
621
1.47k
      PreOrderLoops.push_back(L);
622
1.47k
    } while (!PreOrderWorklist.empty());
623
921
  }
624
616
625
616
  return PreOrderLoops;
626
616
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInReverseSiblingPreorder()
627
628
// Debugging
629
template <class BlockT, class LoopT>
630
32
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
631
260
  for (unsigned i = 0; i < TopLevelLoops.size(); 
++i228
)
632
228
    TopLevelLoops[i]->print(OS);
633
32
#if 0
634
32
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
635
32
         E = BBMap.end(); I != E; ++I)
636
32
    OS << "BB '" << I->first->getName() << "' level = "
637
32
       << I->second->getLoopDepth() << "\n";
638
32
#endif
639
32
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&) const
Line
Count
Source
630
32
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
631
260
  for (unsigned i = 0; i < TopLevelLoops.size(); 
++i228
)
632
228
    TopLevelLoops[i]->print(OS);
633
32
#if 0
634
32
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
635
32
         E = BBMap.end(); I != E; ++I)
636
32
    OS << "BB '" << I->first->getName() << "' level = "
637
32
       << I->second->getLoopDepth() << "\n";
638
32
#endif
639
32
}
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);
644
  llvm::sort(BB2);
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
137
    const DomTreeBase<BlockT> &DomTree) const {
703
137
  DenseSet<const LoopT *> Loops;
704
324
  for (iterator I = begin(), E = end(); I != E; 
++I187
) {
705
187
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
706
187
    (*I)->verifyLoopNest(&Loops);
707
187
  }
708
137
709
137
// Verify that blocks are mapped to valid loops.
710
137
#ifndef NDEBUG
711
137
  for (auto &Entry : BBMap) {
712
137
    const BlockT *BB = Entry.first;
713
137
    LoopT *L = Entry.second;
714
137
    assert(Loops.count(L) && "orphaned loop");
715
137
    assert(L->contains(BB) && "orphaned block");
716
137
    for (LoopT *ChildLoop : *L)
717
137
      assert(!ChildLoop->contains(BB) &&
718
137
             "BBMap should point to the innermost loop containing BB");
719
137
  }
720
137
721
137
  // Recompute LoopInfo to verify loops structure.
722
137
  LoopInfoBase<BlockT, LoopT> OtherLI;
723
137
  OtherLI.analyze(DomTree);
724
137
725
137
  // Build a map we can use to move from our LI to the computed one. This
726
137
  // allows us to ignore the particular order in any layer of the loop forest
727
137
  // while still comparing the structure.
728
137
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
729
137
  for (LoopT *L : OtherLI)
730
137
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
731
137
732
137
  // Walk the top level loops and ensure there is a corresponding top-level
733
137
  // loop in the computed version and then recursively compare those loop
734
137
  // nests.
735
137
  for (LoopT *L : *this) {
736
137
    BlockT *Header = L->getHeader();
737
137
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
738
137
    assert(OtherL && "Top level loop is missing in computed loop info!");
739
137
    // Now that we've matched this loop, erase its header from the map.
740
137
    OtherLoopHeaders.erase(Header);
741
137
    // And recursively compare these loops.
742
137
    compareLoops(L, OtherL, OtherLoopHeaders);
743
137
  }
744
137
745
137
  // Any remaining entries in the map are loops which were found when computing
746
137
  // a fresh LoopInfo but not present in the current one.
747
137
  if (!OtherLoopHeaders.empty()) {
748
137
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
749
137
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
750
137
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
751
137
  }
752
137
#endif
753
137
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) const
Line
Count
Source
702
137
    const DomTreeBase<BlockT> &DomTree) const {
703
137
  DenseSet<const LoopT *> Loops;
704
324
  for (iterator I = begin(), E = end(); I != E; 
++I187
) {
705
187
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
706
187
    (*I)->verifyLoopNest(&Loops);
707
187
  }
708
137
709
137
// Verify that blocks are mapped to valid loops.
710
137
#ifndef NDEBUG
711
137
  for (auto &Entry : BBMap) {
712
137
    const BlockT *BB = Entry.first;
713
137
    LoopT *L = Entry.second;
714
137
    assert(Loops.count(L) && "orphaned loop");
715
137
    assert(L->contains(BB) && "orphaned block");
716
137
    for (LoopT *ChildLoop : *L)
717
137
      assert(!ChildLoop->contains(BB) &&
718
137
             "BBMap should point to the innermost loop containing BB");
719
137
  }
720
137
721
137
  // Recompute LoopInfo to verify loops structure.
722
137
  LoopInfoBase<BlockT, LoopT> OtherLI;
723
137
  OtherLI.analyze(DomTree);
724
137
725
137
  // Build a map we can use to move from our LI to the computed one. This
726
137
  // allows us to ignore the particular order in any layer of the loop forest
727
137
  // while still comparing the structure.
728
137
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
729
137
  for (LoopT *L : OtherLI)
730
137
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
731
137
732
137
  // Walk the top level loops and ensure there is a corresponding top-level
733
137
  // loop in the computed version and then recursively compare those loop
734
137
  // nests.
735
137
  for (LoopT *L : *this) {
736
137
    BlockT *Header = L->getHeader();
737
137
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
738
137
    assert(OtherL && "Top level loop is missing in computed loop info!");
739
137
    // Now that we've matched this loop, erase its header from the map.
740
137
    OtherLoopHeaders.erase(Header);
741
137
    // And recursively compare these loops.
742
137
    compareLoops(L, OtherL, OtherLoopHeaders);
743
137
  }
744
137
745
137
  // Any remaining entries in the map are loops which were found when computing
746
137
  // a fresh LoopInfo but not present in the current one.
747
137
  if (!OtherLoopHeaders.empty()) {
748
137
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
749
137
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
750
137
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
751
137
  }
752
137
#endif
753
137
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) const
754
755
} // End llvm namespace
756
757
#endif