Coverage Report

Created: 2018-09-19 20:53

/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
5.00k
    : 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
5.00k
    : 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
4.92k
RegionBase<Tr>::~RegionBase() {
52
4.92k
  // Only clean the cache for this Region. Caches of child Regions will be
53
4.92k
  // cleaned when the child Regions are deleted.
54
4.92k
  BBNodeMap.clear();
55
4.92k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::~RegionBase()
Line
Count
Source
51
4.92k
RegionBase<Tr>::~RegionBase() {
52
4.92k
  // Only clean the cache for this Region. Caches of child Regions will be
53
4.92k
  // cleaned when the child Regions are deleted.
54
4.92k
  BBNodeMap.clear();
55
4.92k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::~RegionBase()
56
57
template <class Tr>
58
5
void RegionBase<Tr>::replaceEntry(BlockT *BB) {
59
5
  this->entry.setPointer(BB);
60
5
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceEntry(llvm::BasicBlock*)
Line
Count
Source
58
5
void RegionBase<Tr>::replaceEntry(BlockT *BB) {
59
5
  this->entry.setPointer(BB);
60
5
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceEntry(llvm::MachineBasicBlock*)
61
62
template <class Tr>
63
445
void RegionBase<Tr>::replaceExit(BlockT *BB) {
64
445
  assert(exit && "No exit to replace!");
65
445
  exit = BB;
66
445
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceExit(llvm::BasicBlock*)
Line
Count
Source
63
445
void RegionBase<Tr>::replaceExit(BlockT *BB) {
64
445
  assert(exit && "No exit to replace!");
65
445
  exit = BB;
66
445
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceExit(llvm::MachineBasicBlock*)
67
68
template <class Tr>
69
0
void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) {
70
0
  std::vector<RegionT *> RegionQueue;
71
0
  BlockT *OldEntry = getEntry();
72
0
73
0
  RegionQueue.push_back(static_cast<RegionT *>(this));
74
0
  while (!RegionQueue.empty()) {
75
0
    RegionT *R = RegionQueue.back();
76
0
    RegionQueue.pop_back();
77
0
78
0
    R->replaceEntry(NewEntry);
79
0
    for (std::unique_ptr<RegionT> &Child : *R) {
80
0
      if (Child->getEntry() == OldEntry)
81
0
        RegionQueue.push_back(Child.get());
82
0
    }
83
0
  }
84
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceEntryRecursive(llvm::BasicBlock*)
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceEntryRecursive(llvm::MachineBasicBlock*)
85
86
template <class Tr>
87
351
void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
88
351
  std::vector<RegionT *> RegionQueue;
89
351
  BlockT *OldExit = getExit();
90
351
91
351
  RegionQueue.push_back(static_cast<RegionT *>(this));
92
733
  while (!RegionQueue.empty()) {
93
382
    RegionT *R = RegionQueue.back();
94
382
    RegionQueue.pop_back();
95
382
96
382
    R->replaceExit(NewExit);
97
382
    for (std::unique_ptr<RegionT> &Child : *R) {
98
207
      if (Child->getExit() == OldExit)
99
31
        RegionQueue.push_back(Child.get());
100
207
    }
101
382
  }
102
351
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::replaceExitRecursive(llvm::BasicBlock*)
Line
Count
Source
87
351
void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
88
351
  std::vector<RegionT *> RegionQueue;
89
351
  BlockT *OldExit = getExit();
90
351
91
351
  RegionQueue.push_back(static_cast<RegionT *>(this));
92
733
  while (!RegionQueue.empty()) {
93
382
    RegionT *R = RegionQueue.back();
94
382
    RegionQueue.pop_back();
95
382
96
382
    R->replaceExit(NewExit);
97
382
    for (std::unique_ptr<RegionT> &Child : *R) {
98
207
      if (Child->getExit() == OldExit)
99
31
        RegionQueue.push_back(Child.get());
100
207
    }
101
382
  }
102
351
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::replaceExitRecursive(llvm::MachineBasicBlock*)
103
104
template <class Tr>
105
492k
bool RegionBase<Tr>::contains(const BlockT *B) const {
106
492k
  BlockT *BB = const_cast<BlockT *>(B);
107
492k
108
492k
  if (!DT->getNode(BB))
109
7
    return false;
110
492k
111
492k
  BlockT *entry = getEntry(), *exit = getExit();
112
492k
113
492k
  // Toplevel region.
114
492k
  if (!exit)
115
4.98k
    return true;
116
487k
117
487k
  return (DT->dominates(entry, BB) &&
118
487k
          
!(459k
DT->dominates(exit, BB)459k
&&
DT->dominates(entry, exit)22.0k
));
119
487k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::contains(llvm::BasicBlock const*) const
Line
Count
Source
105
492k
bool RegionBase<Tr>::contains(const BlockT *B) const {
106
492k
  BlockT *BB = const_cast<BlockT *>(B);
107
492k
108
492k
  if (!DT->getNode(BB))
109
7
    return false;
110
492k
111
492k
  BlockT *entry = getEntry(), *exit = getExit();
112
492k
113
492k
  // Toplevel region.
114
492k
  if (!exit)
115
4.98k
    return true;
116
487k
117
487k
  return (DT->dominates(entry, BB) &&
118
487k
          
!(459k
DT->dominates(exit, BB)459k
&&
DT->dominates(entry, exit)22.0k
));
119
487k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::contains(llvm::MachineBasicBlock const*) const
120
121
template <class Tr>
122
150k
bool RegionBase<Tr>::contains(const LoopT *L) const {
123
150k
  // BBs that are not part of any loop are element of the Loop
124
150k
  // described by the NULL pointer. This loop is not part of any region,
125
150k
  // except if the region describes the whole function.
126
150k
  if (!L)
127
16.1k
    return getExit() == nullptr;
128
134k
129
134k
  if (!contains(L->getHeader()))
130
4.93k
    return false;
131
129k
132
129k
  SmallVector<BlockT *, 8> ExitingBlocks;
133
129k
  L->getExitingBlocks(ExitingBlocks);
134
129k
135
129k
  for (BlockT *BB : ExitingBlocks) {
136
129k
    if (!contains(BB))
137
738
      return false;
138
129k
  }
139
129k
140
129k
  
return true129k
;
141
129k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::contains(llvm::Loop const*) const
Line
Count
Source
122
150k
bool RegionBase<Tr>::contains(const LoopT *L) const {
123
150k
  // BBs that are not part of any loop are element of the Loop
124
150k
  // described by the NULL pointer. This loop is not part of any region,
125
150k
  // except if the region describes the whole function.
126
150k
  if (!L)
127
16.1k
    return getExit() == nullptr;
128
134k
129
134k
  if (!contains(L->getHeader()))
130
4.93k
    return false;
131
129k
132
129k
  SmallVector<BlockT *, 8> ExitingBlocks;
133
129k
  L->getExitingBlocks(ExitingBlocks);
134
129k
135
129k
  for (BlockT *BB : ExitingBlocks) {
136
129k
    if (!contains(BB))
137
738
      return false;
138
129k
  }
139
129k
140
129k
  
return true129k
;
141
129k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::contains(llvm::MachineLoop const*) const
142
143
template <class Tr>
144
14.8k
typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
145
14.8k
  if (!contains(L))
146
1.09k
    return nullptr;
147
13.7k
148
18.6k
  
while (13.7k
L && contains(L->getParentLoop())) {
149
4.90k
    L = L->getParentLoop();
150
4.90k
  }
151
13.7k
152
13.7k
  return L;
153
13.7k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::outermostLoopInRegion(llvm::Loop*) const
Line
Count
Source
144
14.8k
typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
145
14.8k
  if (!contains(L))
146
1.09k
    return nullptr;
147
13.7k
148
18.6k
  
while (13.7k
L && contains(L->getParentLoop())) {
149
4.90k
    L = L->getParentLoop();
150
4.90k
  }
151
13.7k
152
13.7k
  return L;
153
13.7k
}
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
4.09k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
165
4.09k
  BlockT *entry = getEntry();
166
4.09k
  BlockT *enteringBlock = nullptr;
167
4.09k
168
4.09k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
169
7.25k
                                 InvBlockTraits::child_end(entry))) {
170
7.25k
    if (DT->getNode(Pred) && !contains(Pred)) {
171
4.24k
      if (enteringBlock)
172
234
        return nullptr;
173
4.00k
174
4.00k
      enteringBlock = Pred;
175
4.00k
    }
176
7.25k
  }
177
4.09k
178
4.09k
  
return enteringBlock3.86k
;
179
4.09k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getEnteringBlock() const
Line
Count
Source
164
4.09k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
165
4.09k
  BlockT *entry = getEntry();
166
4.09k
  BlockT *enteringBlock = nullptr;
167
4.09k
168
4.09k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
169
7.25k
                                 InvBlockTraits::child_end(entry))) {
170
7.25k
    if (DT->getNode(Pred) && !contains(Pred)) {
171
4.24k
      if (enteringBlock)
172
234
        return nullptr;
173
4.00k
174
4.00k
      enteringBlock = Pred;
175
4.00k
    }
176
7.25k
  }
177
4.09k
178
4.09k
  
return enteringBlock3.86k
;
179
4.09k
}
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
4.74k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
206
4.74k
  BlockT *exit = getExit();
207
4.74k
  BlockT *exitingBlock = nullptr;
208
4.74k
209
4.74k
  if (!exit)
210
4
    return nullptr;
211
4.74k
212
4.74k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
213
6.23k
                                 InvBlockTraits::child_end(exit))) {
214
6.23k
    if (contains(Pred)) {
215
5.51k
      if (exitingBlock)
216
770
        return nullptr;
217
4.74k
218
4.74k
      exitingBlock = Pred;
219
4.74k
    }
220
6.23k
  }
221
4.74k
222
4.74k
  
return exitingBlock3.97k
;
223
4.74k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getExitingBlock() const
Line
Count
Source
205
4.74k
typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
206
4.74k
  BlockT *exit = getExit();
207
4.74k
  BlockT *exitingBlock = nullptr;
208
4.74k
209
4.74k
  if (!exit)
210
4
    return nullptr;
211
4.74k
212
4.74k
  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
213
6.23k
                                 InvBlockTraits::child_end(exit))) {
214
6.23k
    if (contains(Pred)) {
215
5.51k
      if (exitingBlock)
216
770
        return nullptr;
217
4.74k
218
4.74k
      exitingBlock = Pred;
219
4.74k
    }
220
6.23k
  }
