Coverage Report

Created: 2019-02-15 18:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/RegionInfoImpl.h
Line
Count
Source (jump to first uncovered line)
1
//===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
// Detects single entry single exit regions in the control flow graph.
9
//===----------------------------------------------------------------------===//
10
11
#ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
12
#define LLVM_ANALYSIS_REGIONINFOIMPL_H
13
14
#include "llvm/ADT/GraphTraits.h"
15
#include "llvm/ADT/PostOrderIterator.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/iterator_range.h"
19
#include "llvm/Analysis/DominanceFrontier.h"
20
#include "llvm/Analysis/LoopInfo.h"
21
#include "llvm/Analysis/PostDominators.h"
22
#include "llvm/Analysis/RegionInfo.h"
23
#include "llvm/Analysis/RegionIterator.h"
24
#include "llvm/Config/llvm-config.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/ErrorHandling.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include <algorithm>
29
#include <cassert>
30
#include <iterator>
31
#include <memory>
32
#include <set>
33
#include <string>
34
#include <type_traits>
35
#include <vector>
36
37
#define DEBUG_TYPE "region"
38
39
namespace llvm {
40
41
//===----------------------------------------------------------------------===//
42
/// RegionBase Implementation
43
template <class Tr>
44
RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit,
45
                           typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
46
                           RegionT *Parent)
47
29.5k
    : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::RegionBase(llvm::BasicBlock*, llvm::BasicBlock*, llvm::RegionInfo*, llvm::DominatorTree*, llvm::Region*)
Line
Count
Source
47
29.5k
    : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::RegionBase(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::MachineRegionInfo*, llvm::MachineDominatorTree*, llvm::MachineRegion*)
