Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
11.6M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
11.6M
  assert(!isInvalid() && "Loop not in a valid state!");
38
11.6M
  for (const auto BB : blocks())
39
44.2M
    for (const auto &Succ : children<BlockT *>(BB))
40
67.1M
      
if (67.1M
!contains(Succ)67.1M
) {
41
14.4M
        // Not in current loop? It must be an exit block.
42
14.4M
        ExitingBlocks.push_back(BB);
43
14.4M
        break;
44
14.4M
      }
45
11.6M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
36
86.6k
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
86.6k
  assert(!isInvalid() && "Loop not in a valid state!");
38
86.6k
  for (const auto BB : blocks())
39
3.79M
    for (const auto &Succ : children<BlockT *>(BB))
40
6.15M
      
if (6.15M
!contains(Succ)6.15M
) {
41
213k
        // Not in current loop? It must be an exit block.
42
213k
        ExitingBlocks.push_back(BB);
43
213k
        break;
44
213k
      }
45
86.6k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
36
11.5M
    SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37
11.5M
  assert(!isInvalid() && "Loop not in a valid state!");
38
11.5M
  for (const auto BB : blocks())
39
40.4M
    for (const auto &Succ : children<BlockT *>(BB))
40
61.0M
      
if (61.0M
!contains(Succ)61.0M
) {
41
14.1M
        // Not in current loop? It must be an exit block.
42
14.1M
        ExitingBlocks.push_back(BB);
43
14.1M
        break;
44
14.1M
      }
45
11.5M
}
46
47
/// getExitingBlock - If getExitingBlocks would return exactly one block,
48
/// return that block. Otherwise return null.
49
template <class BlockT, class LoopT>
50
6.08M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
6.08M
  assert(!isInvalid() && "Loop not in a valid state!");
52
6.08M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
6.08M
  getExitingBlocks(ExitingBlocks);
54
6.08M
  if (ExitingBlocks.size() == 1)
55
5.21M
    return ExitingBlocks[0];
56
861k
  return nullptr;
57
6.08M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitingBlock() const
Line
Count
Source
50
26
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
26
  assert(!isInvalid() && "Loop not in a valid state!");
52
26
  SmallVector<BlockT *, 8> ExitingBlocks;
53
26
  getExitingBlocks(ExitingBlocks);
54
26
  if (ExitingBlocks.size() == 1)
55
14
    return ExitingBlocks[0];
56
12
  return nullptr;
57
26
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitingBlock() const
Line
Count
Source
50
6.08M
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
51
6.08M
  assert(!isInvalid() && "Loop not in a valid state!");
52
6.08M
  SmallVector<BlockT *, 8> ExitingBlocks;
53
6.08M
  getExitingBlocks(ExitingBlocks);
54
6.08M
  if (ExitingBlocks.size() == 1)
55
5.21M
    return ExitingBlocks[0];
56
861k
  return nullptr;
57
6.08M
}
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
14.3M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
14.3M
  assert(!isInvalid() && "Loop not in a valid state!");
66
14.3M
  for (const auto BB : blocks())
67
77.7M
    for (const auto &Succ : children<BlockT *>(BB))
68
130M
      
if (130M
!contains(Succ)130M
)
69
130M
        // Not in current loop? It must be an exit block.
70
19.4M
        ExitBlocks.push_back(Succ);
71
14.3M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Line
Count
Source
64
13.8M
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
13.8M
  assert(!isInvalid() && "Loop not in a valid state!");
66
13.8M
  for (const auto BB : blocks())
67
75.4M
    for (const auto &Succ : children<BlockT *>(BB))
68
126M
      
if (126M
!contains(Succ)126M
)
69
126M
        // Not in current loop? It must be an exit block.
70
18.7M
        ExitBlocks.push_back(Succ);
71
13.8M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
Line
Count
Source
64
512k
    SmallVectorImpl<BlockT *> &ExitBlocks) const {
65
512k
  assert(!isInvalid() && "Loop not in a valid state!");
66
512k
  for (const auto BB : blocks())
67
2.29M
    for (const auto &Succ : children<BlockT *>(BB))
68
3.89M
      
if (3.89M
!contains(Succ)3.89M
)
69
3.89M
        // Not in current loop? It must be an exit block.
70
666k
        ExitBlocks.push_back(Succ);
71
512k
}
72
73
/// getExitBlock - If getExitBlocks would return exactly one block,
74
/// return that block. Otherwise return null.
75
template <class BlockT, class LoopT>
76
413k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
413k
  assert(!isInvalid() && "Loop not in a valid state!");
78
413k
  SmallVector<BlockT *, 8> ExitBlocks;
79
413k
  getExitBlocks(ExitBlocks);
80
413k
  if (ExitBlocks.size() == 1)
81
324k
    return ExitBlocks[0];
82
89.6k
  return nullptr;
83
413k
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitBlock() const
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitBlock() const
Line
Count
Source
76
413k
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77
413k
  assert(!isInvalid() && "Loop not in a valid state!");
78
413k
  SmallVector<BlockT *, 8> ExitBlocks;
79
413k
  getExitBlocks(ExitBlocks);
80
413k
  if (ExitBlocks.size() == 1)
81
324k
    return ExitBlocks[0];
82
89.6k
  return nullptr;
83
413k
}
84
85
/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
86
template <class BlockT, class LoopT>
87
void LoopBase<BlockT, LoopT>::getExitEdges(
88
0
    SmallVectorImpl<Edge> &ExitEdges) const {
89
0
  assert(!isInvalid() && "Loop not in a valid state!");
90
0
  for (const auto BB : blocks())
91
0
    for (const auto &Succ : children<BlockT *>(BB))
92
0
      
if (0
!contains(Succ)0
)
93
0
        // Not in current loop? It must be an exit block.
94
0
        ExitEdges.emplace_back(BB, Succ);
95
0
}
Unexecuted instantiation: llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::BasicBlock const*, llvm::BasicBlock const*> >&) const
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getExitEdges(llvm::SmallVectorImpl<std::__1::pair<llvm::MachineBasicBlock const*, llvm::MachineBasicBlock const*> >&) const
96
97
/// getLoopPreheader - If there is a preheader for this loop, return it.  A
98
/// loop has a preheader if there is only one edge to the header of the loop
99
/// from outside of the loop and it is legal to hoist instructions into the
100
/// predecessor. If this is the case, the block branching to the header of the
101
/// loop is the preheader node.
102
///
103
/// This method returns null if there is no preheader for the loop.
104
///
105
template <class BlockT, class LoopT>
106
18.5M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
107
18.5M
  assert(!isInvalid() && "Loop not in a valid state!");
108
18.5M
  // Keep track of nodes outside the loop branching to the header...
109
18.5M
  BlockT *Out = getLoopPredecessor();
110
18.5M
  if (!Out)
111
14.5k
    return nullptr;
112
18.5M
113
18.5M
  // Make sure we are allowed to hoist instructions into the predecessor.
114
18.5M
  
if (18.5M
!Out->isLegalToHoistInto()18.5M
)
115
33
    return nullptr;
116
18.5M
117
18.5M
  // Make sure there is only one exit out of the preheader.
118
18.5M
  typedef GraphTraits<BlockT *> BlockTraits;
119
18.5M
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
120
18.5M
  ++SI;
121
18.5M
  if (SI != BlockTraits::child_end(Out))
122
170k
    return nullptr; // Multiple exits from the block, must not be a preheader.
123
18.5M
124
18.5M
  // The predecessor has exactly one successor, so it is a preheader.
125
18.3M
  return Out;