221
4.74k
222
4.74k
  
return exitingBlock3.97k
;
223
4.74k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getExitingBlock() const
224
225
template <class Tr>
226
4.35k
bool RegionBase<Tr>::isSimple() const {
227
4.35k
  return !isTopLevelRegion() && 
getEnteringBlock()2.93k
&&
getExitingBlock()2.61k
;
228
4.35k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::isSimple() const
Line
Count
Source
226
4.35k
bool RegionBase<Tr>::isSimple() const {
227
4.35k
  return !isTopLevelRegion() && 
getEnteringBlock()2.93k
&&
getExitingBlock()2.61k
;
228
4.35k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::isSimple() const
229
230
template <class Tr>
231
3.43k
std::string RegionBase<Tr>::getNameStr() const {
232
3.43k
  std::string exitName;
233
3.43k
  std::string entryName;
234
3.43k
235
3.43k
  if (getEntry()->getName().empty()) {
236
20
    raw_string_ostream OS(entryName);
237
20
238
20
    getEntry()->printAsOperand(OS, false);
239
20
  } else
240
3.41k
    entryName = getEntry()->getName();
241
3.43k
242
3.43k
  if (getExit()) {
243
2.50k
    if (getExit()->getName().empty()) {
244
13
      raw_string_ostream OS(exitName);
245
13
246
13
      getExit()->printAsOperand(OS, false);
247
13
    } else
248
2.48k
      exitName = getExit()->getName();
249
2.50k
  } else
250
935
    exitName = "<Function Return>";
251
3.43k
252
3.43k
  return entryName + " => " + exitName;
253
3.43k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getNameStr() const
Line
Count
Source
231
3.43k
std::string RegionBase<Tr>::getNameStr() const {
232
3.43k
  std::string exitName;
233
3.43k
  std::string entryName;
234
3.43k
235
3.43k
  if (getEntry()->getName().empty()) {
236
20
    raw_string_ostream OS(entryName);
237
20
238
20
    getEntry()->printAsOperand(OS, false);
239
20
  } else
240
3.41k
    entryName = getEntry()->getName();
241
3.43k
242
3.43k
  if (getExit()) {
243
2.50k
    if (getExit()->getName().empty()) {
244
13
      raw_string_ostream OS(exitName);
245
13
246
13
      getExit()->printAsOperand(OS, false);
247
13
    } else
248
2.48k
      exitName = getExit()->getName();
249
2.50k
  } else
250
935
    exitName = "<Function Return>";
251
3.43k
252
3.43k
  return entryName + " => " + exitName;
253
3.43k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getNameStr() const
254
255
template <class Tr>
256
244
void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
257
244
  if (!contains(BB))
258
0
    report_fatal_error("Broken region found: enumerated BB not in region!");
259
244
260
244
  BlockT *entry = getEntry(), *exit = getExit();
261
244
262
244
  for (BlockT *Succ :
263
338
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
264
338
    if (!contains(Succ) && 
exit != Succ38
)
265
0
      report_fatal_error("Broken region found: edges leaving the region must go "
266
0
                         "to the exit node!");
267
338
  }
268
244
269
244
  if (entry != BB) {
270
197
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
271
274
                                   InvBlockTraits::child_end(BB))) {
272
274
      if (!contains(Pred))
273
0
        report_fatal_error("Broken region found: edges entering the region must "
274
0
                           "go to the entry node!");
275
274
    }
276
197
  }
277
244
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyBBInRegion(llvm::BasicBlock*) const
Line
Count
Source
256
244
void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
257
244
  if (!contains(BB))
258
0
    report_fatal_error("Broken region found: enumerated BB not in region!");
259
244
260
244
  BlockT *entry = getEntry(), *exit = getExit();
261
244
262
244
  for (BlockT *Succ :
263
338
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
264
338
    if (!contains(Succ) && 
exit != Succ38
)
265
0
      report_fatal_error("Broken region found: edges leaving the region must go "
266
0
                         "to the exit node!");
267
338
  }
268
244
269
244
  if (entry != BB) {
270
197
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
271
274
                                   InvBlockTraits::child_end(BB))) {
272
274
      if (!contains(Pred))
273
0
        report_fatal_error("Broken region found: edges entering the region must "
274
0
                           "go to the entry node!");
275
274
    }
276
197
  }