48
49
template <class Tr>
50
29.4k
RegionBase<Tr>::~RegionBase() {
51
29.4k
  // Only clean the cache for this Region. Caches of child Regions will be
52
29.4k
  // cleaned when the child Regions are deleted.
53
29.4k
  BBNodeMap.clear();
54
29.4k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::~RegionBase()
Line
Count
Source
50
29.4k
RegionBase<Tr>::~RegionBase() {
51
29.4k
  // Only clean the cache for this Region. Caches of child Regions will be
52
29.4k
  // cleaned when the child Regions are deleted.
53
29.4k
  BBNodeMap.clear();
54
29.4k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::~RegionBase()
55
56
template <class Tr>
57
45
void RegionBase<Tr>::replaceEntry(BlockT *BB) {
58
45
  this->entry.setPointer(BB);
59
45
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceEntry(llvm::BasicBlock*)
Line
Count
Source
57
45
void RegionBase<Tr>::replaceEntry(BlockT *BB) {
58
45
  this->entry.setPointer(BB);
59
45
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceEntry(llvm::MachineBasicBlock*)
60
61
template <class Tr>
62
541
void RegionBase<Tr>::replaceExit(BlockT *BB) {
63
541
  assert(exit && "No exit to replace!");
64
541
  exit = BB;
65
541
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceExit(llvm::BasicBlock*)
Line
Count
Source
62
541
void RegionBase<Tr>::replaceExit(BlockT *BB) {
63
541
  assert(exit && "No exit to replace!");
64
541
  exit = BB;
65
541
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceExit(llvm::MachineBasicBlock*)
66
67
template <class Tr>
68
40
void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) {
69
40
  std::vector<RegionT *> RegionQueue;
70
40
  BlockT *OldEntry = getEntry();
71
40
72
40
  RegionQueue.push_back(static_cast<RegionT *>(this));
73
80
  while (!RegionQueue.empty()) {
74
40
    RegionT *R = RegionQueue.back();
75
40
    RegionQueue.pop_back();
76
40
77
40
    R->replaceEntry(NewEntry);
78
40
    for (std::unique_ptr<RegionT> &Child : *R) {
79
12
      if (Child->getEntry() == OldEntry)
80
0
        RegionQueue.push_back(Child.get());
81
12
    }
82
40
  }
83
40
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceEntryRecursive(llvm::BasicBlock*)
Line
Count
Source
68
40
void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) {
69
40
  std::vector<RegionT *> RegionQueue;
70
40
  BlockT *OldEntry = getEntry();
71
40
72
40
  RegionQueue.push_back(static_cast<RegionT *>(this));
73
80
  while (!RegionQueue.empty()) {
74
40
    RegionT *R = RegionQueue.back();
75
40
    RegionQueue.pop_back();
76
40
77
40
    R->replaceEntry(NewEntry);
78
40
    for (std::unique_ptr<RegionT> &Child : *R) {
79
12
      if (Child->getEntry() == OldEntry)
80
0
        RegionQueue.push_back(Child.get());
81
12
    }
82
40
  }
83
40
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceEntryRecursive(llvm::MachineBasicBlock*)
84
85
template <class Tr>
86
352
void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
87
352
  std::vector<RegionT *> RegionQueue;
88
352
  BlockT *OldExit = getExit();
89
352
90
352
  RegionQueue.push_back(static_cast<RegionT *>(this));
91
735
  while (!RegionQueue.empty()) {
92
383
    RegionT *R = RegionQueue.back();
93
383
    RegionQueue.pop_back();
94
383
95
383
    R->replaceExit(NewExit);
96
383
    for (std::unique_ptr<RegionT> &Child : *R) {
97
208
      if (Child->getExit() == OldExit)
98
31
        RegionQueue.push_back(Child.get());
99
208
    }
100
383
  }
101
352
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceExitRecursive(llvm::BasicBlock*)
Line
Count
Source
86
352
void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
87
352
  std::vector<RegionT *> RegionQueue;
88
352
  BlockT *OldExit = getExit();
89
352
90
352
  RegionQueue.push_back(static_cast<RegionT *>(this));
91
735
  while (!RegionQueue.empty()) {
92
383
    RegionT *R = RegionQueue.back();
93
383
    RegionQueue.pop_back();
94
383
95
383
    R->replaceExit(NewExit);
96
383
    for (std::unique_ptr<RegionT> &Child : *R) {
97
208
      if (Child->getExit() == OldExit)
98
31
        RegionQueue.push_back(Child.get());
99
208
    }
100
383
  }
101
352
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceExitRecursive(llvm::MachineBasicBlock*)
102
103
template <class Tr>
104
498k
bool RegionBase<Tr>::contains(const BlockT *B) const {
105
498k
  BlockT *BB = const_cast<BlockT *>(B);
106
498k
107
498k
  if (!DT->getNode(BB))
108
11
    return false;
109
498k
110
498k
  BlockT *entry = getEntry(), *exit = getExit();
111
498k
112
498k
  // Toplevel region.
113
498k
  if (!exit)
114
5.03k
    return true;
115
493k
116
493k
  return (DT->dominates(entry, BB) &&
117
493k
          
!(464k
DT->dominates(exit, BB)464k
&&
DT->dominates(entry, exit)23.5k
));
118
493k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::contains(llvm::BasicBlock const*) const
Line
Count
Source
104
498k
bool RegionBase<Tr>::contains(const BlockT *B) const {
105
498k
  BlockT *BB = const_cast<BlockT *>(B);
106
498k
107
498k
  if (!DT->getNode(BB))
108
11
    return false;
109
498k
110
498k
  BlockT *entry = getEntry(), *exit = getExit();
111
498k
112
498k
  // Toplevel region.
113
498k
  if (!exit)
114
5.03k
    return true;
115
493k
116
493k
  return (DT->dominates(entry, BB) &&
117
493k
          
!(464k
DT->dominates(exit, BB)464k
&&
DT->dominates(entry, exit)23.5k
));
118
493k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::contains(llvm::MachineBasicBlock const*) const
119
120
template <class Tr>
121
151k
bool RegionBase<Tr>::contains(const LoopT *L) const {
122
151k
  // BBs that are not part of any loop are element of the Loop
123
151k
  // described by the NULL pointer. This loop is not part of any region,
124
151k
  // except if the region describes the whole function.
125
151k
  if (!L)
126
16.1k
    return getExit() == nullptr;
127
135k
128
135k
  if (!contains(L->getHeader()))
129
5.08k
    return false;
130
130k
131
130k
  SmallVector<BlockT *, 8> ExitingBlocks;
132
130k
  L->getExitingBlocks(ExitingBlocks);
133
130k
134
130k
  for (BlockT *BB : ExitingBlocks) {
135
130k
    if (!contains(BB))
136
738
      return false;
137
130k
  }
138
130k
139
130k
  
return true129k
;
140
130k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::contains(llvm::Loop const*) const
Line
Count
Source
121
151k
bool RegionBase<Tr>::contains(const LoopT *L) const {
122
151k
  // BBs that are not part of any loop are element of the Loop
123
151k
  // described by the NULL pointer. This loop is not part of any region,
124
151k
  // except if the region describes the whole function.
125
151k
  if (!L)
126
16.1k
    return getExit() == nullptr;
127
135k
128
135k
  if (!contains(L->getHeader()))
129
5.08k
    return false;
130
130k
131
130k
  SmallVector<BlockT *, 8> ExitingBlocks;
132
130k
  L->getExitingBlocks(ExitingBlocks);
133
130k
134
130k
  for (BlockT *BB : ExitingBlocks) {
135
130k
    if (!contains(BB))
136
738
      return false;
137
130k
  }
138
130k
139
130k
  
return true129k
;
140
130k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::contains(llvm::MachineLoop const*) const
141
142
template <class Tr>
143
14.9k
typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
144
14.9k
  if (!contains(L))
145
1.09k
    return nullptr;
146
13.8k
147
18.7k
  
while (13.8k
L && contains(L->getParentLoop())) {
148
4.93k
    L = L->getParentLoop();
149
4.93k
  }
150
13.8k
151
13.8k
  return L;
152
13.8k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::outermostLoopInRegion(llvm::Loop*) const
Line
Count
Source
143
14.9k
typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
144
14.9k
  if (!contains(L))
145
1.09k
    return nullptr;
146
13.8k
147
18.7k
  
while (13.8k
L && contains(L->getParentLoop())) {
148
4.93k
    L = L->getParentLoop();
149
4.93k
  }
150
13.8k
151
13.8k
  return L;
152
13.8k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::outermostLoopInRegion(llvm::MachineLoop*) const
153
154
template <class Tr>
155
typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI,
156
0
                                                          BlockT *BB) const {
157
0
  assert(LI && BB && "LI and BB cannot be null!");
158
0
  LoopT *L = LI->getLoopFor(BB);
159
0
  return outermostLoopInRegion(L);
160
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::outermostLoopInRegion(llvm::LoopInfo*, llvm::BasicBlock*) const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::outermostLoopInRegion(llvm::MachineLoopInfo*, llvm::MachineBasicBlock*) const
161
162
template <class Tr>
163
5.42k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
164
5.42k
  BlockT *entry = getEntry();
165
5.42k
  BlockT *enteringBlock = nullptr;
166
5.42k
167
5.42k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
168
8.23k
                                 InvBlockTraits::child_end(entry))) {
169
8.23k
    if (DT->getNode(Pred) && 
!contains(Pred)8.23k
) {
170
4.91k
      if (enteringBlock)
171
345
        return nullptr;
172
4.56k
173
4.56k
      enteringBlock = Pred;
174
4.56k
    }
175
8.23k
  }
176
5.42k
177
5.42k
  
return enteringBlock5.08k
;
178
5.42k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getEnteringBlock() const
Line
Count
Source
163
5.42k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
164
5.42k
  BlockT *entry = getEntry();
165
5.42k
  BlockT *enteringBlock = nullptr;
166
5.42k
167
5.42k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
168
8.23k
                                 InvBlockTraits::child_end(entry))) {
169
8.23k
    if (DT->getNode(Pred) && 
!contains(Pred)8.23k
) {
170
4.91k
      if (enteringBlock)
171
345
        return nullptr;
172
4.56k
173
4.56k
      enteringBlock = Pred;
174
4.56k
    }
175
8.23k
  }
176
5.42k
177
5.42k
  
return enteringBlock5.08k
;
178
5.42k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getEnteringBlock() const
179
180
template <class Tr>
181
bool RegionBase<Tr>::getExitingBlocks(
182
0
    SmallVectorImpl<BlockT *> &Exitings) const {
183
0
  bool CoverAll = true;
184
0
185
0
  if (!exit)
186
0
    return CoverAll;
187
0
188
0
  for (PredIterTy PI = InvBlockTraits::child_begin(exit),
189
0
                  PE = InvBlockTraits::child_end(exit);
190
0
       PI != PE; ++PI) {
191
0
    BlockT *Pred = *PI;
192
0
    if (contains(Pred)) {
193
0
      Exitings.push_back(Pred);
194
0
      continue;
195
0
    }
196
0
197
0
    CoverAll = false;
198
0
  }
199
0
200
0
  return CoverAll;
201
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getExitingBlocks(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getExitingBlocks(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
202
203
template <class Tr>
204
5.19k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
205
5.19k
  BlockT *exit = getExit();
206
5.19k
  BlockT *exitingBlock = nullptr;
207
5.19k
208
5.19k
  if (!exit)
209
4
    return nullptr;
210
5.18k
211
5.18k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
212
6.98k
                                 InvBlockTraits::child_end(exit))) {
213
6.98k
    if (contains(Pred)) {
214
6.13k
      if (exitingBlock)
215
951
        return nullptr;
216
5.18k
217
5.18k
      exitingBlock = Pred;
218
5.18k
    }
219
6.98k
  }
220
5.18k
221
5.18k
  
return exitingBlock4.23k
;
222
5.18k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getExitingBlock() const
Line
Count
Source
204
5.19k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
205
5.19k
  BlockT *exit = getExit();
206
5.19k
  BlockT *exitingBlock = nullptr;
207
5.19k
208
5.19k
  if (!exit)
209
4
    return nullptr;
210
5.18k
211
5.18k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
212
6.98k
                                 InvBlockTraits::child_end(exit))) {
213
6.98k
    if (contains(Pred)) {
214
6.13k
      if (exitingBlock)
215
951
        return nullptr;
216
5.18k
217
5.18k
      exitingBlock = Pred;
218
5.18k
    }
219
6.98k
  }
220
5.18k
221
5.18k
  
return exitingBlock4.23k
;
222
5.18k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getExitingBlock() const
223
224
template <class Tr>
225
28.8k
bool RegionBase<Tr>::isSimple() const {
226
28.8k
  return !isTopLevelRegion() && 
getEnteringBlock()4.26k
&&
getExitingBlock()3.05k
;
227
28.8k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::isSimple() const
Line
Count
Source
225
28.8k
bool RegionBase<Tr>::isSimple() const {
226
28.8k
  return !isTopLevelRegion() && 
getEnteringBlock()4.26k
&&
getExitingBlock()3.05k
;
227
28.8k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::isSimple() const
228
229
template <class Tr>
230
3.68k
std::string RegionBase<Tr>::getNameStr() const {
231
3.68k
  std::string exitName;
232
3.68k
  std::string entryName;
233
3.68k
234
3.68k
  if (getEntry()->getName().empty()) {
235
20
    raw_string_ostream OS(entryName);
236
20
237
20
    getEntry()->printAsOperand(OS, false);
238
20
  } else
239
3.66k
    entryName = getEntry()->getName();
240
3.68k
241
3.68k
  if (getExit()) {
242
2.73k
    if (getExit()->getName().empty()) {
243
13
      raw_string_ostream OS(exitName);
244
13
245
13
      getExit()->printAsOperand(OS, false);
246
13
    } else
247
2.72k
      exitName = getExit()->getName();
248
2.73k
  } else
249
954
    exitName = "<Function Return>";
250
3.68k
251
3.68k
  return entryName + " => " + exitName;
252
3.68k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getNameStr() const
Line
Count
Source
230
3.68k
std::string RegionBase<Tr>::getNameStr() const {
231
3.68k
  std::string exitName;
232
3.68k
  std::string entryName;
233
3.68k
234
3.68k
  if (getEntry()->getName().empty()) {
235
20
    raw_string_ostream OS(entryName);
236
20
237
20
    getEntry()->printAsOperand(OS, false);
238
20
  } else
239
3.66k
    entryName = getEntry()->getName();
240
3.68k
241
3.68k
  if (getExit()) {
242
2.73k
    if (getExit()->getName().empty()) {
243
13
      raw_string_ostream OS(exitName);
244
13
245
13
      getExit()->printAsOperand(OS, false);
246
13
    } else
247
2.72k
      exitName = getExit()->getName();
248
2.73k
  } else
249
954
    exitName = "<Function Return>";
250
3.68k
251
3.68k
  return entryName + " => " + exitName;
252
3.68k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getNameStr() const
253
254
template <class Tr>
255
269
void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
256
269
  if (!contains(BB))
257
0
    report_fatal_error("Broken region found: enumerated BB not in region!");
258
269
259
269
  BlockT *entry = getEntry(), *exit = getExit();
260
269
261
269
  for (BlockT *Succ :
262
375
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
263
375
    if (!contains(Succ) && 
exit != Succ40
)
264
0
      report_fatal_error("Broken region found: edges leaving the region must go "
265
0
                         "to the exit node!");
266
375
  }
267
269
268
269
  if (entry != BB) {
269
219
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
270
308
                                   InvBlockTraits::child_end(BB))) {
271
308
      if (!contains(Pred))
272
1
        report_fatal_error("Broken region found: edges entering the region must "
273
1
                           "go to the entry node!");
274
308
    }
275
219
  }
276
269
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyBBInRegion(llvm::BasicBlock*) const
Line
Count
Source
255
269
void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
256
269
  if (!contains(BB))
257
0
    report_fatal_error("Broken region found: enumerated BB not in region!");
258
269
259
269
  BlockT *entry = getEntry(), *exit = getExit();
260
269
261
269
  for (BlockT *Succ :
262
375
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
263
375
    if (!contains(Succ) && 
exit != Succ40
)
264
0
      report_fatal_error("Broken region found: edges leaving the region must go "
265
0
                         "to the exit node!");
266
375
  }
267
269
268
269
  if (entry != BB) {
269
219
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
270
308
                                   InvBlockTraits::child_end(BB))) {
271
308
      if (!contains(Pred))
272
1
        report_fatal_error("Broken region found: edges entering the region must "
273
1
                           "go to the entry node!");
274
308
    }
275
219
  }
276
269
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyBBInRegion(llvm::MachineBasicBlock*) const
277
278
template <class Tr>
279
269
void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
280
269
  BlockT *exit = getExit();
281
269
282
269
  visited->insert(BB);
283
269
284
269
  verifyBBInRegion(BB);
285
269
286
269
  for (BlockT *Succ :
287
369
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
288
369
    if (Succ != exit && 
visited->find(Succ) == visited->end()329
)
289
219
      verifyWalk(Succ, visited);
290
369
  }
291
269
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyWalk(llvm::BasicBlock*, std::__1::set<llvm::BasicBlock*, std::__1::less<llvm::BasicBlock*>, std::__1::allocator<llvm::BasicBlock*> >*) const
Line
Count
Source
279
269
void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
280
269
  BlockT *exit = getExit();
281
269
282
269
  visited->insert(BB);
283
269
284
269
  verifyBBInRegion(BB);
285
269
286
269
  for (BlockT *Succ :
287
369
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
288
369
    if (Succ != exit && 
visited->find(Succ) == visited->end()329
)
289
219
      verifyWalk(Succ, visited);
290
369
  }
291
269
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyWalk(llvm::MachineBasicBlock*, std::__1::set<llvm::MachineBasicBlock*, std::__1::less<llvm::MachineBasicBlock*>, std::__1::allocator<llvm::MachineBasicBlock*> >*) const
292
293
template <class Tr>
294
38.5k
void RegionBase<Tr>::verifyRegion() const {
295
38.5k
  // Only do verification when user wants to, otherwise this expensive check
296
38.5k
  // will be invoked by PMDataManager::verifyPreservedAnalysis when
297
38.5k
  // a regionpass (marked PreservedAll) finish.
298
38.5k
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
299
38.4k
    return;
300
50
301
50
  std::set<BlockT *> visited;
302
50
  verifyWalk(getEntry(), &visited);
303
50
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyRegion() const
Line
Count
Source
294
38.5k
void RegionBase<Tr>::verifyRegion() const {
295
38.5k
  // Only do verification when user wants to, otherwise this expensive check
296
38.5k
  // will be invoked by PMDataManager::verifyPreservedAnalysis when
297
38.5k
  // a regionpass (marked PreservedAll) finish.
298
38.5k
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
299
38.4k
    return;
300
50
301
50
  std::set<BlockT *> visited;
302
50
  verifyWalk(getEntry(), &visited);
303
50
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyRegion() const
304
305
template <class Tr>
306
0
void RegionBase<Tr>::verifyRegionNest() const {
307
0
  for (const std::unique_ptr<RegionT> &R : *this)
308
0
    R->verifyRegionNest();
309
0
310
0
  verifyRegion();
311
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyRegionNest() const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyRegionNest() const
312
313
template <class Tr>
314
4.42k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
315
4.42k
  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
316
4.42k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_begin()
Line
Count
Source
314
4.42k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
315
4.42k
  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
316
4.42k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_begin()
317
318
template <class Tr>
319
4.42k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
320
4.42k
  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
321
4.42k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_end()
Line
Count
Source
319
4.42k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
320
4.42k
  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
321
4.42k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_end()
322
323
template <class Tr>
324
typename RegionBase<Tr>::const_element_iterator
325
4
RegionBase<Tr>::element_begin() const {
326
4
  return GraphTraits<const RegionT *>::nodes_begin(
327
4
      static_cast<const RegionT *>(this));
328
4
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_begin() const
Line
Count
Source
325
4
RegionBase<Tr>::element_begin() const {
326
4
  return GraphTraits<const RegionT *>::nodes_begin(
327
4
      static_cast<const RegionT *>(this));
328
4
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_begin() const
329
330
template <class Tr>
331
typename RegionBase<Tr>::const_element_iterator
332
4
RegionBase<Tr>::element_end() const {
333
4
  return GraphTraits<const RegionT *>::nodes_end(
334
4
      static_cast<const RegionT *>(this));
335
4
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_end() const
Line
Count
Source
332
4
RegionBase<Tr>::element_end() const {
333
4
  return GraphTraits<const RegionT *>::nodes_end(
334
4
      static_cast<const RegionT *>(this));
335
4
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_end() const
336
337
template <class Tr>
338
53.7k
typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
339
53.7k
  using RegionT = typename Tr::RegionT;
340
53.7k
341
53.7k
  RegionT *R = RI->getRegionFor(BB);
342
53.7k
343
53.7k
  if (!R || R == this)
344
45.2k
    return nullptr;
345
8.45k
346
8.45k
  // If we pass the BB out of this region, that means our code is broken.
347
8.45k
  assert(contains(R) && "BB not in current region!");
348
8.45k
349
8.69k
  while (contains(R->getParent()) && R->getParent() != this)
350
240
    R = R->getParent();
351
8.45k
352
8.45k
  if (R->getEntry() != BB)
353
0
    return nullptr;
354
8.45k
355
8.45k
  return R;
356
8.45k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getSubRegionNode(llvm::BasicBlock*) const
Line
Count
Source
338
53.7k
typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
339
53.7k
  using RegionT = typename Tr::RegionT;
340
53.7k
341
53.7k
  RegionT *R = RI->getRegionFor(BB);
342
53.7k
343
53.7k
  if (!R || R == this)
344
45.2k
    return nullptr;
345
8.45k
346
8.45k
  // If we pass the BB out of this region, that means our code is broken.
347
8.45k
  assert(contains(R) && "BB not in current region!");
348
8.45k
349
8.69k
  while (contains(R->getParent()) && R->getParent() != this)
350
240
    R = R->getParent();
351
8.45k
352
8.45k
  if (R->getEntry() != BB)
353
0
    return nullptr;
354
8.45k
355
8.45k
  return R;
356
8.45k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getSubRegionNode(llvm::MachineBasicBlock*) const
357
358
template <class Tr>
359
45.6k
typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
360
45.6k
  assert(contains(BB) && "Can get BB node out of this region!");
361
45.6k
362
45.6k
  typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
363
45.6k
364
45.6k
  if (at == BBNodeMap.end()) {
365
9.61k
    auto Deconst = const_cast<RegionBase<Tr> *>(this);
366
9.61k
    typename BBNodeMapT::value_type V = {
367
9.61k
        BB,
368
9.61k
        llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
369
9.61k
    at = BBNodeMap.insert(std::move(V)).first;
370
9.61k
  }
371
45.6k
  return at->second.get();
372
45.6k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getBBNode(llvm::BasicBlock*) const
Line
Count
Source
359
45.6k
typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
360
45.6k
  assert(contains(BB) && "Can get BB node out of this region!");
361
45.6k
362
45.6k
  typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
363
45.6k
364
45.6k
  if (at == BBNodeMap.end()) {
365
9.61k
    auto Deconst = const_cast<RegionBase<Tr> *>(this);
366
9.61k
    typename BBNodeMapT::value_type V = {
367
9.61k
        BB,
368
9.61k
        llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
369
9.61k
    at = BBNodeMap.insert(std::move(V)).first;
370
9.61k
  }
371
45.6k
  return at->second.get();
372
45.6k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getBBNode(llvm::MachineBasicBlock*) const
373
374
template <class Tr>
375
53.7k
typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
376
53.7k
  assert(contains(BB) && "Can get BB node out of this region!");
377
53.7k
  if (RegionT *Child = getSubRegionNode(BB))
378
8.45k
    return Child->getNode();
379
45.2k
380
45.2k
  return getBBNode(BB);
381
45.2k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getNode(llvm::BasicBlock*) const
Line
Count
Source
375
53.7k
typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
376
53.7k
  assert(contains(BB) && "Can get BB node out of this region!");
377
53.7k
  if (RegionT *Child = getSubRegionNode(BB))
378
8.45k
    return Child->getNode();
379
45.2k
380
45.2k
  return getBBNode(BB);
381
45.2k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getNode(llvm::MachineBasicBlock*) const
382
383
template <class Tr>
384
0
void RegionBase<Tr>::transferChildrenTo(RegionT *To) {
385
0
  for (std::unique_ptr<RegionT> &R : *this) {
386
0
    R->parent = To;
387
0
    To->children.push_back(std::move(R));
388
0
  }
389
0
  children.clear();
390
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::transferChildrenTo(llvm::Region*)
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::transferChildrenTo(llvm::MachineRegion*)
391
392
template <class Tr>
393
4.61k
void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
394
4.61k
  assert(!SubRegion->parent && "SubRegion already has a parent!");
395
4.61k
  assert(llvm::find_if(*this,
396
4.61k
                       [&](const std::unique_ptr<RegionT> &R) {
397
4.61k
                         return R.get() == SubRegion;
398
4.61k
                       }) == children.end() &&
399
4.61k
         "Subregion already exists!");
400
4.61k
401
4.61k
  SubRegion->parent = static_cast<RegionT *>(this);
402
4.61k
  children.push_back(std::unique_ptr<RegionT>(SubRegion));
403
4.61k
404
4.61k
  if (!moveChildren)
405
4.26k
    return;
406
350
407
350
  assert(SubRegion->children.empty() &&
408
350
         "SubRegions that contain children are not supported");
409
350
410
1.76k
  for (RegionNodeT *Element : elements()) {
411
1.76k
    if (!Element->isSubRegion()) {
412
1.18k
      BlockT *BB = Element->template getNodeAs<BlockT>();
413
1.18k
414
1.18k
      if (SubRegion->contains(BB))
415
397
        RI->setRegionFor(BB, SubRegion);
416
1.18k
    }
417
1.76k
  }
418
350
419
350
  std::vector<std::unique_ptr<RegionT>> Keep;
420
938
  for (std::unique_ptr<RegionT> &R : *this) {
421
938
    if (SubRegion->contains(R.get()) && 
R.get() != SubRegion909
) {
422
559
      R->parent = SubRegion;
423
559
      SubRegion->children.push_back(std::move(R));
424
559
    } else
425
379
      Keep.push_back(std::move(R));
426
938
  }
427
350
428
350
  children.clear();
429
350
  children.insert(
430
350
      children.begin(),
431
350
      std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
432
350
      std::move_iterator<typename RegionSet::iterator>(Keep.end()));
433
350
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::addSubRegion(llvm::Region*, bool)
Line
Count
Source
393
4.61k
void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
394
4.61k
  assert(!SubRegion->parent && "SubRegion already has a parent!");
395
4.61k
  assert(llvm::find_if(*this,
396
4.61k
                       [&](const std::unique_ptr<RegionT> &R) {
397
4.61k
                         return R.get() == SubRegion;
398
4.61k
                       }) == children.end() &&
399
4.61k
         "Subregion already exists!");
400
4.61k
401
4.61k
  SubRegion->parent = static_cast<RegionT *>(this);
402
4.61k
  children.push_back(std::unique_ptr<RegionT>(SubRegion));
403
4.61k
404
4.61k
  if (!moveChildren)
405
4.26k
    return;
406
350
407
350
  assert(SubRegion->children.empty() &&
408
350
         "SubRegions that contain children are not supported");
409
350
410
1.76k
  for (RegionNodeT *Element : elements()) {
411
1.76k
    if (!Element->isSubRegion()) {
412
1.18k
      BlockT *BB = Element->template getNodeAs<BlockT>();
413
1.18k
414
1.18k
      if (SubRegion->contains(BB))
415
397
        RI->setRegionFor(BB, SubRegion);
416
1.18k
    }
417
1.76k
  }
418
350
419
350
  std::vector<std::unique_ptr<RegionT>> Keep;
420
938
  for (std::unique_ptr<RegionT> &R : *this) {
421
938
    if (SubRegion->contains(R.get()) && 
R.get() != SubRegion909
) {
422
559
      R->parent = SubRegion;
423
559
      SubRegion->children.push_back(std::move(R));
424
559
    } else
425
379
      Keep.push_back(std::move(R));
426
938
  }
427
350
428
350
  children.clear();
429
350
  children.insert(
430
350
      children.begin(),
431
350
      std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
432
350
      std::move_iterator<typename RegionSet::iterator>(Keep.end()));
433
350
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::addSubRegion(llvm::MachineRegion*, bool)
434
435
template <class Tr>
436
0
typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
437
0
  assert(Child->parent == this && "Child is not a child of this region!");
438
0
  Child->parent = nullptr;
439
0
  typename RegionSet::iterator I =
440
0
      llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) {
441
0
        return R.get() == Child;
442
0
      });
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::removeSubRegion(llvm::Region*)::'lambda'(std::__1::unique_ptr<llvm::Region, std::__1::default_delete<llvm::Region> > const&)::operator()(std::__1::unique_ptr<llvm::Region, std::__1::default_delete<llvm::Region> > const&) const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::removeSubRegion(llvm::MachineRegion*)::'lambda'(std::__1::unique_ptr<llvm::MachineRegion, std::__1::default_delete<llvm::MachineRegion> > const&)::operator()(std::__1::unique_ptr<llvm::MachineRegion, std::__1::default_delete<llvm::MachineRegion> > const&) const
443
0
  assert(I != children.end() && "Region does not exit. Unable to remove.");
444
0
  children.erase(children.begin() + (I - begin()));
445
0
  return Child;
446
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::removeSubRegion(llvm::Region*)
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::removeSubRegion(llvm::MachineRegion*)
447
448
template <class Tr>
449
11
unsigned RegionBase<Tr>::getDepth() const {
450
11
  unsigned Depth = 0;
451
11
452
24
  for (RegionT *R = getParent(); R != nullptr; 
R = R->getParent()13
)
453
13
    ++Depth;
454
11
455
11
  return Depth;
456
11
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getDepth() const
Line
Count
Source
449
11
unsigned RegionBase<Tr>::getDepth() const {
450
11
  unsigned Depth = 0;
451
11
452
24
  for (RegionT *R = getParent(); R != nullptr; 
R = R->getParent()13
)
453
13
    ++Depth;
454
11
455
11
  return Depth;
456
11
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getDepth() const
457
458
template <class Tr>
459
1.88k
typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
460
1.88k
  unsigned NumSuccessors = Tr::getNumSuccessors(exit);
461
1.88k
462
1.88k
  if (NumSuccessors == 0)
463
1.13k
    return nullptr;
464
747
465
747
  RegionT *R = RI->getRegionFor(exit);
466
747
467
747
  if (R->getEntry() != exit) {
468
476
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
469
476
                                   InvBlockTraits::child_end(getExit())))
470
582
      if (!contains(Pred))
471
19
        return nullptr;
472
476
    
if (457
Tr::getNumSuccessors(exit) == 1457
)
473
413
      return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
474
44
    return nullptr;
475
44
  }
476
271
477
277
  
while (271
R->getParent() && R->getParent()->getEntry() == exit)
478
6
    R = R->getParent();
479
271
480
271
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
481
531
                                 InvBlockTraits::child_end(getExit()))) {
482
531
    if (!(contains(Pred) || 
R->contains(Pred)176
))
483
31
      return nullptr;
484
531
  }
485
271
486
271
  
return new RegionT(getEntry(), R->getExit(), RI, DT)240
;
487
271
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getExpandedRegion() const
Line
Count
Source
459
1.88k
typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
460
1.88k
  unsigned NumSuccessors = Tr::getNumSuccessors(exit);
461
1.88k
462
1.88k
  if (NumSuccessors == 0)
463
1.13k
    return nullptr;
464
747
465
747
  RegionT *R = RI->getRegionFor(exit);
466
747
467
747
  if (R->getEntry() != exit) {
468
476
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
469
476
                                   InvBlockTraits::child_end(getExit())))
470
582
      if (!contains(Pred))
471
19
        return nullptr;
472
476
    
if (457
Tr::getNumSuccessors(exit) == 1457
)
473
413
      return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
474
44
    return nullptr;
475
44
  }
476
271
477
277
  
while (271
R->getParent() && R->getParent()->getEntry() == exit)
478
6
    R = R->getParent();
479
271
480
271
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
481
531
                                 InvBlockTraits::child_end(getExit()))) {
482
531
    if (!(contains(Pred) || 
R->contains(Pred)176
))
483
31
      return nullptr;
484
531
  }
485
271
486
271
  
return new RegionT(getEntry(), R->getExit(), RI, DT)240
;
487
271
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getExpandedRegion() const
488
489
template <class Tr>
490
void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
491
19
                           PrintStyle Style) const {
492
19
  if (print_tree)
493
19
    OS.indent(level * 2) << '[' << level << "] " << getNameStr();
494
0
  else
495
0
    OS.indent(level * 2) << getNameStr();
496
19
497
19
  OS << '\n';
498
19
499
19
  if (Style != PrintNone) {
500
8
    OS.indent(level * 2) << "{\n";
501
8
    OS.indent(level * 2 + 2);
502
8
503
8
    if (Style == PrintBB) {
504
4
      for (const auto *BB : blocks())
505
10
        OS << BB->getName() << ", "; // TODO: remove the last ","
506
4
    } else if (Style == PrintRN) {
507
8
      for (const RegionNodeT *Element : elements()) {
508
8
        OS << *Element << ", "; // TODO: remove the last ",
509
8
      }
510
4
    }
511
8
512
8
    OS << '\n';
513
8
  }
514
19
515
19
  if (print_tree) {
516
19
    for (const std::unique_ptr<RegionT> &R : *this)
517
9
      R->print(OS, print_tree, level + 1, Style);
518
19
  }
519
19
520
19
  if (Style != PrintNone)
521
8
    OS.indent(level * 2) << "} \n";
522
19
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::print(llvm::raw_ostream&, bool, unsigned int, llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::PrintStyle) const
Line
Count
Source
491
19
                           PrintStyle Style) const {
492
19
  if (print_tree)
493
19
    OS.indent(level * 2) << '[' << level << "] " << getNameStr();
494
0
  else
495
0
    OS.indent(level * 2) << getNameStr();
496
19
497
19
  OS << '\n';
498
19
499
19
  if (Style != PrintNone) {
500
8
    OS.indent(level * 2) << "{\n";
501
8
    OS.indent(level * 2 + 2);
502
8
503
8
    if (Style == PrintBB) {
504
4
      for (const auto *BB : blocks())
505
10
        OS << BB->getName() << ", "; // TODO: remove the last ","
506
4
    } else if (Style == PrintRN) {
507
8
      for (const RegionNodeT *Element : elements()) {
508
8
        OS << *Element << ", "; // TODO: remove the last ",
509
8
      }
510
4
    }
511
8
512
8
    OS << '\n';
513
8
  }
514
19
515
19
  if (print_tree) {
516
19
    for (const std::unique_ptr<RegionT> &R : *this)
517
9
      R->print(OS, print_tree, level + 1, Style);
518
19
  }
519
19
520
19
  if (Style != PrintNone)
521
8
    OS.indent(level * 2) << "} \n";
522
19
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::print(llvm::raw_ostream&, bool, unsigned int, llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::PrintStyle) const
523
524
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
525
template <class Tr>
526
void RegionBase<Tr>::dump() const {
527
  print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
528
}
529
#endif
530
531
template <class Tr>
532
50.0k
void RegionBase<Tr>::clearNodeCache() {
533
50.0k
  BBNodeMap.clear();
534
50.0k
  for (std::unique_ptr<RegionT> &R : *this)
535
21.5k
    R->clearNodeCache();
536
50.0k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::clearNodeCache()
Line
Count
Source
532
50.0k
void RegionBase<Tr>::clearNodeCache() {
533
50.0k
  BBNodeMap.clear();
534
50.0k
  for (std::unique_ptr<RegionT> &R : *this)
535
21.5k
    R->clearNodeCache();
536
50.0k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::clearNodeCache()
537
538
//===----------------------------------------------------------------------===//
539
// RegionInfoBase implementation
540
//
541
542
template <class Tr>
543
RegionInfoBase<Tr>::RegionInfoBase() = default;
544
545
template <class Tr>
546
3.73k
RegionInfoBase<Tr>::~RegionInfoBase() {
547
3.73k
  releaseMemory();
548
3.73k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::~RegionInfoBase()
Line
Count
Source
546
3.73k
RegionInfoBase<Tr>::~RegionInfoBase() {
547
3.73k
  releaseMemory();
548
3.73k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::~RegionInfoBase()
549
550
template <class Tr>
551
0
void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
552
0
  assert(R && "Re must be non-null");
553
0
  for (const typename Tr::RegionNodeT *Element : R->elements()) {
554
0
    if (Element->isSubRegion()) {
555
0
      const RegionT *SR = Element->template getNodeAs<RegionT>();
556
0
      verifyBBMap(SR);
557
0
    } else {
558
0
      BlockT *BB = Element->template getNodeAs<BlockT>();
559
0
      if (getRegionFor(BB) != R)
560
0
        report_fatal_error("BB map does not match region nesting");
561
0
    }
562
0
  }
563
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::verifyBBMap(llvm::Region const*) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyBBMap(llvm::MachineRegion const*) const
564
565
template <class Tr>
566
bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
567
3.63k
                                             BlockT *exit) const {
568
3.63k
  for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
569
7.39k
                              InvBlockTraits::child_end(BB))) {
570
7.39k
    if (DT->dominates(entry, P) && 
!DT->dominates(exit, P)3.68k
)
571
2
      return false;
572
7.39k
  }
573
3.63k
574
3.63k
  
return true3.62k
;
575
3.63k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isCommonDomFrontier(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
567
3.63k
                                             BlockT *exit) const {
568
3.63k
  for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
569
7.39k
                              InvBlockTraits::child_end(BB))) {
570
7.39k
    if (DT->dominates(entry, P) && 
!DT->dominates(exit, P)3.68k
)
571
2
      return false;
572
7.39k
  }
573
3.63k
574
3.63k
  
return true3.62k
;
575
3.63k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::isCommonDomFrontier(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
576
577
template <class Tr>
578
15.5k
bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
579
15.5k
  assert(entry && exit && "entry and exit must not be null!");
580
15.5k
581
15.5k
  using DST = typename DomFrontierT::DomSetType;
582
15.5k
583
15.5k
  DST *entrySuccs = &DF->find(entry)->second;
584
15.5k
585
15.5k
  // Exit is the header of a loop that contains the entry. In this case,
586
15.5k
  // the dominance frontier must only contain the exit.
587
15.5k
  if (!DT->dominates(entry, exit)) {
588
6.25k
    for (typename DST::iterator SI = entrySuccs->begin(),
589
6.25k
                                SE = entrySuccs->end();
590
10.1k
         SI != SE; 
++SI3.90k
) {
591
6.64k
      if (*SI != exit && 
*SI != entry3.00k
)
592
2.73k
        return false;
593
6.64k
    }
594
6.25k
595
6.25k
    
return true3.52k
;
596
9.26k
  }
597
9.26k
598
9.26k
  DST *exitSuccs = &DF->find(exit)->second;
599
9.26k
600
9.26k
  // Do not allow edges leaving the region.
601
9.26k
  for (BlockT *Succ : *entrySuccs) {
602
7.26k
    if (Succ == exit || Succ == entry)
603
2.73k
      continue;
604
4.53k
    if (exitSuccs->find(Succ) == exitSuccs->end())
605
909
      return false;
606
3.63k
    if (!isCommonDomFrontier(Succ, entry, exit))
607
2
      return false;
608
3.63k
  }
609
9.26k
610
9.26k
  // Do not allow edges pointing into the region.
611
9.26k
  
for (BlockT *Succ : *exitSuccs)8.35k
{
612
6.19k
    if (DT->properlyDominates(entry, Succ) && 
Succ != exit2.32k
)
613
12
      return false;
614
6.19k
  }
615
8.35k
616
8.35k
  
return true8.34k
;
617
8.35k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isRegion(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
578
15.5k
bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
579
15.5k
  assert(entry && exit && "entry and exit must not be null!");
580
15.5k
581
15.5k
  using DST = typename DomFrontierT::DomSetType;
582
15.5k
583
15.5k
  DST *entrySuccs = &DF->find(entry)->second;
584
15.5k
585
15.5k
  // Exit is the header of a loop that contains the entry. In this case,
586
15.5k
  // the dominance frontier must only contain the exit.
587
15.5k
  if (!DT->dominates(entry, exit)) {
588
6.25k
    for (typename DST::iterator SI = entrySuccs->begin(),
589
6.25k
                                SE = entrySuccs->end();
590
10.1k
         SI != SE; 
++SI3.90k
) {
591
6.64k
      if (*SI != exit && 
*SI != entry3.00k
)
592
2.73k
        return false;
593
6.64k
    }
594
6.25k
595
6.25k
    
return true3.52k
;
596
9.26k
  }
597
9.26k
598
9.26k
  DST *exitSuccs = &DF->find(exit)->second;
599
9.26k
600
9.26k
  // Do not allow edges leaving the region.
601
9.26k
  for (BlockT *Succ : *entrySuccs) {
602
7.26k
    if (Succ == exit || Succ == entry)
603
2.73k
      continue;
604
4.53k
    if (exitSuccs->find(Succ) == exitSuccs->end())
605
909
      return false;
606
3.63k
    if (!isCommonDomFrontier(Succ, entry, exit))
607
2
      return false;
608
3.63k
  }
609
9.26k
610
9.26k
  // Do not allow edges pointing into the region.
611
9.26k
  
for (BlockT *Succ : *exitSuccs)8.35k
{
612
6.19k
    if (DT->properlyDominates(entry, Succ) && 
Succ != exit2.32k
)
613
12
      return false;
614
6.19k
  }
615
8.35k
616
8.35k
  
return true8.34k
;
617
8.35k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::isRegion(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
618
619
template <class Tr>
620
void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
621
11.3k
                                        BBtoBBMap *ShortCut) const {
622
11.3k
  assert(entry && exit && "entry and exit must not be null!");
623
11.3k
624
11.3k
  typename BBtoBBMap::iterator e = ShortCut->find(exit);
625
11.3k
626
11.3k
  if (e == ShortCut->end())
627
5.89k
    // No further region at exit available.
628
5.89k
    (*ShortCut)[entry] = exit;
629
5.46k
  else {
630
5.46k
    // We found a region e that starts at exit. Therefore (entry, e->second)
631
5.46k
    // is also a region, that is larger than (entry, exit). Insert the
632
5.46k
    // larger one.
633
5.46k
    BlockT *BB = e->second;
634
5.46k
    (*ShortCut)[entry] = BB;
635
5.46k
  }
636
11.3k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::insertShortCut(llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMap<llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::BasicBlock*> >*) const
Line
Count
Source
621
11.3k
                                        BBtoBBMap *ShortCut) const {
622
11.3k
  assert(entry && exit && "entry and exit must not be null!");
623
11.3k
624
11.3k
  typename BBtoBBMap::iterator e = ShortCut->find(exit);
625
11.3k
626
11.3k
  if (e == ShortCut->end())
627
5.89k
    // No further region at exit available.
628
5.89k
    (*ShortCut)[entry] = exit;
629
5.46k
  else {
630
5.46k
    // We found a region e that starts at exit. Therefore (entry, e->second)
631
5.46k
    // is also a region, that is larger than (entry, exit). Insert the
632
5.46k
    // larger one.
633
5.46k
    BlockT *BB = e->second;
634
5.46k
    (*ShortCut)[entry] = BB;
635
5.46k
  }
636
11.3k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::insertShortCut(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::DenseMap<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::DenseMapInfo<llvm::MachineBasicBlock*>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*> >*) const
637
638
template <class Tr>
639
typename Tr::DomTreeNodeT *
640
46.3k
RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
641
46.3k
  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
642
46.3k
643
46.3k
  if (e == ShortCut->end())
644
40.7k
    return N->getIDom();
645
5.59k
646
5.59k
  return PDT->getNode(e->second)->getIDom();
647
5.59k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getNextPostDom(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::DenseMap<llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::BasicBlock*> >*) const
Line
Count
Source
640
46.3k
RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
641
46.3k
  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
642
46.3k
643
46.3k
  if (e == ShortCut->end())
644
40.7k
    return N->getIDom();
645
5.59k
646
5.59k
  return PDT->getNode(e->second)->getIDom();
647
5.59k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getNextPostDom(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*, llvm::DenseMap<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::DenseMapInfo<llvm::MachineBasicBlock*>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*> >*) const
648
649
template <class Tr>
650
11.8k
bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
651
11.8k
  assert(entry && exit && "entry and exit must not be null!");
652
11.8k
653
11.8k
  unsigned num_successors =
654
11.8k
      BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
655
11.8k
656
11.8k
  if (num_successors <= 1 && 
exit == *(BlockTraits::child_begin(entry))7.96k
)
657
7.60k
    return true;
658
4.26k
659
4.26k
  return false;
660
4.26k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isTrivialRegion(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
650
11.8k
bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
651
11.8k
  assert(entry && exit && "entry and exit must not be null!");
652
11.8k
653
11.8k
  unsigned num_successors =
654
11.8k
      BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
655
11.8k
656
11.8k
  if (num_successors <= 1 && 
exit == *(BlockTraits::child_begin(entry))7.96k
)
657
7.60k
    return true;
658
4.26k
659
4.26k
  return false;
660
4.26k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::isTrivialRegion(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
661
662
template <class Tr>
663
typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
664
11.8k
                                                       BlockT *exit) {
665
11.8k
  assert(entry && exit && "entry and exit must not be null!");
666
11.8k
667
11.8k
  if (isTrivialRegion(entry, exit))
668
7.60k
    return nullptr;
669
4.26k
670
4.26k
  RegionT *region =
671
4.26k
      new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
672
4.26k
  BBtoRegion.insert({entry, region});
673
4.26k
674
4.26k
#ifdef EXPENSIVE_CHECKS
675
4.26k
  region->verifyRegion();
676
4.26k
#else
677
4.26k
  LLVM_DEBUG(region->verifyRegion());
678
4.26k
#endif
679
4.26k
680
4.26k
  updateStatistics(region);
681
4.26k
  return region;
682
4.26k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::createRegion(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
664
11.8k
                                                       BlockT *exit) {
665
11.8k
  assert(entry && exit && "entry and exit must not be null!");
666
11.8k
667
11.8k
  if (isTrivialRegion(entry, exit))
668
7.60k
    return nullptr;
669
4.26k
670
4.26k
  RegionT *region =
671
4.26k
      new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
672
4.26k
  BBtoRegion.insert({entry, region});
673
4.26k
674
4.26k
#ifdef EXPENSIVE_CHECKS
675
4.26k
  region->verifyRegion();
676
4.26k
#else
677
4.26k
  LLVM_DEBUG(region->verifyRegion());
678
4.26k
#endif
679
4.26k
680
4.26k
  updateStatistics(region);
681
4.26k
  return region;
682
4.26k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::createRegion(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*)
683
684
template <class Tr>
685
void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
686
37.0k
                                              BBtoBBMap *ShortCut) {
687
37.0k
  assert(entry);
688
37.0k
689
37.0k
  DomTreeNodeT *N = PDT->getNode(entry);
690
37.0k
  if (!N)
691
0
    return;
692
37.0k
693
37.0k
  RegionT *lastRegion = nullptr;
694
37.0k
  BlockT *lastExit = entry;
695
37.0k
696
37.0k
  // As only a BasicBlock that postdominates entry can finish a region, walk the
697
37.0k
  // post dominance tree upwards.
698
46.3k
  while ((N = getNextPostDom(N, ShortCut))) {
699
46.3k
    BlockT *exit = N->getBlock();
700
46.3k
701
46.3k
    if (!exit)
702
30.7k
      break;
703
15.5k
704
15.5k
    if (isRegion(entry, exit)) {
705
11.8k
      RegionT *newRegion = createRegion(entry, exit);
706
11.8k
707
11.8k
      if (lastRegion)
708
142
        newRegion->addSubRegion(lastRegion);
709
11.8k
710
11.8k
      lastRegion = newRegion;
711
11.8k
      lastExit = exit;
712
11.8k
    }
713
15.5k
714
15.5k
    // This can never be a region, so stop the search.
715
15.5k
    if (!DT->dominates(entry, exit))
716
6.25k
      break;
717
15.5k
  }
718
37.0k
719
37.0k
  // Tried to create regions from entry to lastExit.  Next time take a
720
37.0k
  // shortcut from entry to lastExit.
721
37.0k
  if (lastExit != entry)
722
11.3k
    insertShortCut(entry, lastExit, ShortCut);
723
37.0k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::findRegionsWithEntry(llvm::BasicBlock*, llvm::DenseMap<llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::BasicBlock*> >*)
Line
Count
Source
686
37.0k
                                              BBtoBBMap *ShortCut) {
687
37.0k
  assert(entry);
688
37.0k
689
37.0k
  DomTreeNodeT *N = PDT->getNode(entry);
690
37.0k
  if (!N)
691
0
    return;
692
37.0k
693
37.0k
  RegionT *lastRegion = nullptr;
694
37.0k
  BlockT *lastExit = entry;
695
37.0k
696
37.0k
  // As only a BasicBlock that postdominates entry can finish a region, walk the
697
37.0k
  // post dominance tree upwards.
698
46.3k
  while ((N = getNextPostDom(N, ShortCut))) {
699
46.3k
    BlockT *exit = N->getBlock();
700
46.3k
701
46.3k
    if (!exit)
702
30.7k
      break;
703
15.5k
704
15.5k
    if (isRegion(entry, exit)) {
705
11.8k
      RegionT *newRegion = createRegion(entry, exit);
706
11.8k
707
11.8k
      if (lastRegion)
708
142
        newRegion->addSubRegion(lastRegion);
709
11.8k
710
11.8k
      lastRegion = newRegion;
711
11.8k
      lastExit = exit;
712
11.8k
    }
713
15.5k
714
15.5k
    // This can never be a region, so stop the search.
715
15.5k
    if (!DT->dominates(entry, exit))
716
6.25k
      break;
717
15.5k
  }
718
37.0k
719
37.0k
  // Tried to create regions from entry to lastExit.  Next time take a
720
37.0k
  // shortcut from entry to lastExit.
721
37.0k
  if (lastExit != entry)
722
11.3k
    insertShortCut(entry, lastExit, ShortCut);
723
37.0k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::findRegionsWithEntry(llvm::MachineBasicBlock*, llvm::DenseMap<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::DenseMapInfo<llvm::MachineBasicBlock*>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*> >*)
724
725
template <class Tr>
726
24.6k
void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
727
24.6k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
728
24.6k
729
24.6k
  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
730
24.6k
  DomTreeNodeT *N = DT->getNode(entry);
731
24.6k
732
24.6k
  // Iterate over the dominance tree in post order to start with the small
733
24.6k
  // regions from the bottom of the dominance tree.  If the small regions are
734
24.6k
  // detected first, detection of bigger regions is faster, as we can jump
735
24.6k
  // over the small regions.
736
24.6k
  for (auto DomNode : post_order(N))
737
37.0k
    findRegionsWithEntry(DomNode->getBlock(), ShortCut);
738
24.6k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::scanForRegions(llvm::Function&, llvm::DenseMap<llvm::BasicBlock*, llvm::BasicBlock*, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::BasicBlock*> >*)
Line
Count
Source
726
24.6k
void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
727
24.6k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
728
24.6k
729
24.6k
  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
730
24.6k
  DomTreeNodeT *N = DT->getNode(entry);
731
24.6k
732
24.6k
  // Iterate over the dominance tree in post order to start with the small
733
24.6k
  // regions from the bottom of the dominance tree.  If the small regions are
734
24.6k
  // detected first, detection of bigger regions is faster, as we can jump
735
24.6k
  // over the small regions.
736
24.6k
  for (auto DomNode : post_order(N))
737
37.0k
    findRegionsWithEntry(DomNode->getBlock(), ShortCut);
738
24.6k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::scanForRegions(llvm::MachineFunction&, llvm::DenseMap<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::DenseMapInfo<llvm::MachineBasicBlock*>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock*, llvm::MachineBasicBlock*> >*)
739
740
template <class Tr>
741
4.11k
typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
742
4.26k
  while (region->getParent())
743
142
    region = region->getParent();
744
4.11k
745
4.11k
  return region;
746
4.11k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getTopMostParent(llvm::Region*)
Line
Count
Source
741
4.11k
typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
742
4.26k
  while (region->getParent())
743
142
    region = region->getParent();
744
4.11k
745
4.11k
  return region;
746
4.11k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getTopMostParent(llvm::MachineRegion*)
747
748
template <class Tr>
749
37.0k
void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
750
37.0k
  BlockT *BB = N->getBlock();
751
37.0k
752
37.0k
  // Passed region exit
753
40.9k
  while (BB == region->getExit())
754
3.86k
    region = region->getParent();
755
37.0k
756
37.0k
  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
757
37.0k
758
37.0k
  // This basic block is a start block of a region. It is already in the
759
37.0k
  // BBtoRegion relation. Only the child basic blocks have to be updated.
760
37.0k
  if (it != BBtoRegion.end()) {
761
4.11k
    RegionT *newRegion = it->second;
762
4.11k
    region->addSubRegion(getTopMostParent(newRegion));
763
4.11k
    region = newRegion;
764
32.9k
  } else {
765
32.9k
    BBtoRegion[BB] = region;
766
32.9k
  }
767
37.0k
768
37.0k
  for (DomTreeNodeBase<BlockT> *C : *N) {
769
12.4k
    buildRegionsTree(C, region);
770
12.4k
  }
771
37.0k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::buildRegionsTree(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::Region*)
Line
Count
Source
749
37.0k
void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
750
37.0k
  BlockT *BB = N->getBlock();
751
37.0k
752
37.0k
  // Passed region exit
753
40.9k
  while (BB == region->getExit())
754
3.86k
    region = region->getParent();
755
37.0k
756
37.0k
  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
757
37.0k
758
37.0k
  // This basic block is a start block of a region. It is already in the
759
37.0k
  // BBtoRegion relation. Only the child basic blocks have to be updated.
760
37.0k
  if (it != BBtoRegion.end()) {
761
4.11k
    RegionT *newRegion = it->second;
762
4.11k
    region->addSubRegion(getTopMostParent(newRegion));
763
4.11k
    region = newRegion;
764
32.9k
  } else {
765
32.9k
    BBtoRegion[BB] = region;
766
32.9k
  }
767
37.0k
768
37.0k
  for (DomTreeNodeBase<BlockT> *C : *N) {
769
12.4k
    buildRegionsTree(C, region);
770
12.4k
  }
771
37.0k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::buildRegionsTree(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*, llvm::MachineRegion*)
772
773
#ifdef EXPENSIVE_CHECKS
774
template <class Tr>
775
bool RegionInfoBase<Tr>::VerifyRegionInfo = true;
776
#else
777
template <class Tr>
778
bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
779
#endif
780
781
template <class Tr>
782
typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
783
    RegionBase<Tr>::PrintNone;
784
785
template <class Tr>
786
10
void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
787
10
  OS << "Region tree:\n";
788
10
  TopLevelRegion->print(OS, true, 0, printStyle);
789
10
  OS << "End region tree\n";
790
10
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::print(llvm::raw_ostream&) const
Line
Count
Source
786
10
void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
787
10
  OS << "Region tree:\n";
788
10
  TopLevelRegion->print(OS, true, 0, printStyle);
789
10
  OS << "End region tree\n";
790
10
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::print(llvm::raw_ostream&) const
791
792
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
793
template <class Tr>
794
void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
795
#endif
796
797
template <class Tr>
798
52.9k
void RegionInfoBase<Tr>::releaseMemory() {
799
52.9k
  BBtoRegion.clear();
800
52.9k
  if (TopLevelRegion)
801
24.6k
    delete TopLevelRegion;
802
52.9k
  TopLevelRegion = nullptr;
803
52.9k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::releaseMemory()
Line
Count
Source
798
52.9k
void RegionInfoBase<Tr>::releaseMemory() {
799
52.9k
  BBtoRegion.clear();
800
52.9k
  if (TopLevelRegion)
801
24.6k
    delete TopLevelRegion;
802
52.9k
  TopLevelRegion = nullptr;
803
52.9k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::releaseMemory()
804
805
template <class Tr>
806
0
void RegionInfoBase<Tr>::verifyAnalysis() const {
807
0
  // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
808
0
  // -verify-region-info
809
0
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
810
0
    return;
811
0
812
0
  TopLevelRegion->verifyRegionNest();
813
0
814
0
  verifyBBMap(TopLevelRegion);
815
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::verifyAnalysis() const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyAnalysis() const
816
817
// Region pass manager support.
818
template <class Tr>
819
74.6k
typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
820
74.6k
  typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
821
74.6k
  return I != BBtoRegion.end() ? 
I->second72.7k
:
nullptr1.87k
;
822
74.6k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getRegionFor(llvm::BasicBlock*) const
Line
Count
Source
819
74.6k
typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
820
74.6k
  typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
821
74.6k
  return I != BBtoRegion.end() ? 
I->second72.7k
:
nullptr1.87k
;
822
74.6k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getRegionFor(llvm::MachineBasicBlock*) const
823
824
template <class Tr>
825
4.69k
void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
826
4.69k
  BBtoRegion[BB] = R;
827
4.69k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::setRegionFor(llvm::BasicBlock*, llvm::Region*)
Line
Count
Source
825
4.69k
void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
826
4.69k
  BBtoRegion[BB] = R;
827
4.69k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::setRegionFor(llvm::MachineBasicBlock*, llvm::MachineRegion*)
828
829
template <class Tr>
830
0
typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
831
0
  return getRegionFor(BB);
832
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::operator[](llvm::BasicBlock*) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::operator[](llvm::MachineBasicBlock*) const
833
834
template <class Tr>
835
typename RegionInfoBase<Tr>::BlockT *
836
0
RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const {
837
0
  BlockT *Exit = nullptr;
838
0
839
0
  while (true) {
840
0
    // Get largest region that starts at BB.
841
0
    RegionT *R = getRegionFor(BB);
842
0
    while (R && R->getParent() && R->getParent()->getEntry() == BB)
843
0
      R = R->getParent();
844
0
845
0
    // Get the single exit of BB.
846
0
    if (R && R->getEntry() == BB)
847
0
      Exit = R->getExit();
848
0
    else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
849
0
      Exit = *BlockTraits::child_begin(BB);
850
0
    else // No single exit exists.
851
0
      return Exit;
852
0
853
0
    // Get largest region that starts at Exit.
854
0
    RegionT *ExitR = getRegionFor(Exit);
855
0
    while (ExitR && ExitR->getParent() &&
856
0
           ExitR->getParent()->getEntry() == Exit)
857
0
      ExitR = ExitR->getParent();
858
0
859
0
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
860
0
                                   InvBlockTraits::child_end(Exit))) {
861
0
      if (!R->contains(Pred) && !ExitR->contains(Pred))
862
0
        break;
863
0
    }
864
0
865
0
    // This stops infinite cycles.
866
0
    if (DT->dominates(Exit, BB))
867
0
      break;
868
0
869
0
    BB = Exit;
870
0
  }
871
0
872
0
  return Exit;
873
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getMaxRegionExit(llvm::BasicBlock*) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getMaxRegionExit(llvm::MachineBasicBlock*) const
874
875
template <class Tr>
876
typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
877
0
                                                          RegionT *B) const {
878
0
  assert(A && B && "One of the Regions is NULL");
879
0
880
0
  if (A->contains(B))
881
0
    return A;
882
0
883
0
  while (!B->contains(A))
884
0
    B = B->getParent();
885
0
886
0
  return B;
887
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getCommonRegion(llvm::Region*, llvm::Region*) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getCommonRegion(llvm::MachineRegion*, llvm::MachineRegion*) const
888
889
template <class Tr>
890
typename Tr::RegionT *
891
0
RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const {
892
0
  RegionT *ret = Regions.back();
893
0
  Regions.pop_back();
894
0
895
0
  for (RegionT *R : Regions)
896
0
    ret = getCommonRegion(ret, R);
897
0
898
0
  return ret;
899
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getCommonRegion(llvm::SmallVectorImpl<llvm::Region*>&) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getCommonRegion(llvm::SmallVectorImpl<llvm::MachineRegion*>&) const
900
901
template <class Tr>
902
typename Tr::RegionT *
903
0
RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const {
904
0
  RegionT *ret = getRegionFor(BBs.back());
905
0
  BBs.pop_back();
906
0
907
0
  for (BlockT *BB : BBs)
908
0
    ret = getCommonRegion(ret, getRegionFor(BB));
909
0
910
0
  return ret;
911
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getCommonRegion(llvm::SmallVectorImpl<llvm::BasicBlock*>&) const
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getCommonRegion(llvm::SmallVectorImpl<llvm::MachineBasicBlock*>&) const
912
913
template <class Tr>
914
24.6k
void RegionInfoBase<Tr>::calculate(FuncT &F) {
915
24.6k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
916
24.6k
917
24.6k
  // ShortCut a function where for every BB the exit of the largest region
918
24.6k
  // starting with BB is stored. These regions can be threated as single BBS.
919
24.6k
  // This improves performance on linear CFGs.
920
24.6k
  BBtoBBMap ShortCut;
921
24.6k
922
24.6k
  scanForRegions(F, &ShortCut);
923
24.6k
  BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
924
24.6k
  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
925
24.6k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::calculate(llvm::Function&)
Line
Count
Source
914
24.6k
void RegionInfoBase<Tr>::calculate(FuncT &F) {
915
24.6k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
916
24.6k
917
24.6k
  // ShortCut a function where for every BB the exit of the largest region
918
24.6k
  // starting with BB is stored. These regions can be threated as single BBS.
919
24.6k
  // This improves performance on linear CFGs.
920
24.6k
  BBtoBBMap ShortCut;
921
24.6k
922
24.6k
  scanForRegions(F, &ShortCut);
923
24.6k
  BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
924
24.6k
  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
925
24.6k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::calculate(llvm::MachineFunction&)
926
927
} // end namespace llvm
928
929
#undef DEBUG_TYPE
930
931
#endif // LLVM_ANALYSIS_REGIONINFOIMPL_H