126
18.5M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPreheader() const
Line
Count
Source
106
544k
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
107
544k
  assert(!isInvalid() && "Loop not in a valid state!");
108
544k
  // Keep track of nodes outside the loop branching to the header...
109
544k
  BlockT *Out = getLoopPredecessor();
110
544k
  if (!Out)
111
2.82k
    return nullptr;
112
544k
113
544k
  // Make sure we are allowed to hoist instructions into the predecessor.
114
541k
  
if (541k
!Out->isLegalToHoistInto()541k
)
115
0
    return nullptr;
116
541k
117
541k
  // Make sure there is only one exit out of the preheader.
118
541k
  typedef GraphTraits<BlockT *> BlockTraits;
119
541k
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
120
541k
  ++SI;
121
541k
  if (SI != BlockTraits::child_end(Out))
122
23.6k
    return nullptr; // Multiple exits from the block, must not be a preheader.
123
541k
124
541k
  // The predecessor has exactly one successor, so it is a preheader.
125
518k
  return Out;
126
544k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPreheader() const
Line
Count
Source
106
18.0M
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
107
18.0M
  assert(!isInvalid() && "Loop not in a valid state!");
108
18.0M
  // Keep track of nodes outside the loop branching to the header...
109
18.0M
  BlockT *Out = getLoopPredecessor();
110
18.0M
  if (!Out)
111
11.6k
    return nullptr;
112
18.0M
113
18.0M
  // Make sure we are allowed to hoist instructions into the predecessor.
114
18.0M
  
if (18.0M
!Out->isLegalToHoistInto()18.0M
)
115
33
    return nullptr;
116
18.0M
117
18.0M
  // Make sure there is only one exit out of the preheader.
118
18.0M
  typedef GraphTraits<BlockT *> BlockTraits;
119
18.0M
  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
120
18.0M
  ++SI;
121
18.0M
  if (SI != BlockTraits::child_end(Out))
122
147k
    return nullptr; // Multiple exits from the block, must not be a preheader.
123
18.0M
124
18.0M
  // The predecessor has exactly one successor, so it is a preheader.
125
17.8M
  return Out;
126
18.0M
}
127
128
/// getLoopPredecessor - If the given loop's header has exactly one unique
129
/// predecessor outside the loop, return it. Otherwise return null.
130
/// This is less strict that the loop "preheader" concept, which requires
131
/// the predecessor to have exactly one successor.
132
///
133
template <class BlockT, class LoopT>
134
20.9M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
135
20.9M
  assert(!isInvalid() && "Loop not in a valid state!");
136
20.9M
  // Keep track of nodes outside the loop branching to the header...
137
20.9M
  BlockT *Out = nullptr;
138
20.9M
139
20.9M
  // Loop over the predecessors of the header node...
140
20.9M
  BlockT *Header = getHeader();
141
41.7M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
142
41.7M
    if (
!contains(Pred)41.7M
) { // If the block is not in the loop...
143
20.9M
      if (
Out && 20.9M
Out != Pred23.0k
)
144
22.9k
        return nullptr; // Multiple predecessors outside the loop
145
20.9M
      Out = Pred;
146
20.9M
    }
147
41.7M
  }
148
20.9M
149
20.9M
  // Make sure there is only one exit out of the preheader.
150
20.9M
  assert(Out && "Header of loop has no predecessors from outside loop?");
151
20.9M
  return Out;
152
20.9M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopPredecessor() const
Line
Count
Source
134
20.1M
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
135
20.1M
  assert(!isInvalid() && "Loop not in a valid state!");
136
20.1M
  // Keep track of nodes outside the loop branching to the header...
137
20.1M
  BlockT *Out = nullptr;
138
20.1M
139
20.1M
  // Loop over the predecessors of the header node...
140
20.1M
  BlockT *Header = getHeader();
141
40.0M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
142
40.0M
    if (
!contains(Pred)40.0M
) { // If the block is not in the loop...
143
20.1M
      if (
Out && 20.1M
Out != Pred11.8k
)
144
11.6k
        return nullptr; // Multiple predecessors outside the loop
145
20.1M
      Out = Pred;
146
20.1M
    }
147
40.0M
  }
148
20.1M
149
20.1M
  // Make sure there is only one exit out of the preheader.
150
20.0M
  assert(Out && "Header of loop has no predecessors from outside loop?");
151
20.0M
  return Out;
152
20.1M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopPredecessor() const
Line
Count
Source
134
832k
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
135
832k
  assert(!isInvalid() && "Loop not in a valid state!");
136
832k
  // Keep track of nodes outside the loop branching to the header...
137
832k
  BlockT *Out = nullptr;
138
832k
139
832k
  // Loop over the predecessors of the header node...
140
832k
  BlockT *Header = getHeader();
141
1.71M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
142
1.71M
    if (
!contains(Pred)1.71M
) { // If the block is not in the loop...
143
844k
      if (
Out && 844k
Out != Pred11.2k
)
144
11.2k
        return nullptr; // Multiple predecessors outside the loop
145
832k
      Out = Pred;
146
832k
    }
147
1.71M
  }
148
832k
149
832k
  // Make sure there is only one exit out of the preheader.
150
821k
  assert(Out && "Header of loop has no predecessors from outside loop?");
151
821k
  return Out;
152
832k
}
153
154
/// getLoopLatch - If there is a single latch block for this loop, return it.
155
/// A latch block is a block that contains a branch back to the header.
156
template <class BlockT, class LoopT>
157
25.1M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
158
25.1M
  assert(!isInvalid() && "Loop not in a valid state!");
159
25.1M
  BlockT *Header = getHeader();
160
25.1M
  BlockT *Latch = nullptr;
161
50.2M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
162
50.2M
    if (
contains(Pred)50.2M
) {
163
25.1M
      if (Latch)
164
4.71k
        return nullptr;
165
25.1M
      Latch = Pred;
166
25.1M
    }
167
50.2M
  }
168
25.1M
169
25.1M
  return Latch;
170
25.1M
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const
Line
Count
Source
157
25.1M
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
158
25.1M
  assert(!isInvalid() && "Loop not in a valid state!");
159
25.1M
  BlockT *Header = getHeader();
160
25.1M
  BlockT *Latch = nullptr;
161
50.2M
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
162
50.2M
    if (
contains(Pred)50.2M
) {
163
25.1M
      if (Latch)
164
4.71k
        return nullptr;
165
25.1M
      Latch = Pred;
166
25.1M
    }
167
50.2M
  }
168
25.1M
169
25.1M
  return Latch;
170
25.1M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopLatch() const
Line
Count
Source
157
1.57k
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
158
1.57k
  assert(!isInvalid() && "Loop not in a valid state!");
159
1.57k
  BlockT *Header = getHeader();
160
1.57k
  BlockT *Latch = nullptr;
161
3.14k
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
162
3.14k
    if (
contains(Pred)3.14k
) {
163
1.57k
      if (Latch)
164
3
        return nullptr;
165
1.57k
      Latch = Pred;
166
1.57k
    }
167
3.14k
  }
168
1.57k
169
1.57k
  return Latch;
170
1.57k
}
171
172
//===----------------------------------------------------------------------===//
173
// APIs for updating loop information after changing the CFG
174
//
175
176
/// addBasicBlockToLoop - This method is used by other analyses to update loop
177
/// information.  NewBB is set to be a new member of the current loop.
178
/// Because of this, it is added as a member of all parent loops, and is added
179
/// to the specified LoopInfo object as being in the current basic block.  It
180
/// is not valid to replace the loop header with this method.
181
///
182
template <class BlockT, class LoopT>
183
void LoopBase<BlockT, LoopT>::addBasicBlockToLoop(
184
1.16M
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
185
1.16M
  assert(!isInvalid() && "Loop not in a valid state!");
186
#ifndef NDEBUG
187
  if (!Blocks.empty()) {
188
    auto SameHeader = LIB[getHeader()];
189
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
190
           "Incorrect LI specified for this loop!");
191
  }