277
244
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::verifyBBInRegion(llvm::MachineBasicBlock*) const
278
279
template <class Tr>
280
244
void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
281
244
  BlockT *exit = getExit();
282
244
283
244
  visited->insert(BB);
284
244
285
244
  verifyBBInRegion(BB);
286
244
287
244
  for (BlockT *Succ :
288
338
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
289
338
    if (Succ != exit && 
visited->find(Succ) == visited->end()300
)
290
197
      verifyWalk(Succ, visited);
291
338
  }
292
244
}
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
244
void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
281
244
  BlockT *exit = getExit();
282
244
283
244
  visited->insert(BB);
284
244
285
244
  verifyBBInRegion(BB);
286
244
287
244
  for (BlockT *Succ :
288
338
       make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
289
338
    if (Succ != exit && 
visited->find(Succ) == visited->end()300
)
290
197
      verifyWalk(Succ, visited);
291
338
  }
292
244
}
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
13.6k
void RegionBase<Tr>::verifyRegion() const {
296
13.6k
  // Only do verification when user wants to, otherwise this expensive check
297
13.6k
  // will be invoked by PMDataManager::verifyPreservedAnalysis when
298
13.6k
  // a regionpass (marked PreservedAll) finish.
299
13.6k
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
300
13.5k
    return;
301
47
302
47
  std::set<BlockT *> visited;
303
47
  verifyWalk(getEntry(), &visited);
304
47
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::verifyRegion() const
Line
Count
Source
295
13.6k
void RegionBase<Tr>::verifyRegion() const {
296
13.6k
  // Only do verification when user wants to, otherwise this expensive check
297
13.6k
  // will be invoked by PMDataManager::verifyPreservedAnalysis when
298
13.6k
  // a regionpass (marked PreservedAll) finish.
299
13.6k
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
300
13.5k
    return;
301
47
302
47
  std::set<BlockT *> visited;
303
47
  verifyWalk(getEntry(), &visited);
304
47
}
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
2.78k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
316
2.78k
  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
317
2.78k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_begin()
Line
Count
Source
315
2.78k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
316
2.78k
  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
317
2.78k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_begin()
318
319
template <class Tr>
320
2.78k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
321
2.78k
  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
322
2.78k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_end()
Line
Count
Source
320
2.78k
typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
321
2.78k
  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
322
2.78k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_end()
323
324
template <class Tr>
325
typename RegionBase<Tr>::const_element_iterator
326
0
RegionBase<Tr>::element_begin() const {
327
0
  return GraphTraits<const RegionT *>::nodes_begin(
328
0
      static_cast<const RegionT *>(this));
329
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_begin() const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_begin() const
330
331
template <class Tr>
332
typename RegionBase<Tr>::const_element_iterator
333
0
RegionBase<Tr>::element_end() const {
334
0
  return GraphTraits<const RegionT *>::nodes_end(
335
0
      static_cast<const RegionT *>(this));
336
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::element_end() const
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::element_end() const
337
338
template <class Tr>
339
47.2k
typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
340
47.2k
  using RegionT = typename Tr::RegionT;
341
47.2k
342
47.2k
  RegionT *R = RI->getRegionFor(BB);
343
47.2k
344
47.2k
  if (!R || R == this)
345
39.1k
    return nullptr;
346
8.13k
347
8.13k
  // If we pass the BB out of this region, that means our code is broken.
348
8.13k
  assert(contains(R) && "BB not in current region!");
349
8.13k
350
8.37k
  while (contains(R->getParent()) && R->getParent() != this)
351
231
    R = R->getParent();
352
8.13k
353
8.13k
  if (R->getEntry() != BB)
354
0
    return nullptr;
355
8.13k
356
8.13k
  return R;
357
8.13k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getSubRegionNode(llvm::BasicBlock*) const
Line
Count
Source
339
47.2k
typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
340
47.2k
  using RegionT = typename Tr::RegionT;
341
47.2k
342
47.2k
  RegionT *R = RI->getRegionFor(BB);
343
47.2k
344
47.2k
  if (!R || R == this)
345
39.1k
    return nullptr;
346
8.13k
347
8.13k
  // If we pass the BB out of this region, that means our code is broken.
348
8.13k
  assert(contains(R) && "BB not in current region!");
349
8.13k
350
8.37k
  while (contains(R->getParent()) && R->getParent() != this)
351
231
    R = R->getParent();
352
8.13k
353
8.13k
  if (R->getEntry() != BB)
354
0
    return nullptr;
355
8.13k
356
8.13k
  return R;
357
8.13k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getSubRegionNode(llvm::MachineBasicBlock*) const
358
359
template <class Tr>
360
39.1k
typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
361
39.1k
  assert(contains(BB) && "Can get BB node out of this region!");
362
39.1k
363
39.1k
  typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
364
39.1k
365
39.1k
  if (at == BBNodeMap.end()) {
366
6.74k
    auto Deconst = const_cast<RegionBase<Tr> *>(this);
367
6.74k
    typename BBNodeMapT::value_type V = {
368
6.74k
        BB,
369
6.74k
        llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
370
6.74k
    at = BBNodeMap.insert(std::move(V)).first;
371
6.74k
  }
372
39.1k
  return at->second.get();
373
39.1k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getBBNode(llvm::BasicBlock*) const
Line
Count
Source
360
39.1k
typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
361
39.1k
  assert(contains(BB) && "Can get BB node out of this region!");
362
39.1k
363
39.1k
  typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
364
39.1k
365
39.1k
  if (at == BBNodeMap.end()) {
366
6.74k
    auto Deconst = const_cast<RegionBase<Tr> *>(this);
367
6.74k
    typename BBNodeMapT::value_type V = {
368
6.74k
        BB,
369
6.74k
        llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
370
6.74k
    at = BBNodeMap.insert(std::move(V)).first;
371
6.74k
  }
372
39.1k
  return at->second.get();
373
39.1k
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::MachineFunction> >::getBBNode(llvm::MachineBasicBlock*) const
374
375
template <class Tr>
376
47.2k
typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
377
47.2k
  assert(contains(BB) && "Can get BB node out of this region!");
378
47.2k
  if (RegionT *Child = getSubRegionNode(BB))
379
8.13k
    return Child->getNode();
380
39.1k
381
39.1k
  return getBBNode(BB);
382
39.1k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getNode(llvm::BasicBlock*) const
Line
Count
Source
376
47.2k
typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
377
47.2k
  assert(contains(BB) && "Can get BB node out of this region!");
378
47.2k
  if (RegionT *Child = getSubRegionNode(BB))
379
8.13k
    return Child->getNode();
380
39.1k
381
39.1k
  return getBBNode(BB);
382
39.1k
}
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
3.27k
void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
395
3.27k
  assert(!SubRegion->parent && "SubRegion already has a parent!");
396
3.27k
  assert(llvm::find_if(*this,
397
3.27k
                       [&](const std::unique_ptr<RegionT> &R) {
398
3.27k
                         return R.get() == SubRegion;
399
3.27k
                       }) == children.end() &&
400
3.27k
         "Subregion already exists!");
401
3.27k
402
3.27k
  SubRegion->parent = static_cast<RegionT *>(this);
403
3.27k
  children.push_back(std::unique_ptr<RegionT>(SubRegion));
404
3.27k
405
3.27k
  if (!moveChildren)
406
2.93k
    return;
407
349
408
349
  assert(SubRegion->children.empty() &&
409
349
         "SubRegions that contain children are not supported");
410
349
411
1.76k
  for (RegionNodeT *Element : elements()) {
412
1.76k
    if (!Element->isSubRegion()) {
413
1.17k
      BlockT *BB = Element->template getNodeAs<BlockT>();
414
1.17k
415
1.17k
      if (SubRegion->contains(BB))
416
396
        RI->setRegionFor(BB, SubRegion);
417
1.17k
    }
418
1.76k
  }
419
349
420
349
  std::vector<std::unique_ptr<RegionT>> Keep;
421
936
  for (std::unique_ptr<RegionT> &R : *this) {
422
936
    if (SubRegion->contains(R.get()) && 
R.get() != SubRegion907
) {
423
558
      R->parent = SubRegion;
424
558
      SubRegion->children.push_back(std::move(R));
425
558
    } else
426
378
      Keep.push_back(std::move(R));
427
936
  }
428
349
429
349
  children.clear();
430
349
  children.insert(
431
349
      children.begin(),
432
349
      std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
433
349
      std::move_iterator<typename RegionSet::iterator>(Keep.end()));
434
349
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::addSubRegion(llvm::Region*, bool)
Line
Count
Source
394
3.27k
void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
395
3.27k
  assert(!SubRegion->parent && "SubRegion already has a parent!");
396
3.27k
  assert(llvm::find_if(*this,
397
3.27k
                       [&](const std::unique_ptr<RegionT> &R) {
398
3.27k
                         return R.get() == SubRegion;
399
3.27k
                       }) == children.end() &&
400
3.27k
         "Subregion already exists!");
401
3.27k
402
3.27k
  SubRegion->parent = static_cast<RegionT *>(this);
403
3.27k
  children.push_back(std::unique_ptr<RegionT>(SubRegion));
404
3.27k
405
3.27k
  if (!moveChildren)
406
2.93k
    return;
407
349
408
349
  assert(SubRegion->children.empty() &&
409
349
         "SubRegions that contain children are not supported");
410
349
411
1.76k
  for (RegionNodeT *Element : elements()) {
412
1.76k
    if (!Element->isSubRegion()) {
413
1.17k
      BlockT *BB = Element->template getNodeAs<BlockT>();
414
1.17k
415
1.17k
      if (SubRegion->contains(BB))
416
396
        RI->setRegionFor(BB, SubRegion);
417
1.17k
    }
418
1.76k
  }
419
349
420
349
  std::vector<std::unique_ptr<RegionT>> Keep;
421
936
  for (std::unique_ptr<RegionT> &R : *this) {
422
936
    if (SubRegion->contains(R.get()) && 
R.get() != SubRegion907
) {
423
558
      R->parent = SubRegion;
424
558
      SubRegion->children.push_back(std::move(R));
425
558
    } else
426
378
      Keep.push_back(std::move(R));
427
936
  }
428
349
429
349
  children.clear();
430
349
  children.insert(
431
349
      children.begin(),
432
349
      std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
433
349
      std::move_iterator<typename RegionSet::iterator>(Keep.end()));
434
349
}
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
3
unsigned RegionBase<Tr>::getDepth() const {
451
3
  unsigned Depth = 0;
452
3
453
8
  for (RegionT *R = getParent(); R != nullptr; 
R = R->getParent()5
)
454
5
    ++Depth;
455
3
456
3
  return Depth;
457
3
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::getDepth() const
Line
Count
Source
450
3
unsigned RegionBase<Tr>::getDepth() const {
451
3
  unsigned Depth = 0;
452
3
453
8
  for (RegionT *R = getParent(); R != nullptr; 
R = R->getParent()5
)
454
5
    ++Depth;
455
3
456
3
  return Depth;
457
3
}
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
745
466
745
  RegionT *R = RI->getRegionFor(exit);
467
745
468
745
  if (R->getEntry() != exit) {
469
474
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
470
474
                                   InvBlockTraits::child_end(getExit())))
471
579
      if (!contains(Pred))
472
18
        return nullptr;
473
474
    
if (456
Tr::getNumSuccessors(exit) == 1456
)
474
412
      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
745
466
745
  RegionT *R = RI->getRegionFor(exit);
467
745
468
745
  if (R->getEntry() != exit) {
469
474
    for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
470
474
                                   InvBlockTraits::child_end(getExit())))
471
579
      if (!contains(Pred))
472
18
        return nullptr;
473
474
    
if (456
Tr::getNumSuccessors(exit) == 1456
)
474
412
      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
0
                           PrintStyle Style) const {
493
0
  if (print_tree)
494
0
    OS.indent(level * 2) << '[' << level << "] " << getNameStr();
495
0
  else
496
0
    OS.indent(level * 2) << getNameStr();
497
0
498
0
  OS << '\n';
499
0
500
0
  if (Style != PrintNone) {
501
0
    OS.indent(level * 2) << "{\n";
502
0
    OS.indent(level * 2 + 2);
503
0
504
0
    if (Style == PrintBB) {
505
0
      for (const auto *BB : blocks())
506
0
        OS << BB->getName() << ", "; // TODO: remove the last ","
507
0
    } else if (Style == PrintRN) {
508
0
      for (const RegionNodeT *Element : elements()) {
509
0
        OS << *Element << ", "; // TODO: remove the last ",
510
0
      }
511
0
    }
512
0
513
0
    OS << '\n';
514
0
  }
515
0
516
0
  if (print_tree) {
517
0
    for (const std::unique_ptr<RegionT> &R : *this)
518
0
      R->print(OS, print_tree, level + 1, Style);
519
0
  }
520
0
521
0
  if (Style != PrintNone)
522
0
    OS.indent(level * 2) << "} \n";
523
0
}
Unexecuted instantiation: llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::print(llvm::raw_ostream&, bool, unsigned int, llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::PrintStyle) const
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
19.7k
void RegionBase<Tr>::clearNodeCache() {
534
19.7k
  BBNodeMap.clear();
535
19.7k
  for (std::unique_ptr<RegionT> &R : *this)
536
15.6k
    R->clearNodeCache();
537
19.7k
}
llvm::RegionBase<llvm::RegionTraits<llvm::Function> >::clearNodeCache()
Line
Count
Source
533
19.7k
void RegionBase<Tr>::clearNodeCache() {
534
19.7k
  BBNodeMap.clear();
535
19.7k
  for (std::unique_ptr<RegionT> &R : *this)
536
15.6k
    R->clearNodeCache();
537
19.7k
}
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
1.27k
RegionInfoBase<Tr>::~RegionInfoBase() {
548
1.27k
  releaseMemory();
549
1.27k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::~RegionInfoBase()
Line
Count
Source
547
1.27k
RegionInfoBase<Tr>::~RegionInfoBase() {
548
1.27k
  releaseMemory();
549
1.27k
}
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.33k
                                             BlockT *exit) const {
569
3.33k
  for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
570
6.77k
                              InvBlockTraits::child_end(BB))) {
571
6.77k
    if (DT->dominates(entry, P) && 
!DT->dominates(exit, P)3.36k
)
572
2
      return false;
573
6.77k
  }
