Coverage Report

Created: 2019-07-24 05:18

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