192
#endif
193
  assert(NewBB && "Cannot add a null basic block to the loop!");
194
1.16M
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
195
1.16M
196
1.16M
  LoopT *L = static_cast<LoopT *>(this);
197
1.16M
198
1.16M
  // Add the loop mapping to the LoopInfo object...
199
1.16M
  LIB.BBMap[NewBB] = L;
200
1.16M
201
1.16M
  // Add the basic block to this loop and all parent loops...
202
2.99M
  while (
L2.99M
) {
203
1.82M
    L->addBlockEntry(NewBB);
204
1.82M
    L = L->getParentLoop();
205
1.82M
  }
206
1.16M
}
llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::addBasicBlockToLoop(llvm::MachineBasicBlock*, llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>&)
Line
Count
Source
184
96.5k
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
185
96.5k
  assert(!isInvalid() && "Loop not in a valid state!");
186
#ifndef NDEBUG
187
  if (!Blocks.empty()) {
188
    auto SameHeader = LIB[getHeader()];
189
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
190
           "Incorrect LI specified for this loop!");
191
  }
192
#endif
193
  assert(NewBB && "Cannot add a null basic block to the loop!");
194
96.5k
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
195
96.5k
196
96.5k
  LoopT *L = static_cast<LoopT *>(this);
197
96.5k
198
96.5k
  // Add the loop mapping to the LoopInfo object...
199
96.5k
  LIB.BBMap[NewBB] = L;
200
96.5k
201
96.5k
  // Add the basic block to this loop and all parent loops...
202
256k
  while (
L256k
) {
203
159k
    L->addBlockEntry(NewBB);
204
159k
    L = L->getParentLoop();
205
159k
  }
206
96.5k
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::addBasicBlockToLoop(llvm::BasicBlock*, llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>&)
Line
Count
Source
184
1.07M
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
185
1.07M
  assert(!isInvalid() && "Loop not in a valid state!");
186
#ifndef NDEBUG
187
  if (!Blocks.empty()) {
188
    auto SameHeader = LIB[getHeader()];
189
    assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
190
           "Incorrect LI specified for this loop!");
191
  }
192
#endif
193
  assert(NewBB && "Cannot add a null basic block to the loop!");
194
1.07M
  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
195
1.07M
196
1.07M
  LoopT *L = static_cast<LoopT *>(this);
197
1.07M
198
1.07M
  // Add the loop mapping to the LoopInfo object...
199
1.07M
  LIB.BBMap[NewBB] = L;
200
1.07M
201
1.07M
  // Add the basic block to this loop and all parent loops...
202
2.73M
  while (
L2.73M
) {
203
1.66M
    L->addBlockEntry(NewBB);
204
1.66M
    L = L->getParentLoop();
205
1.66M
  }
206
1.07M
}
207
208
/// replaceChildLoopWith - This is used when splitting loops up.  It replaces
209
/// the OldChild entry in our children list with NewChild, and updates the
210
/// parent pointer of OldChild to be null and the NewChild to be this loop.
211
/// This updates the loop depth of the new child.
212
template <class BlockT, class LoopT>
213
void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild,
214
122
                                                   LoopT *NewChild) {
215
122
  assert(!isInvalid() && "Loop not in a valid state!");
216
122
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
217
122
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
218
122
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
219
122
  assert(I != SubLoops.end() && "OldChild not in loop!");
220
122
  *I = NewChild;
221
122
  OldChild->ParentLoop = nullptr;
222
122
  NewChild->ParentLoop = static_cast<LoopT *>(this);
223
122
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::replaceChildLoopWith(llvm::MachineLoop*, llvm::MachineLoop*)
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::replaceChildLoopWith(llvm::Loop*, llvm::Loop*)
Line
Count
Source
214
122
                                                   LoopT *NewChild) {
215
122
  assert(!isInvalid() && "Loop not in a valid state!");
216
122
  assert(OldChild->ParentLoop == this && "This loop is already broken!");
217
122
  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
218
122
  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
219
122
  assert(I != SubLoops.end() && "OldChild not in loop!");
220
122
  *I = NewChild;
221
122
  OldChild->ParentLoop = nullptr;
222
122
  NewChild->ParentLoop = static_cast<LoopT *>(this);
223
122
}
224
225
/// verifyLoop - Verify loop structure
226
template <class BlockT, class LoopT>
227
4.85M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
228
4.85M
  assert(!isInvalid() && "Loop not in a valid state!");
229
#ifndef NDEBUG
230
  assert(!Blocks.empty() && "Loop header is missing");
231
232
  // Setup for using a depth-first iterator to visit every block in the loop.
233
  SmallVector<BlockT *, 8> ExitBBs;
234
  getExitBlocks(ExitBBs);
235
  df_iterator_default_set<BlockT *> VisitSet;
236
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
237
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
238
      BI = df_ext_begin(getHeader(), VisitSet),
239
      BE = df_ext_end(getHeader(), VisitSet);
240
241
  // Keep track of the BBs visited.
242
  SmallPtrSet<BlockT *, 8> VisitedBBs;
243
244
  // Check the individual blocks.
245
  for (; BI != BE; ++BI) {
246
    BlockT *BB = *BI;
247
248
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
249
                       GraphTraits<BlockT *>::child_end(BB),
250
                       [&](BlockT *B) { return contains(B); }) &&
251
           "Loop block has no in-loop successors!");
252
253
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
254
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
255
                       [&](BlockT *B) { return contains(B); }) &&
256
           "Loop block has no in-loop predecessors!");
257
258
    SmallVector<BlockT *, 2> OutsideLoopPreds;
259
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
260
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
261
                  [&](BlockT *B) {
262
                    if (!contains(B))
263
                      OutsideLoopPreds.push_back(B);
264
                  });
265
266
    if (BB == getHeader()) {
267
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
268
    } else if (!OutsideLoopPreds.empty()) {
269
      // A non-header loop shouldn't be reachable from outside the loop,
270
      // though it is permitted if the predecessor is not itself actually
271
      // reachable.
272
      BlockT *EntryBB = &BB->getParent()->front();
273
      for (BlockT *CB : depth_first(EntryBB))
274
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
275
          assert(CB != OutsideLoopPreds[i] &&
276
                 "Loop has multiple entry points!");
277
    }
278
    assert(BB != &getHeader()->getParent()->front() &&
279
           "Loop contains function entry block!");
280
281
    VisitedBBs.insert(BB);
282
  }
283
284
  if (VisitedBBs.size() != getNumBlocks()) {
285
    dbgs() << "The following blocks are unreachable in the loop: ";
286
    for (auto BB : Blocks) {
287
      if (!VisitedBBs.count(BB)) {
288
        dbgs() << *BB << "\n";
289
      }
290
    }
291
    assert(false && "Unreachable block in loop");
292
  }
293
294
  // Check the subloops.
295
  for (iterator I = begin(), E = end(); I != E; ++I)
296
    // Each block in each subloop should be contained within this loop.
297
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
298
         BI != BE; ++BI) {
299
      assert(contains(*BI) &&
300
             "Loop does not contain all the blocks of a subloop!");
301
    }
302
303
  // Check the parent loop pointer.