574
3.33k
575
3.33k
  
return true3.33k
;
576
3.33k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isCommonDomFrontier(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
568
3.33k
                                             BlockT *exit) const {
569
3.33k
  for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
570
6.77k
                              InvBlockTraits::child_end(BB))) {
571
6.77k
    if (DT->dominates(entry, P) && 
!DT->dominates(exit, P)3.36k
)
572
2
      return false;
573
6.77k
  }
574
3.33k
575
3.33k
  
return true3.33k
;
576
3.33k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::isCommonDomFrontier(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) const
577
578
template <class Tr>
579
12.1k
bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
580
12.1k
  assert(entry && exit && "entry and exit must not be null!");
581
12.1k
582
12.1k
  using DST = typename DomFrontierT::DomSetType;
583
12.1k
584
12.1k
  DST *entrySuccs = &DF->find(entry)->second;
585
12.1k
586
12.1k
  // Exit is the header of a loop that contains the entry. In this case,
587
12.1k
  // the dominance frontier must only contain the exit.
588
12.1k
  if (!DT->dominates(entry, exit)) {
589
4.67k
    for (typename DST::iterator SI = entrySuccs->begin(),
590
4.67k
                                SE = entrySuccs->end();
591
7.18k
         SI != SE; 
++SI2.51k
) {
592
4.95k
      if (*SI != exit && 
*SI != entry2.63k
)
593
2.43k
        return false;
594
4.95k
    }
595
4.67k
596
4.67k
    
return true2.23k
;
597
7.51k
  }
