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