304
  if (ParentLoop) {
305
    assert(is_contained(*ParentLoop, this) &&
306
           "Loop is not a subloop of its parent!");
307
  }
308
#endif
309
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoop() const
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoop() const
Line
Count
Source
227
4.85M
void LoopBase<BlockT, LoopT>::verifyLoop() const {
228
4.85M
  assert(!isInvalid() && "Loop not in a valid state!");
229
#ifndef NDEBUG
230
  assert(!Blocks.empty() && "Loop header is missing");
231
232
  // Setup for using a depth-first iterator to visit every block in the loop.
233
  SmallVector<BlockT *, 8> ExitBBs;
234
  getExitBlocks(ExitBBs);
235
  df_iterator_default_set<BlockT *> VisitSet;
236
  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
237
  df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
238
      BI = df_ext_begin(getHeader(), VisitSet),
239
      BE = df_ext_end(getHeader(), VisitSet);
240
241
  // Keep track of the BBs visited.
242
  SmallPtrSet<BlockT *, 8> VisitedBBs;
243
244
  // Check the individual blocks.
245
  for (; BI != BE; ++BI) {
246
    BlockT *BB = *BI;
247
248
    assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
249
                       GraphTraits<BlockT *>::child_end(BB),
250
                       [&](BlockT *B) { return contains(B); }) &&
251
           "Loop block has no in-loop successors!");
252
253
    assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
254
                       GraphTraits<Inverse<BlockT *>>::child_end(BB),
255
                       [&](BlockT *B) { return contains(B); }) &&
256
           "Loop block has no in-loop predecessors!");
257
258
    SmallVector<BlockT *, 2> OutsideLoopPreds;
259
    std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
260
                  GraphTraits<Inverse<BlockT *>>::child_end(BB),
261
                  [&](BlockT *B) {
262
                    if (!contains(B))
263
                      OutsideLoopPreds.push_back(B);
264
                  });
265
266
    if (BB == getHeader()) {
267
      assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
268
    } else if (!OutsideLoopPreds.empty()) {
269
      // A non-header loop shouldn't be reachable from outside the loop,
270
      // though it is permitted if the predecessor is not itself actually
271
      // reachable.
272
      BlockT *EntryBB = &BB->getParent()->front();
273
      for (BlockT *CB : depth_first(EntryBB))
274
        for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
275
          assert(CB != OutsideLoopPreds[i] &&
276
                 "Loop has multiple entry points!");
277
    }
278
    assert(BB != &getHeader()->getParent()->front() &&
279
           "Loop contains function entry block!");
280
281
    VisitedBBs.insert(BB);
282
  }
283
284
  if (VisitedBBs.size() != getNumBlocks()) {
285
    dbgs() << "The following blocks are unreachable in the loop: ";
286
    for (auto BB : Blocks) {
287
      if (!VisitedBBs.count(BB)) {
288
        dbgs() << *BB << "\n";
289
      }
290
    }
291
    assert(false && "Unreachable block in loop");
292
  }
293
294
  // Check the subloops.
295
  for (iterator I = begin(), E = end(); I != E; ++I)
296
    // Each block in each subloop should be contained within this loop.
297
    for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
298
         BI != BE; ++BI) {
299
      assert(contains(*BI) &&
300
             "Loop does not contain all the blocks of a subloop!");
301
    }
302
303
  // Check the parent loop pointer.
304
  if (ParentLoop) {
305
    assert(is_contained(*ParentLoop, this) &&
306
           "Loop is not a subloop of its parent!");
307
  }
308
#endif
309
}
310
311
/// verifyLoop - Verify loop structure of this loop and all nested loops.
312
template <class BlockT, class LoopT>
313
void LoopBase<BlockT, LoopT>::verifyLoopNest(
314
54
    DenseSet<const LoopT *> *Loops) const {
315
54
  assert(!isInvalid() && "Loop not in a valid state!");
316
54
  Loops->insert(static_cast<const LoopT *>(this));
317
54
  // Verify this loop.
318
54
  verifyLoop();
319
54
  // Verify the subloops.
320
77
  for (iterator I = begin(), E = end(); 
I != E77
;
++I23
)
321
23
    (*I)->verifyLoopNest(Loops);
322
54
}
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::verifyLoopNest(llvm::DenseSet<llvm::Loop const*, llvm::DenseMapInfo<llvm::Loop const*> >*) const
Line
Count
Source
314
54
    DenseSet<const LoopT *> *Loops) const {
315
54
  assert(!isInvalid() && "Loop not in a valid state!");
316
54
  Loops->insert(static_cast<const LoopT *>(this));
317
54
  // Verify this loop.
318
54
  verifyLoop();
319
54
  // Verify the subloops.
320
77
  for (iterator I = begin(), E = end(); 
I != E77
;
++I23
)
321
23
    (*I)->verifyLoopNest(Loops);
322
54
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verifyLoopNest(llvm::DenseSet<llvm::MachineLoop const*, llvm::DenseMapInfo<llvm::MachineLoop const*> >*) const
323
324
template <class BlockT, class LoopT>
325
void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth,
326
531
                                    bool Verbose) const {
327
531
  OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: ";
328
531
329
531
  BlockT *H = getHeader();
330
1.55k
  for (unsigned i = 0; 
i < getBlocks().size()1.55k
;
++i1.02k
) {
331
1.02k
    BlockT *BB = getBlocks()[i];
332
1.02k
    if (
!Verbose1.02k
) {
333
1.02k
      if (i)
334
492
        OS << ",";
335
1.02k
      BB->printAsOperand(OS, false);
336
1.02k
    } else
337
0
      OS << "\n";
338
1.02k
339
1.02k
    if (BB == H)
340
531
      OS << "<header>";
341
1.02k
    if (isLoopLatch(BB))
342
531
      OS << "<latch>";
343
1.02k
    if (isLoopExiting(BB))
344
570
      OS << "<exiting>";
345
1.02k
    if (Verbose)
346
0
      BB->print(OS);
347
1.02k
  }
348
531
  OS << "\n";
349
531
350
659
  for (iterator I = begin(), E = end(); 
I != E659
;
++I128
)
351
128
    (*I)->print(OS, Depth + 2);
352
531
}
Unexecuted instantiation: llvm::LoopBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&, unsigned int, bool) const
llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&, unsigned int, bool) const
Line
Count
Source
326
531
                                    bool Verbose) const {
327
531
  OS.indent(Depth * 2) << "Loop at depth " << getLoopDepth() << " containing: ";
328
531
329
531
  BlockT *H = getHeader();
330
1.55k
  for (unsigned i = 0; 
i < getBlocks().size()1.55k
;
++i1.02k
) {
331
1.02k
    BlockT *BB = getBlocks()[i];
332
1.02k
    if (
!Verbose1.02k
) {
333
1.02k
      if (i)
334
492
        OS << ",";
335
1.02k
      BB->printAsOperand(OS, false);
336
1.02k
    } else
337
0
      OS << "\n";
338
1.02k
339
1.02k
    if (BB == H)
340
531
      OS << "<header>";
341
1.02k
    if (isLoopLatch(BB))
342
531
      OS << "<latch>";
343
1.02k
    if (isLoopExiting(BB))
344
570
      OS << "<exiting>";
345
1.02k
    if (Verbose)
346
0
      BB->print(OS);
347
1.02k
  }
348
531
  OS << "\n";
349
531
350
659
  for (iterator I = begin(), E = end(); 
I != E659
;
++I128
)
351
128
    (*I)->print(OS, Depth + 2);
352
531
}
353
354
//===----------------------------------------------------------------------===//
355
/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
356
/// result does / not depend on use list (block predecessor) order.
357
///
358
359
/// Discover a subloop with the specified backedges such that: All blocks within
360
/// this loop are mapped to this loop or a subloop. And all subloops within this
361
/// loop have their parent loop set to this loop or a subloop.
362
template <class BlockT, class LoopT>
363
static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
364
                                  LoopInfoBase<BlockT, LoopT> *LI,