598
7.51k
599
7.51k
  DST *exitSuccs = &DF->find(exit)->second;
600
7.51k
601
7.51k
  // Do not allow edges leaving the region.
602
7.51k
  for (BlockT *Succ : *entrySuccs) {
603
6.61k
    if (Succ == exit || Succ == entry)
604
2.42k
      continue;
605
4.19k
    if (exitSuccs->find(Succ) == exitSuccs->end())
606
856
      return false;
607
3.33k
    if (!isCommonDomFrontier(Succ, entry, exit))
608
2
      return false;
609
3.33k
  }
610
7.51k
611
7.51k
  // Do not allow edges pointing into the region.
612
7.51k
  
for (BlockT *Succ : *exitSuccs)6.66k
{
613
5.49k
    if (DT->properlyDominates(entry, Succ) && 
Succ != exit1.99k
)
614
11
      return false;
615
5.49k
  }
616
6.66k
617
6.66k
  
return true6.65k
;
618
6.66k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isRegion(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
579
12.1k
bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
580
12.1k
  assert(entry && exit && "entry and exit must not be null!");
581
12.1k
582
12.1k
  using DST = typename DomFrontierT::DomSetType;
583
12.1k
584
12.1k
  DST *entrySuccs = &DF->find(entry)->second;
585
12.1k
586
12.1k
  // Exit is the header of a loop that contains the entry. In this case,
587
12.1k
  // the dominance frontier must only contain the exit.
588
12.1k
  if (!DT->dominates(entry, exit)) {
589
4.67k
    for (typename DST::iterator SI = entrySuccs->begin(),
590
4.67k
                                SE = entrySuccs->end();
591
7.18k
         SI != SE; 
++SI2.51k
) {
592
4.95k
      if (*SI != exit && 
*SI != entry2.63k
)
593
2.43k
        return false;
594
4.95k
    }
595
4.67k
596
4.67k
    
return true2.23k
;
597
7.51k
  }
598
7.51k
599
7.51k
  DST *exitSuccs = &DF->find(exit)->second;
600
7.51k
601
7.51k
  // Do not allow edges leaving the region.
602
7.51k
  for (BlockT *Succ : *entrySuccs) {
603
6.61k
    if (Succ == exit || Succ == entry)
604
2.42k
      continue;
605
4.19k
    if (exitSuccs->find(Succ) == exitSuccs->end())
606
856
      return false;
607
3.33k
    if (!isCommonDomFrontier(Succ, entry, exit))
608
2
      return false;
609
3.33k
  }
610
7.51k
611
7.51k
  // Do not allow edges pointing into the region.
612
7.51k
  
for (BlockT *Succ : *exitSuccs)6.66k
{
613
5.49k
    if (DT->properlyDominates(entry, Succ) && 
Succ != exit1.99k
)
614
11
      return false;
615
5.49k
  }
616
6.66k
617
6.66k
  
return true6.65k
;
618
6.66k
}
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
8.44k
                                        BBtoBBMap *ShortCut) const {
623
8.44k
  assert(entry && exit && "entry and exit must not be null!");
624
8.44k
625
8.44k
  typename BBtoBBMap::iterator e = ShortCut->find(exit);
626
8.44k
627
8.44k
  if (e == ShortCut->end())
628
3.67k
    // No further region at exit available.
629
3.67k
    (*ShortCut)[entry] = exit;
630
4.77k
  else {
631
4.77k
    // We found a region e that starts at exit. Therefore (entry, e->second)
632
4.77k
    // is also a region, that is larger than (entry, exit). Insert the
633
4.77k
    // larger one.
634
4.77k
    BlockT *BB = e->second;
635
4.77k
    (*ShortCut)[entry] = BB;
636
4.77k
  }
637
8.44k
}
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
8.44k
                                        BBtoBBMap *ShortCut) const {
623
8.44k
  assert(entry && exit && "entry and exit must not be null!");
624
8.44k
625
8.44k
  typename BBtoBBMap::iterator e = ShortCut->find(exit);
626
8.44k
627
8.44k
  if (e == ShortCut->end())
628
3.67k
    // No further region at exit available.
629
3.67k
    (*ShortCut)[entry] = exit;
630
4.77k
  else {
631
4.77k
    // We found a region e that starts at exit. Therefore (entry, e->second)
632
4.77k
    // is also a region, that is larger than (entry, exit). Insert the
633
4.77k
    // larger one.
634
4.77k
    BlockT *BB = e->second;
635
4.77k
    (*ShortCut)[entry] = BB;
636
4.77k
  }
637
8.44k
}
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
18.1k
RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
642
18.1k
  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
