Coverage Report

Created: 2018-11-16 02:38

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