365
7.59M
                                  const DomTreeBase<BlockT> &DomTree) {
366
7.59M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
367
7.59M
368
7.59M
  unsigned NumBlocks = 0;
369
7.59M
  unsigned NumSubloops = 0;
370
7.59M
371
7.59M
  // Perform a backward CFG traversal using a worklist.
372
7.59M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
373
41.4M
  while (
!ReverseCFGWorklist.empty()41.4M
) {
374
33.8M
    BlockT *PredBB = ReverseCFGWorklist.back();
375
33.8M
    ReverseCFGWorklist.pop_back();
376
33.8M
377
33.8M
    LoopT *Subloop = LI->getLoopFor(PredBB);
378
33.8M
    if (
!Subloop33.8M
) {
379
23.8M
      if (!DomTree.isReachableFromEntry(PredBB))
380
24
        continue;
381
23.8M
382
23.8M
      // This is an undiscovered block. Map it to the current loop.
383
23.8M
      LI->changeLoopFor(PredBB, L);
384
23.8M
      ++NumBlocks;
385
23.8M
      if (PredBB == L->getHeader())
386
7.59M
        continue;
387
23.8M
      // Push all block predecessors on the worklist.
388
16.2M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
389
16.2M
                                InvBlockTraits::child_begin(PredBB),
390
16.2M
                                InvBlockTraits::child_end(PredBB));
391
33.8M
    } else {
392
10.0M
      // This is a discovered block. Find its outermost discovered loop.
393
10.4M
      while (LoopT *Parent = Subloop->getParentLoop())
394
428k
        Subloop = Parent;
395
10.0M
396
10.0M
      // If it is already discovered to be a subloop of this loop, continue.
397
10.0M
      if (Subloop == L)
398
7.86M
        continue;
399
10.0M
400
10.0M
      // Discover a subloop of this loop.
401
2.15M
      Subloop->setParentLoop(L);
402
2.15M
      ++NumSubloops;
403
2.15M
      NumBlocks += Subloop->getBlocks().capacity();
404
2.15M
      PredBB = Subloop->getHeader();
405
2.15M
      // Continue traversal along predecessors that are not loop-back edges from
406
2.15M
      // within this subloop tree itself. Note that a predecessor may directly
407
2.15M
      // reach another subloop that is not yet discovered to be a subloop of
408
2.15M
      // this loop, which we must traverse.
409
4.33M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
410
4.33M
        if (LI->getLoopFor(Pred) != Subloop)
411
2.16M
          ReverseCFGWorklist.push_back(Pred);
412
4.33M
      }
413
10.0M
    }
414
33.8M
  }
415
7.59M
  L->getSubLoopsVector().reserve(NumSubloops);
416
7.59M
  L->reserveBlocks(NumBlocks);
417
7.59M
}
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
365
2.15M
                                  const DomTreeBase<BlockT> &DomTree) {
366
2.15M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
367
2.15M
368
2.15M
  unsigned NumBlocks = 0;
369
2.15M
  unsigned NumSubloops = 0;
370
2.15M
371
2.15M
  // Perform a backward CFG traversal using a worklist.
372
2.15M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
373
11.7M
  while (
!ReverseCFGWorklist.empty()11.7M
) {
374
9.55M
    BlockT *PredBB = ReverseCFGWorklist.back();
375
9.55M
    ReverseCFGWorklist.pop_back();
376
9.55M
377
9.55M
    LoopT *Subloop = LI->getLoopFor(PredBB);
378
9.55M
    if (
!Subloop9.55M
) {
379
6.72M
      if (!DomTree.isReachableFromEntry(PredBB))
380
0
        continue;
381
6.72M
382
6.72M
      // This is an undiscovered block. Map it to the current loop.
383
6.72M
      LI->changeLoopFor(PredBB, L);
384
6.72M
      ++NumBlocks;
385
6.72M
      if (PredBB == L->getHeader())
386
2.15M
        continue;
387
6.72M
      // Push all block predecessors on the worklist.
388
4.56M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
389
4.56M
                                InvBlockTraits::child_begin(PredBB),
390
4.56M
                                InvBlockTraits::child_end(PredBB));
391
9.55M
    } else {
392
2.83M
      // This is a discovered block. Find its outermost discovered loop.
393
3.00M
      while (LoopT *Parent = Subloop->getParentLoop())
394
168k
        Subloop = Parent;
395
2.83M
396
2.83M
      // If it is already discovered to be a subloop of this loop, continue.
397
2.83M
      if (Subloop == L)
398
2.21M
        continue;
399
2.83M
400
2.83M
      // Discover a subloop of this loop.
401
618k
      Subloop->setParentLoop(L);
402
618k
      ++NumSubloops;
403
618k
      NumBlocks += Subloop->getBlocks().capacity();
404
618k
      PredBB = Subloop->getHeader();
405
618k
      // Continue traversal along predecessors that are not loop-back edges from
406
618k
      // within this subloop tree itself. Note that a predecessor may directly
407
618k
      // reach another subloop that is not yet discovered to be a subloop of
408
618k
      // this loop, which we must traverse.
409
1.25M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
410
1.25M
        if (LI->getLoopFor(Pred) != Subloop)
411
625k
          ReverseCFGWorklist.push_back(Pred);
412
1.25M
      }
413
2.83M
    }
414
9.55M
  }
415
2.15M
  L->getSubLoopsVector().reserve(NumSubloops);
416
2.15M
  L->reserveBlocks(NumBlocks);
417
2.15M
}
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
365
5.43M
                                  const DomTreeBase<BlockT> &DomTree) {
366
5.43M
  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
367
5.43M
368
5.43M
  unsigned NumBlocks = 0;
369
5.43M
  unsigned NumSubloops = 0;
370
5.43M
371
5.43M
  // Perform a backward CFG traversal using a worklist.
372
5.43M
  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
373
29.7M
  while (
!ReverseCFGWorklist.empty()29.7M
) {
374
24.3M
    BlockT *PredBB = ReverseCFGWorklist.back();
375
24.3M
    ReverseCFGWorklist.pop_back();
376
24.3M
377
24.3M
    LoopT *Subloop = LI->getLoopFor(PredBB);
378
24.3M
    if (
!Subloop24.3M
) {
379
17.1M
      if (!DomTree.isReachableFromEntry(PredBB))
380
24
        continue;
381
17.1M
382
17.1M
      // This is an undiscovered block. Map it to the current loop.
383
17.1M
      LI->changeLoopFor(PredBB, L);
384
17.1M
      ++NumBlocks;
385
17.1M
      if (PredBB == L->getHeader())
386
5.43M
        continue;
387
17.1M
      // Push all block predecessors on the worklist.
388
11.7M
      ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
389
11.7M
                                InvBlockTraits::child_begin(PredBB),
390
11.7M
                                InvBlockTraits::child_end(PredBB));
391
24.3M
    } else {
392
7.18M
      // This is a discovered block. Find its outermost discovered loop.
393
7.45M
      while (LoopT *Parent = Subloop->getParentLoop())
394
260k
        Subloop = Parent;
395
7.18M
396
7.18M
      // If it is already discovered to be a subloop of this loop, continue.
397
7.18M
      if (Subloop == L)
398
5.65M
        continue;
399
7.18M
400
7.18M
      // Discover a subloop of this loop.
401
1.53M
      Subloop->setParentLoop(L);
402
1.53M
      ++NumSubloops;
403
1.53M
      NumBlocks += Subloop->getBlocks().capacity();
404
1.53M
      PredBB = Subloop->getHeader();
405
1.53M
      // Continue traversal along predecessors that are not loop-back edges from
406
1.53M
      // within this subloop tree itself. Note that a predecessor may directly
407
1.53M
      // reach another subloop that is not yet discovered to be a subloop of
408
1.53M
      // this loop, which we must traverse.
409
3.08M
      for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
410
3.08M
        if (LI->getLoopFor(Pred) != Subloop)
411
1.54M
          ReverseCFGWorklist.push_back(Pred);
412
3.08M
      }
413
7.18M
    }