643
18.1k
644
18.1k
  if (e == ShortCut->end())
645
13.1k
    return N->getIDom();
646
5.00k
647
5.00k
  return PDT->getNode(e->second)->getIDom();
648
5.00k
}
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
18.1k
RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
642
18.1k
  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
643
18.1k
644
18.1k
  if (e == ShortCut->end())
645
13.1k
    return N->getIDom();
646
5.00k
647
5.00k
  return PDT->getNode(e->second)->getIDom();
648
5.00k
}
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
8.88k
bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
652
8.88k
  assert(entry && exit && "entry and exit must not be null!");
653
8.88k
654
8.88k
  unsigned num_successors =
655
8.88k
      BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
656
8.88k
657
8.88k
  if (num_successors <= 1 && 
exit == *(BlockTraits::child_begin(entry))6.27k
)
658
5.95k
    return true;
659
2.93k
660
2.93k
  return false;
661
2.93k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::isTrivialRegion(llvm::BasicBlock*, llvm::BasicBlock*) const
Line
Count
Source
651
8.88k
bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
652
8.88k
  assert(entry && exit && "entry and exit must not be null!");
653
8.88k
654
8.88k
  unsigned num_successors =
655
8.88k
      BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
656
8.88k
657
8.88k
  if (num_successors <= 1 && 
exit == *(BlockTraits::child_begin(entry))6.27k
)
658
5.95k
    return true;
659
2.93k
660
2.93k
  return false;
661
2.93k
}
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
8.88k
                                                       BlockT *exit) {
666
8.88k
  assert(entry && exit && "entry and exit must not be null!");
667
8.88k
668
8.88k
  if (isTrivialRegion(entry, exit))
669
5.95k
    return nullptr;
670
2.93k
671
2.93k
  RegionT *region =
672
2.93k
      new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
673
2.93k
  BBtoRegion.insert({entry, region});
674
2.93k
675
2.93k
#ifdef EXPENSIVE_CHECKS
676
2.93k
  region->verifyRegion();
677
2.93k
#else
678
2.93k
  LLVM_DEBUG(region->verifyRegion());
679
2.93k
#endif
680
2.93k
681
2.93k
  updateStatistics(region);
682
2.93k
  return region;
683
2.93k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::createRegion(llvm::BasicBlock*, llvm::BasicBlock*)
Line
Count
Source
665
8.88k
                                                       BlockT *exit) {
666
8.88k
  assert(entry && exit && "entry and exit must not be null!");
667
8.88k
668
8.88k
  if (isTrivialRegion(entry, exit))
669
5.95k
    return nullptr;
670
2.93k
671
2.93k
  RegionT *region =
672
2.93k
      new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
673
2.93k
  BBtoRegion.insert({entry, region});
674
2.93k
675
2.93k
#ifdef EXPENSIVE_CHECKS
676
2.93k
  region->verifyRegion();
677
2.93k
#else
678
2.93k
  LLVM_DEBUG(region->verifyRegion());
679
2.93k
#endif
680
2.93k
681
2.93k
  updateStatistics(region);
682
2.93k
  return region;
683
2.93k
}
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
10.6k
                                              BBtoBBMap *ShortCut) {
688
10.6k
  assert(entry);
689
10.6k
690
10.6k
  DomTreeNodeT *N = PDT->getNode(entry);
691
10.6k
  if (!N)
692
0
    return;
693
10.6k
694
10.6k
  RegionT *lastRegion = nullptr;
695
10.6k
  BlockT *lastExit = entry;
696
10.6k
697
10.6k
  // As only a BasicBlock that postdominates entry can finish a region, walk the
698
10.6k
  // post dominance tree upwards.
699
18.1k
  while ((N = getNextPostDom(N, ShortCut))) {
700
18.1k
    BlockT *exit = N->getBlock();
701
18.1k
702
18.1k
    if (!exit)
703
5.93k
      break;
704
12.1k
705
12.1k
    if (isRegion(entry, exit)) {
706
8.88k
      RegionT *newRegion = createRegion(entry, exit);
707
8.88k
708
8.88k
      if (lastRegion)
709
118
        newRegion->addSubRegion(lastRegion);
710
8.88k
711
8.88k
      lastRegion = newRegion;
712
8.88k
      lastExit = exit;
713
8.88k
    }
714
12.1k
715
12.1k
    // This can never be a region, so stop the search.
716
12.1k
    if (!DT->dominates(entry, exit))
717
4.67k
      break;
718
12.1k
  }
719
10.6k
720
10.6k
  // Tried to create regions from entry to lastExit.  Next time take a
721
10.6k
  // shortcut from entry to lastExit.
722
10.6k
  if (lastExit != entry)
723
8.44k
    insertShortCut(entry, lastExit, ShortCut);
724
10.6k
}
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
10.6k
                                              BBtoBBMap *ShortCut) {
688
10.6k
  assert(entry);
689
10.6k
690
10.6k
  DomTreeNodeT *N = PDT->getNode(entry);
691
10.6k
  if (!N)
692
0
    return;
693
10.6k
694
10.6k
  RegionT *lastRegion = nullptr;
695
10.6k
  BlockT *lastExit = entry;
696
10.6k
697
10.6k
  // As only a BasicBlock that postdominates entry can finish a region, walk the
698
10.6k
  // post dominance tree upwards.
699
18.1k
  while ((N = getNextPostDom(N, ShortCut))) {
700
18.1k
    BlockT *exit = N->getBlock();
701
18.1k
702
18.1k
    if (!exit)
703
5.93k
      break;
704
12.1k
705
12.1k
    if (isRegion(entry, exit)) {
706
8.88k
      RegionT *newRegion = createRegion(entry, exit);
707
8.88k
708
8.88k
      if (lastRegion)
709
118
        newRegion->addSubRegion(lastRegion);
710
8.88k
711
8.88k
      lastRegion = newRegion;
712
8.88k
      lastExit = exit;
713
8.88k
    }
714
12.1k
715
12.1k
    // This can never be a region, so stop the search.
716
12.1k
    if (!DT->dominates(entry, exit))
717
4.67k
      break;
718
12.1k
  }
719
10.6k
720
10.6k
  // Tried to create regions from entry to lastExit.  Next time take a
721
10.6k
  // shortcut from entry to lastExit.
722
10.6k
  if (lastExit != entry)
723
8.44k
    insertShortCut(entry, lastExit, ShortCut);
724
10.6k
}
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
1.42k
void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
728
1.42k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
729
1.42k
730
1.42k
  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
731
1.42k
  DomTreeNodeT *N = DT->getNode(entry);
732
1.42k
733
1.42k
  // Iterate over the dominance tree in post order to start with the small
734
1.42k
  // regions from the bottom of the dominance tree.  If the small regions are
735
1.42k
  // detected first, detection of bigger regions is faster, as we can jump
736
1.42k
  // over the small regions.
737
1.42k
  for (auto DomNode : post_order(N))
738
10.6k
    findRegionsWithEntry(DomNode->getBlock(), ShortCut);
739
1.42k
}
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
1.42k
void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
728
1.42k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
729
1.42k
730
1.42k
  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
731
1.42k
  DomTreeNodeT *N = DT->getNode(entry);
732
1.42k
733
1.42k
  // Iterate over the dominance tree in post order to start with the small