414
24.3M
  }
415
5.43M
  L->getSubLoopsVector().reserve(NumSubloops);
416
5.43M
  L->reserveBlocks(NumBlocks);
417
5.43M
}
418
419
/// Populate all loop data in a stable order during a single forward DFS.
420
template <class BlockT, class LoopT> class PopulateLoopsDFS {
421
  typedef GraphTraits<BlockT *> BlockTraits;
422
  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
423
424
  LoopInfoBase<BlockT, LoopT> *LI;
425
426
public:
427
12.0M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>*)
Line
Count
Source
427
8.47M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::PopulateLoopsDFS(llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>*)
Line
Count
Source
427
3.58M
  PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
428
429
  void traverse(BlockT *EntryBlock);
430
431
protected:
432
  void insertIntoLoop(BlockT *Block);
433
};
434
435
/// Top-level driver for the forward DFS within the loop.
436
template <class BlockT, class LoopT>
437
12.0M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
438
12.0M
  for (BlockT *BB : post_order(EntryBlock))
439
82.6M
    insertIntoLoop(BB);
440
12.0M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::traverse(llvm::MachineBasicBlock*)
Line
Count
Source
437
3.58M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
438
3.58M
  for (BlockT *BB : post_order(EntryBlock))
439
23.7M
    insertIntoLoop(BB);
440
3.58M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::traverse(llvm::BasicBlock*)
Line
Count
Source
437
8.47M
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
438
8.47M
  for (BlockT *BB : post_order(EntryBlock))
439
58.9M
    insertIntoLoop(BB);
440
8.47M
}
441
442
/// Add a single Block to its ancestor loops in PostOrder. If the block is a
443
/// subloop header, add the subloop to its parent in PostOrder, then reverse the
444
/// Block and Subloop vectors of the now complete subloop to achieve RPO.
445
template <class BlockT, class LoopT>
446
82.6M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
447
82.6M
  LoopT *Subloop = LI->getLoopFor(Block);
448
82.6M
  if (
Subloop && 82.6M
Block == Subloop->getHeader()23.8M
) {
449
7.59M
    // We reach this point once per subloop after processing all the blocks in
450
7.59M
    // the subloop.
451
7.59M
    if (Subloop->getParentLoop())
452
2.15M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
453
7.59M
    else
454
5.43M
      LI->addTopLevelLoop(Subloop);
455
7.59M
456
7.59M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
457
7.59M
    // the lists, except for the loop header, which is always at the beginning.
458
7.59M
    Subloop->reverseBlock(1);
459
7.59M
    std::reverse(Subloop->getSubLoopsVector().begin(),
460
7.59M
                 Subloop->getSubLoopsVector().end());
461
7.59M
462
7.59M
    Subloop = Subloop->getParentLoop();
463
7.59M
  }
464
107M
  for (; 
Subloop107M
;
Subloop = Subloop->getParentLoop()24.6M
)
465
24.6M
    Subloop->addBlockEntry(Block);
466
82.6M
}
llvm::PopulateLoopsDFS<llvm::BasicBlock, llvm::Loop>::insertIntoLoop(llvm::BasicBlock*)
Line
Count
Source
446
58.9M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
447
58.9M
  LoopT *Subloop = LI->getLoopFor(Block);
448
58.9M
  if (
Subloop && 58.9M
Block == Subloop->getHeader()17.1M
) {
449
5.43M
    // We reach this point once per subloop after processing all the blocks in
450
5.43M
    // the subloop.
451
5.43M
    if (Subloop->getParentLoop())
452
1.53M
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
453
5.43M
    else
454
3.89M
      LI->addTopLevelLoop(Subloop);
455
5.43M
456
5.43M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
457
5.43M
    // the lists, except for the loop header, which is always at the beginning.
458
5.43M
    Subloop->reverseBlock(1);
459
5.43M
    std::reverse(Subloop->getSubLoopsVector().begin(),
460
5.43M
                 Subloop->getSubLoopsVector().end());
461
5.43M
462
5.43M
    Subloop = Subloop->getParentLoop();
463
5.43M
  }
464
76.6M
  for (; 
Subloop76.6M
;
Subloop = Subloop->getParentLoop()17.6M
)
465
17.6M
    Subloop->addBlockEntry(Block);
466
58.9M
}
llvm::PopulateLoopsDFS<llvm::MachineBasicBlock, llvm::MachineLoop>::insertIntoLoop(llvm::MachineBasicBlock*)
Line
Count
Source
446
23.7M
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
447
23.7M
  LoopT *Subloop = LI->getLoopFor(Block);
448
23.7M
  if (
Subloop && 23.7M
Block == Subloop->getHeader()6.72M
) {
449
2.15M
    // We reach this point once per subloop after processing all the blocks in
450
2.15M
    // the subloop.
451
2.15M
    if (Subloop->getParentLoop())
452
618k
      Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
453
2.15M
    else
454
1.53M
      LI->addTopLevelLoop(Subloop);
455
2.15M
456
2.15M
    // For convenience, Blocks and Subloops are inserted in postorder. Reverse
457
2.15M
    // the lists, except for the loop header, which is always at the beginning.
458
2.15M
    Subloop->reverseBlock(1);
459
2.15M
    std::reverse(Subloop->getSubLoopsVector().begin(),
460
2.15M
                 Subloop->getSubLoopsVector().end());
461
2.15M
462
2.15M
    Subloop = Subloop->getParentLoop();
463
2.15M
  }
464
30.6M
  for (; 
Subloop30.6M
;
Subloop = Subloop->getParentLoop()6.97M
)
465
6.97M
    Subloop->addBlockEntry(Block);
466
23.7M
}
467
468
/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
469
/// interleaved with backward CFG traversals within each subloop
470
/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
471
/// this part of the algorithm is linear in the number of CFG edges. Subloop and
472
/// Block vectors are then populated during a single forward CFG traversal
473
/// (PopulateLoopDFS).
474
///
475
/// During the two CFG traversals each block is seen three times:
476
/// 1) Discovered and mapped by a reverse CFG traversal.
477
/// 2) Visited during a forward DFS CFG traversal.
478
/// 3) Reverse-inserted in the loop in postorder following forward DFS.
479
///
480
/// The Block vectors are inclusive, so step 3 requires loop-depth number of
481
/// insertions per block.
482
template <class BlockT, class LoopT>
483
12.0M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
484
12.0M
  // Postorder traversal of the dominator tree.
485
12.0M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
486
82.6M
  for (auto DomNode : post_order(DomRoot)) {
487
82.6M
488
82.6M
    BlockT *Header = DomNode->getBlock();
489
82.6M
    SmallVector<BlockT *, 4> Backedges;
490
82.6M
491
82.6M
    // Check each predecessor of the potential loop header.
492
109M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
493
109M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
494
109M
      if (DomTree.dominates(Header, Backedge) &&
495
109M
          
DomTree.isReachableFromEntry(Backedge)7.75M
) {
496
7.75M
        Backedges.push_back(Backedge);
497
7.75M
      }
498
109M
    }
499
82.6M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
500
82.6M
    if (
!Backedges.empty()82.6M
) {
501
7.59M
      LoopT *L = AllocateLoop(Header);
502
7.59M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
503
7.59M
    }
504
82.6M
  }
505
12.0M
  // Perform a single forward CFG traversal to populate block and subloop
506
12.0M
  // vectors for all loops.
507
12.0M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
508
12.0M
  DFS.traverse(DomRoot->getBlock());
509
12.0M
}
llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&)
Line
Count
Source
483
3.58M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
484
3.58M
  // Postorder traversal of the dominator tree.
485
3.58M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
486
23.7M
  for (auto DomNode : post_order(DomRoot)) {
487
23.7M
488
23.7M
    BlockT *Header = DomNode->getBlock();
489
23.7M
    SmallVector<BlockT *, 4> Backedges;
490
23.7M
491
23.7M
    // Check each predecessor of the potential loop header.
492
30.4M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
493
30.4M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
494
30.4M
      if (DomTree.dominates(Header, Backedge) &&
495
30.4M
          
DomTree.isReachableFromEntry(Backedge)2.28M
) {
496
2.28M
        Backedges.push_back(Backedge);
497
2.28M
      }
498
30.4M
    }
499
23.7M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
500
23.7M
    if (
!Backedges.empty()23.7M
) {
501
2.15M
      LoopT *L = AllocateLoop(Header);
502
2.15M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
503
2.15M
    }
504
23.7M
  }
505
3.58M
  // Perform a single forward CFG traversal to populate block and subloop
506
3.58M
  // vectors for all loops.
507
3.58M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
508
3.58M
  DFS.traverse(DomRoot->getBlock());
509
3.58M
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&)
Line
Count
Source
483
8.47M
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
484
8.47M
  // Postorder traversal of the dominator tree.
485
8.47M
  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
486
58.9M
  for (auto DomNode : post_order(DomRoot)) {
487
58.9M
488
58.9M
    BlockT *Header = DomNode->getBlock();
489
58.9M
    SmallVector<BlockT *, 4> Backedges;
490
58.9M
491
58.9M
    // Check each predecessor of the potential loop header.
492
79.3M
    for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
493
79.3M
      // If Header dominates predBB, this is a new loop. Collect the backedges.
494
79.3M
      if (DomTree.dominates(Header, Backedge) &&
495
79.3M
          
DomTree.isReachableFromEntry(Backedge)5.46M
) {
496
5.46M
        Backedges.push_back(Backedge);
497
5.46M
      }
498
79.3M
    }
499
58.9M
    // Perform a backward CFG traversal to discover and map blocks in this loop.
500
58.9M
    if (
!Backedges.empty()58.9M
) {
501
5.43M
      LoopT *L = AllocateLoop(Header);
502
5.43M
      discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
503
5.43M
    }
504
58.9M
  }
505
8.47M
  // Perform a single forward CFG traversal to populate block and subloop
506
8.47M
  // vectors for all loops.
507
8.47M
  PopulateLoopsDFS<BlockT, LoopT> DFS(this);
508
8.47M
  DFS.traverse(DomRoot->getBlock());
509
8.47M
}
510
511
template <class BlockT, class LoopT>
512
46
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
513
46
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
514
46
  // The outer-most loop actually goes into the result in the same relative
515
46
  // order as we walk it. But LoopInfo stores the top level loops in reverse
516
46
  // program order so for here we reverse it to get forward program order.
517
46
  // FIXME: If we change the order of LoopInfo we will want to remove the
518
46
  // reverse here.
519
46
  for (LoopT *RootL : reverse(*this)) {
520
46
    assert(PreOrderWorklist.empty() &&
521
46
           "Must start with an empty preorder walk worklist.");
522
46
    PreOrderWorklist.push_back(RootL);
523
59
    do {
524
59
      LoopT *L = PreOrderWorklist.pop_back_val();
525
59
      // Sub-loops are stored in forward program order, but will process the
526
59
      // worklist backwards so append them in reverse order.
527
59
      PreOrderWorklist.append(L->rbegin(), L->rend());
528
59
      PreOrderLoops.push_back(L);
529
59
    } while (!PreOrderWorklist.empty());
530
46
  }
531
46
532
46
  return PreOrderLoops;
533
46
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInPreorder()
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInPreorder()
Line
Count
Source
512
46
SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
513
46
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
514
46
  // The outer-most loop actually goes into the result in the same relative
515
46
  // order as we walk it. But LoopInfo stores the top level loops in reverse
516
46
  // program order so for here we reverse it to get forward program order.
517
46
  // FIXME: If we change the order of LoopInfo we will want to remove the
518
46
  // reverse here.
519
46
  for (LoopT *RootL : reverse(*this)) {
520
46
    assert(PreOrderWorklist.empty() &&
521
46
           "Must start with an empty preorder walk worklist.");
522
46
    PreOrderWorklist.push_back(RootL);
523
59
    do {
524
59
      LoopT *L = PreOrderWorklist.pop_back_val();
525
59
      // Sub-loops are stored in forward program order, but will process the
526
59
      // worklist backwards so append them in reverse order.
527
59
      PreOrderWorklist.append(L->rbegin(), L->rend());
528
59
      PreOrderLoops.push_back(L);
529
59
    } while (!PreOrderWorklist.empty());
530
46
  }
531
46
532
46
  return PreOrderLoops;
533
46
}
534
535
template <class BlockT, class LoopT>
536
SmallVector<LoopT *, 4>
537
245
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
538
245
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
539
245
  // The outer-most loop actually goes into the result in the same relative
540
245
  // order as we walk it. LoopInfo stores the top level loops in reverse
541
245
  // program order so we walk in order here.
542
245
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
543
245
  // here.
544
230
  for (LoopT *RootL : *this) {
545
230
    assert(PreOrderWorklist.empty() &&
546
230
           "Must start with an empty preorder walk worklist.");
547
230
    PreOrderWorklist.push_back(RootL);
548
302
    do {
549
302
      LoopT *L = PreOrderWorklist.pop_back_val();
550
302
      // Sub-loops are stored in forward program order, but will process the
551
302
      // worklist backwards so we can just append them in order.
552
302
      PreOrderWorklist.append(L->begin(), L->end());
553
302
      PreOrderLoops.push_back(L);
554
302
    } while (!PreOrderWorklist.empty());
555
230
  }
556
245
557
245
  return PreOrderLoops;
558
245
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::getLoopsInReverseSiblingPreorder()
Line
Count
Source
537
245
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
538
245
  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
539
245
  // The outer-most loop actually goes into the result in the same relative
540
245
  // order as we walk it. LoopInfo stores the top level loops in reverse
541
245
  // program order so we walk in order here.
542
245
  // FIXME: If we change the order of LoopInfo we will want to add a reverse
543
245
  // here.
544
230
  for (LoopT *RootL : *this) {
545
230
    assert(PreOrderWorklist.empty() &&
546
230
           "Must start with an empty preorder walk worklist.");
547
230
    PreOrderWorklist.push_back(RootL);
548
302
    do {
549
302
      LoopT *L = PreOrderWorklist.pop_back_val();
550
302
      // Sub-loops are stored in forward program order, but will process the
551
302
      // worklist backwards so we can just append them in order.
552
302
      PreOrderWorklist.append(L->begin(), L->end());
553
302
      PreOrderLoops.push_back(L);
554
302
    } while (!PreOrderWorklist.empty());
555
230
  }