734
1.42k
  // regions from the bottom of the dominance tree.  If the small regions are
735
1.42k
  // detected first, detection of bigger regions is faster, as we can jump
736
1.42k
  // over the small regions.
737
1.42k
  for (auto DomNode : post_order(N))
738
10.6k
    findRegionsWithEntry(DomNode->getBlock(), ShortCut);
739
1.42k
}
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
2.81k
typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
743
2.93k
  while (region->getParent())
744
118
    region = region->getParent();
745
2.81k
746
2.81k
  return region;
747
2.81k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getTopMostParent(llvm::Region*)
Line
Count
Source
742
2.81k
typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
743
2.93k
  while (region->getParent())
744
118
    region = region->getParent();
745
2.81k
746
2.81k
  return region;
747
2.81k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getTopMostParent(llvm::MachineRegion*)
748
749
template <class Tr>
750
10.6k
void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
751
10.6k
  BlockT *BB = N->getBlock();
752
10.6k
753
10.6k
  // Passed region exit
754
13.2k
  while (BB == region->getExit())
755
2.66k
    region = region->getParent();
756
10.6k
757
10.6k
  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
758
10.6k
759
10.6k
  // This basic block is a start block of a region. It is already in the
760
10.6k
  // BBtoRegion relation. Only the child basic blocks have to be updated.
761
10.6k
  if (it != BBtoRegion.end()) {
762
2.81k
    RegionT *newRegion = it->second;
763
2.81k
    region->addSubRegion(getTopMostParent(newRegion));
764
2.81k
    region = newRegion;
765
7.79k
  } else {
766
7.79k
    BBtoRegion[BB] = region;
767
7.79k
  }
768
10.6k
769
10.6k
  for (DomTreeNodeBase<BlockT> *C : *N) {
770
9.17k
    buildRegionsTree(C, region);
771
9.17k
  }
772
10.6k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::buildRegionsTree(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::Region*)
Line
Count
Source
750
10.6k
void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
751
10.6k
  BlockT *BB = N->getBlock();
752
10.6k
753
10.6k
  // Passed region exit
754
13.2k
  while (BB == region->getExit())
755
2.66k
    region = region->getParent();
756
10.6k
757
10.6k
  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
758
10.6k
759
10.6k
  // This basic block is a start block of a region. It is already in the
760
10.6k
  // BBtoRegion relation. Only the child basic blocks have to be updated.
761
10.6k
  if (it != BBtoRegion.end()) {
762
2.81k
    RegionT *newRegion = it->second;
763
2.81k
    region->addSubRegion(getTopMostParent(newRegion));
764
2.81k
    region = newRegion;
765
7.79k
  } else {
766
7.79k
    BBtoRegion[BB] = region;
767
7.79k
  }
768
10.6k
769
10.6k
  for (DomTreeNodeBase<BlockT> *C : *N) {
770
9.17k
    buildRegionsTree(C, region);
771
9.17k
  }
772
10.6k
}
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
0
void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
788
0
  OS << "Region tree:\n";
789
0
  TopLevelRegion->print(OS, true, 0, printStyle);
790
0
  OS << "End region tree\n";
791
0
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::print(llvm::raw_ostream&) const
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
4.09k
void RegionInfoBase<Tr>::releaseMemory() {
800
4.09k
  BBtoRegion.clear();
801
4.09k
  if (TopLevelRegion)
802
1.40k
    delete TopLevelRegion;
803
4.09k
  TopLevelRegion = nullptr;
804
4.09k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::releaseMemory()
Line
Count
Source
799
4.09k
void RegionInfoBase<Tr>::releaseMemory() {
800
4.09k
  BBtoRegion.clear();
801
4.09k
  if (TopLevelRegion)
802
1.40k
    delete TopLevelRegion;
803
4.09k
  TopLevelRegion = nullptr;
804
4.09k
}
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
66.8k
typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
821
66.8k
  typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
822
66.8k
  return I != BBtoRegion.end() ? 
I->second64.9k
:
nullptr1.85k
;
823
66.8k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::getRegionFor(llvm::BasicBlock*) const
Line
Count
Source
820
66.8k
typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
821
66.8k
  typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
822
66.8k
  return I != BBtoRegion.end() ? 
I->second64.9k
:
nullptr1.85k
;
823
66.8k
}
Unexecuted instantiation: llvm::RegionInfoBase<llvm::RegionTraits<llvm::MachineFunction> >::getRegionFor(llvm::MachineBasicBlock*) const
824
825
template <class Tr>
826
4.35k
void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
827
4.35k
  BBtoRegion[BB] = R;
828
4.35k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::setRegionFor(llvm::BasicBlock*, llvm::Region*)
Line
Count
Source
826
4.35k
void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
827
4.35k
  BBtoRegion[BB] = R;
828
4.35k
}
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
1.42k
void RegionInfoBase<Tr>::calculate(FuncT &F) {
916
1.42k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
917
1.42k
918
1.42k
  // ShortCut a function where for every BB the exit of the largest region
919
1.42k
  // starting with BB is stored. These regions can be threated as single BBS.
920
1.42k
  // This improves performance on linear CFGs.
921
1.42k
  BBtoBBMap ShortCut;
922
1.42k
923
1.42k
  scanForRegions(F, &ShortCut);
924
1.42k
  BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
925
1.42k
  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
926
1.42k
}
llvm::RegionInfoBase<llvm::RegionTraits<llvm::Function> >::calculate(llvm::Function&)
Line
Count
Source
915
1.42k
void RegionInfoBase<Tr>::calculate(FuncT &F) {
916
1.42k
  using FuncPtrT = typename std::add_pointer<FuncT>::type;
917
1.42k
918
1.42k
  // ShortCut a function where for every BB the exit of the largest region
919
1.42k
  // starting with BB is stored. These regions can be threated as single BBS.
920
1.42k
  // This improves performance on linear CFGs.
921
1.42k
  BBtoBBMap ShortCut;
922
1.42k
923
1.42k
  scanForRegions(F, &ShortCut);
924
1.42k
  BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
925
1.42k
  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
926
1.42k
}
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