556
245
557
245
  return PreOrderLoops;
558
245
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::getLoopsInReverseSiblingPreorder()
559
560
// Debugging
561
template <class BlockT, class LoopT>
562
7
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
563
16
  for (unsigned i = 0; 
i < TopLevelLoops.size()16
;
++i9
)
564
9
    TopLevelLoops[i]->print(OS);
565
#if 0
566
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
567
         E = BBMap.end(); I != E; ++I)
568
    OS << "BB '" << I->first->getName() << "' level = "
569
       << I->second->getLoopDepth() << "\n";
570
#endif
571
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::print(llvm::raw_ostream&) const
Line
Count
Source
562
7
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
563
16
  for (unsigned i = 0; 
i < TopLevelLoops.size()16
;
++i9
)
564
9
    TopLevelLoops[i]->print(OS);
565
#if 0
566
  for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
567
         E = BBMap.end(); I != E; ++I)
568
    OS << "BB '" << I->first->getName() << "' level = "
569
       << I->second->getLoopDepth() << "\n";
570
#endif
571
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::print(llvm::raw_ostream&) const
572
573
template <typename T>
574
bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
575
  std::sort(BB1.begin(), BB1.end());
576
  std::sort(BB2.begin(), BB2.end());
577
  return BB1 == BB2;
578
}
579
580
template <class BlockT, class LoopT>
581
void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
582
                               const LoopInfoBase<BlockT, LoopT> &LI,
583
                               const LoopT &L) {
584
  LoopHeaders[L.getHeader()] = &L;
585
  for (LoopT *SL : L)
586
    addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
587
}
588
589
#ifndef NDEBUG
590
template <class BlockT, class LoopT>
591
static void compareLoops(const LoopT *L, const LoopT *OtherL,
592
                         DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
593
  BlockT *H = L->getHeader();
594
  BlockT *OtherH = OtherL->getHeader();
595
  assert(H == OtherH &&
596
         "Mismatched headers even though found in the same map entry!");
597
598
  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
599
         "Mismatched loop depth!");
600
  const LoopT *ParentL = L, *OtherParentL = OtherL;
601
  do {
602
    assert(ParentL->getHeader() == OtherParentL->getHeader() &&
603
           "Mismatched parent loop headers!");
604
    ParentL = ParentL->getParentLoop();
605
    OtherParentL = OtherParentL->getParentLoop();
606
  } while (ParentL);
607
608
  for (const LoopT *SubL : *L) {
609
    BlockT *SubH = SubL->getHeader();
610
    const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
611
    assert(OtherSubL && "Inner loop is missing in computed loop info!");
612
    OtherLoopHeaders.erase(SubH);
613
    compareLoops(SubL, OtherSubL, OtherLoopHeaders);
614
  }
615
616
  std::vector<BlockT *> BBs = L->getBlocks();
617
  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
618
  assert(compareVectors(BBs, OtherBBs) &&
619
         "Mismatched basic blocks in the loops!");
620
}
621
#endif
622
623
template <class BlockT, class LoopT>
624
void LoopInfoBase<BlockT, LoopT>::verify(
625
28
    const DomTreeBase<BlockT> &DomTree) const {
626
28
  DenseSet<const LoopT *> Loops;
627
59
  for (iterator I = begin(), E = end(); 
I != E59
;
++I31
) {
628
31
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
629
31
    (*I)->verifyLoopNest(&Loops);
630
31
  }
631
28
632
28
// Verify that blocks are mapped to valid loops.
633
#ifndef NDEBUG
634
  for (auto &Entry : BBMap) {
635
    const BlockT *BB = Entry.first;
636
    LoopT *L = Entry.second;
637
    assert(Loops.count(L) && "orphaned loop");
638
    assert(L->contains(BB) && "orphaned block");
639
  }
640
641
  // Recompute LoopInfo to verify loops structure.
642
  LoopInfoBase<BlockT, LoopT> OtherLI;
643
  OtherLI.analyze(DomTree);
644
645
  // Build a map we can use to move from our LI to the computed one. This
646
  // allows us to ignore the particular order in any layer of the loop forest
647
  // while still comparing the structure.
648
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
649
  for (LoopT *L : OtherLI)
650
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
651
652
  // Walk the top level loops and ensure there is a corresponding top-level
653
  // loop in the computed version and then recursively compare those loop
654
  // nests.
655
  for (LoopT *L : *this) {
656
    BlockT *Header = L->getHeader();
657
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
658
    assert(OtherL && "Top level loop is missing in computed loop info!");
659
    // Now that we've matched this loop, erase its header from the map.
660
    OtherLoopHeaders.erase(Header);
661
    // And recursively compare these loops.
662
    compareLoops(L, OtherL, OtherLoopHeaders);
663
  }
664
665
  // Any remaining entries in the map are loops which were found when computing
666
  // a fresh LoopInfo but not present in the current one.
667
  if (!OtherLoopHeaders.empty()) {
668
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
669
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
670
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
671
  }
672
#endif
673
}
llvm::LoopInfoBase<llvm::BasicBlock, llvm::Loop>::verify(llvm::DominatorTreeBase<llvm::BasicBlock, false> const&) const
Line
Count
Source
625
28
    const DomTreeBase<BlockT> &DomTree) const {
626
28
  DenseSet<const LoopT *> Loops;
627
59
  for (iterator I = begin(), E = end(); 
I != E59
;
++I31
) {
628
31
    assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
629
31
    (*I)->verifyLoopNest(&Loops);
630
31
  }
631
28
632
28
// Verify that blocks are mapped to valid loops.
633
#ifndef NDEBUG
634
  for (auto &Entry : BBMap) {
635
    const BlockT *BB = Entry.first;
636
    LoopT *L = Entry.second;
637
    assert(Loops.count(L) && "orphaned loop");
638
    assert(L->contains(BB) && "orphaned block");
639
  }
640
641
  // Recompute LoopInfo to verify loops structure.
642
  LoopInfoBase<BlockT, LoopT> OtherLI;
643
  OtherLI.analyze(DomTree);
644
645
  // Build a map we can use to move from our LI to the computed one. This
646
  // allows us to ignore the particular order in any layer of the loop forest
647
  // while still comparing the structure.
648
  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
649
  for (LoopT *L : OtherLI)
650
    addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
651
652
  // Walk the top level loops and ensure there is a corresponding top-level
653
  // loop in the computed version and then recursively compare those loop
654
  // nests.
655
  for (LoopT *L : *this) {
656
    BlockT *Header = L->getHeader();
657
    const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
658
    assert(OtherL && "Top level loop is missing in computed loop info!");
659
    // Now that we've matched this loop, erase its header from the map.
660
    OtherLoopHeaders.erase(Header);
661
    // And recursively compare these loops.
662
    compareLoops(L, OtherL, OtherLoopHeaders);
663
  }
664
665
  // Any remaining entries in the map are loops which were found when computing
666
  // a fresh LoopInfo but not present in the current one.
667
  if (!OtherLoopHeaders.empty()) {
668
    for (const auto &HeaderAndLoop : OtherLoopHeaders)
669
      dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
670
    llvm_unreachable("Found new loops when recomputing LoopInfo!");
671
  }
672
#endif
673
}
Unexecuted instantiation: llvm::LoopInfoBase<llvm::MachineBasicBlock, llvm::MachineLoop>::verify(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false> const&) const
674
675
} // End llvm namespace
676
677
#endif