LLVM 18.0.0git
RegionInfoImpl.h
Go to the documentation of this file.
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
16#include "llvm/ADT/STLExtras.h"
22#include "llvm/Config/llvm-config.h"
23#include "llvm/Support/Debug.h"
25#include <algorithm>
26#include <cassert>
27#include <iterator>
28#include <memory>
29#include <set>
30#include <string>
31#include <type_traits>
32#include <vector>
33
34#define DEBUG_TYPE "region"
35
36namespace llvm {
37class raw_ostream;
38
39//===----------------------------------------------------------------------===//
40/// RegionBase Implementation
41template <class Tr>
42RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit,
43 typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
44 RegionT *Parent)
45 : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
46
47template <class Tr>
49 // Only clean the cache for this Region. Caches of child Regions will be
50 // cleaned when the child Regions are deleted.
51 BBNodeMap.clear();
52}
53
54template <class Tr>
56 this->entry.setPointer(BB);
57}
58
59template <class Tr>
61 assert(exit && "No exit to replace!");
62 exit = BB;
63}
64
65template <class Tr>
67 std::vector<RegionT *> RegionQueue;
68 BlockT *OldEntry = getEntry();
69
70 RegionQueue.push_back(static_cast<RegionT *>(this));
71 while (!RegionQueue.empty()) {
72 RegionT *R = RegionQueue.back();
73 RegionQueue.pop_back();
74
75 R->replaceEntry(NewEntry);
76 for (std::unique_ptr<RegionT> &Child : *R) {
77 if (Child->getEntry() == OldEntry)
78 RegionQueue.push_back(Child.get());
79 }
80 }
81}
82
83template <class Tr>
85 std::vector<RegionT *> RegionQueue;
86 BlockT *OldExit = getExit();
87
88 RegionQueue.push_back(static_cast<RegionT *>(this));
89 while (!RegionQueue.empty()) {
90 RegionT *R = RegionQueue.back();
91 RegionQueue.pop_back();
92
93 R->replaceExit(NewExit);
94 for (std::unique_ptr<RegionT> &Child : *R) {
95 if (Child->getExit() == OldExit)
96 RegionQueue.push_back(Child.get());
97 }
98 }
99}
100
101template <class Tr>
102bool RegionBase<Tr>::contains(const BlockT *B) const {
103 BlockT *BB = const_cast<BlockT *>(B);
104
105 if (!DT->getNode(BB))
106 return false;
107
108 BlockT *entry = getEntry(), *exit = getExit();
109
110 // Toplevel region.
111 if (!exit)
112 return true;
113
114 return (DT->dominates(entry, BB) &&
115 !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
116}
117
118template <class Tr>
119bool RegionBase<Tr>::contains(const LoopT *L) const {
120 // BBs that are not part of any loop are element of the Loop
121 // described by the NULL pointer. This loop is not part of any region,
122 // except if the region describes the whole function.
123 if (!L)
124 return getExit() == nullptr;
125
126 if (!contains(L->getHeader()))
127 return false;
128
129 SmallVector<BlockT *, 8> ExitingBlocks;
130 L->getExitingBlocks(ExitingBlocks);
131
132 for (BlockT *BB : ExitingBlocks) {
133 if (!contains(BB))
134 return false;
135 }
136
137 return true;
138}
139
140template <class Tr>
141typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
142 if (!contains(L))
143 return nullptr;
144
145 while (L && contains(L->getParentLoop())) {
146 L = L->getParentLoop();
147 }
148
149 return L;
150}
151
152template <class Tr>
153typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI,
154 BlockT *BB) const {
155 assert(LI && BB && "LI and BB cannot be null!");
156 LoopT *L = LI->getLoopFor(BB);
157 return outermostLoopInRegion(L);
158}
159
160template <class Tr>
161typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
162 auto isEnteringBlock = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
163 assert(!AllowRepeats && "Unexpected parameter value.");
164 return DT->getNode(Pred) && !contains(Pred) ? Pred : nullptr;
165 };
166 BlockT *entry = getEntry();
167 return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(entry),
168 InvBlockTraits::child_end(entry)),
169 isEnteringBlock);
170}
171
172template <class Tr>
174 SmallVectorImpl<BlockT *> &Exitings) const {
175 bool CoverAll = true;
176
177 if (!exit)
178 return CoverAll;
179
180 for (PredIterTy PI = InvBlockTraits::child_begin(exit),
181 PE = InvBlockTraits::child_end(exit);
182 PI != PE; ++PI) {
183 BlockT *Pred = *PI;
184 if (contains(Pred)) {
185 Exitings.push_back(Pred);
186 continue;
187 }
188
189 CoverAll = false;
190 }
191
192 return CoverAll;
193}
194
195template <class Tr>
196typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
197 BlockT *exit = getExit();
198 if (!exit)
199 return nullptr;
200
201 auto isContained = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
202 assert(!AllowRepeats && "Unexpected parameter value.");
203 return contains(Pred) ? Pred : nullptr;
204 };
205 return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(exit),
206 InvBlockTraits::child_end(exit)),
207 isContained);
208}
209
210template <class Tr>
212 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
213}
214
215template <class Tr>
216std::string RegionBase<Tr>::getNameStr() const {
217 std::string exitName;
218 std::string entryName;
219
220 if (getEntry()->getName().empty()) {
221 raw_string_ostream OS(entryName);
222
223 getEntry()->printAsOperand(OS, false);
224 } else
225 entryName = std::string(getEntry()->getName());
226
227 if (getExit()) {
228 if (getExit()->getName().empty()) {
229 raw_string_ostream OS(exitName);
230
231 getExit()->printAsOperand(OS, false);
232 } else
233 exitName = std::string(getExit()->getName());
234 } else
235 exitName = "<Function Return>";
236
237 return entryName + " => " + exitName;
238}
239
240template <class Tr>
241void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
242 if (!contains(BB))
243 report_fatal_error("Broken region found: enumerated BB not in region!");
244
245 BlockT *entry = getEntry(), *exit = getExit();
246
247 for (BlockT *Succ :
248 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
249 if (!contains(Succ) && exit != Succ)
250 report_fatal_error("Broken region found: edges leaving the region must go "
251 "to the exit node!");
252 }
253
254 if (entry != BB) {
255 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
256 InvBlockTraits::child_end(BB))) {
257 // Allow predecessors that are unreachable, as these are ignored during
258 // region analysis.
259 if (!contains(Pred) && DT->isReachableFromEntry(Pred))
260 report_fatal_error("Broken region found: edges entering the region must "
261 "go to the entry node!");
262 }
263 }
264}
265
266template <class Tr>
267void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
268 BlockT *exit = getExit();
269
270 visited->insert(BB);
271
272 verifyBBInRegion(BB);
273
274 for (BlockT *Succ :
275 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
276 if (Succ != exit && visited->find(Succ) == visited->end())
277 verifyWalk(Succ, visited);
278 }
279}
280
281template <class Tr>
283 // Only do verification when user wants to, otherwise this expensive check
284 // will be invoked by PMDataManager::verifyPreservedAnalysis when
285 // a regionpass (marked PreservedAll) finish.
287 return;
288
289 std::set<BlockT *> visited;
290 verifyWalk(getEntry(), &visited);
291}
292
293template <class Tr>
295 for (const std::unique_ptr<RegionT> &R : *this)
296 R->verifyRegionNest();
297
298 verifyRegion();
299}
300
301template <class Tr>
303 return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
304}
305
306template <class Tr>
308 return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
309}
310
311template <class Tr>
315 static_cast<const RegionT *>(this));
316}
317
318template <class Tr>
322 static_cast<const RegionT *>(this));
323}
324
325template <class Tr>
326typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
327 using RegionT = typename Tr::RegionT;
328
329 RegionT *R = RI->getRegionFor(BB);
331 if (!R || R == this)
332 return nullptr;
333
334 // If we pass the BB out of this region, that means our code is broken.
335 assert(contains(R) && "BB not in current region!");
337 while (contains(R->getParent()) && R->getParent() != this)
338 R = R->getParent();
339
340 if (R->getEntry() != BB)
341 return nullptr;
342
343 return R;
344}
346template <class Tr>
347typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
348 assert(contains(BB) && "Can get BB node out of this region!");
349
350 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
351
352 if (at == BBNodeMap.end()) {
353 auto Deconst = const_cast<RegionBase<Tr> *>(this);
354 typename BBNodeMapT::value_type V = {
355 BB,
356 std::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
357 at = BBNodeMap.insert(std::move(V)).first;
358 }
359 return at->second.get();
360}
361
362template <class Tr>
363typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
364 assert(contains(BB) && "Can get BB node out of this region!");
365 if (RegionT *Child = getSubRegionNode(BB))
366 return Child->getNode();
367
368 return getBBNode(BB);
369}
370
371template <class Tr>
373 for (std::unique_ptr<RegionT> &R : *this) {
374 R->parent = To;
375 To->children.push_back(std::move(R));
376 }
377 children.clear();
378}
379
380template <class Tr>
381void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
382 assert(!SubRegion->parent && "SubRegion already has a parent!");
383 assert(llvm::none_of(*this,
384 [&](const std::unique_ptr<RegionT> &R) {
385 return R.get() == SubRegion;
386 }) &&
387 "Subregion already exists!");
388
389 SubRegion->parent = static_cast<RegionT *>(this);
390 children.push_back(std::unique_ptr<RegionT>(SubRegion));
391
392 if (!moveChildren)
393 return;
394
395 assert(SubRegion->children.empty() &&
396 "SubRegions that contain children are not supported");
397
398 for (RegionNodeT *Element : elements()) {
399 if (!Element->isSubRegion()) {
400 BlockT *BB = Element->template getNodeAs<BlockT>();
401
402 if (SubRegion->contains(BB))
403 RI->setRegionFor(BB, SubRegion);
404 }
405 }
406
407 std::vector<std::unique_ptr<RegionT>> Keep;
408 for (std::unique_ptr<RegionT> &R : *this) {
409 if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
410 R->parent = SubRegion;
411 SubRegion->children.push_back(std::move(R));
412 } else
413 Keep.push_back(std::move(R));
414 }
415
416 children.clear();
417 children.insert(
418 children.begin(),
419 std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
420 std::move_iterator<typename RegionSet::iterator>(Keep.end()));
421}
422
423template <class Tr>
424typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
425 assert(Child->parent == this && "Child is not a child of this region!");
426 Child->parent = nullptr;
427 typename RegionSet::iterator I =
428 llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) {
429 return R.get() == Child;
430 });
431 assert(I != children.end() && "Region does not exit. Unable to remove.");
432 children.erase(children.begin() + (I - begin()));
433 return Child;
434}
435
436template <class Tr>
437unsigned RegionBase<Tr>::getDepth() const {
438 unsigned Depth = 0;
439
440 for (RegionT *R = getParent(); R != nullptr; R = R->getParent())
442
443 return Depth;
444}
445
446template <class Tr>
447typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
448 unsigned NumSuccessors = Tr::getNumSuccessors(exit);
449
450 if (NumSuccessors == 0)
451 return nullptr;
452
453 RegionT *R = RI->getRegionFor(exit);
454
455 if (R->getEntry() != exit) {
456 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
457 InvBlockTraits::child_end(getExit())))
458 if (!contains(Pred))
459 return nullptr;
460 if (Tr::getNumSuccessors(exit) == 1)
461 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
462 return nullptr;
463 }
464
465 while (R->getParent() && R->getParent()->getEntry() == exit)
466 R = R->getParent();
467
468 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
469 InvBlockTraits::child_end(getExit()))) {
470 if (!(contains(Pred) || R->contains(Pred)))
471 return nullptr;
472 }
473
474 return new RegionT(getEntry(), R->getExit(), RI, DT);
475}
476
477template <class Tr>
478void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
479 PrintStyle Style) const {
480 if (print_tree)
481 OS.indent(level * 2) << '[' << level << "] " << getNameStr();
482 else
483 OS.indent(level * 2) << getNameStr();
484
485 OS << '\n';
486
487 if (Style != PrintNone) {
488 OS.indent(level * 2) << "{\n";
489 OS.indent(level * 2 + 2);
490
491 if (Style == PrintBB) {
492 for (const auto *BB : blocks())
493 OS << BB->getName() << ", "; // TODO: remove the last ","
494 } else if (Style == PrintRN) {
495 for (const RegionNodeT *Element : elements()) {
496 OS << *Element << ", "; // TODO: remove the last ",
497 }
498 }
500 OS << '\n';
501 }
502
503 if (print_tree) {
504 for (const std::unique_ptr<RegionT> &R : *this)
505 R->print(OS, print_tree, level + 1, Style);
506 }
507
508 if (Style != PrintNone)
509 OS.indent(level * 2) << "} \n";
510}
511
512#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
513template <class Tr>
515 print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
516}
517#endif
518
519template <class Tr>
521 BBNodeMap.clear();
522 for (std::unique_ptr<RegionT> &R : *this)
523 R->clearNodeCache();
524}
525
526//===----------------------------------------------------------------------===//
527// RegionInfoBase implementation
528//
529
530template <class Tr>
532
533template <class Tr>
535 releaseMemory();
536}
537
538template <class Tr>
539void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
540 assert(R && "Re must be non-null");
541 for (const typename Tr::RegionNodeT *Element : R->elements()) {
542 if (Element->isSubRegion()) {
543 const RegionT *SR = Element->template getNodeAs<RegionT>();
544 verifyBBMap(SR);
545 } else {
546 BlockT *BB = Element->template getNodeAs<BlockT>();
547 if (getRegionFor(BB) != R)
548 report_fatal_error("BB map does not match region nesting");
549 }
550 }
552
553template <class Tr>
554bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
555 BlockT *exit) const {
556 for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
557 InvBlockTraits::child_end(BB))) {
558 if (DT->dominates(entry, P) && !DT->dominates(exit, P))
559 return false;
560 }
561
562 return true;
563}
564
565template <class Tr>
566bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
567 assert(entry && exit && "entry and exit must not be null!");
568
569 using DST = typename DomFrontierT::DomSetType;
570
571 DST *entrySuccs = &DF->find(entry)->second;
572
573 // Exit is the header of a loop that contains the entry. In this case,
574 // the dominance frontier must only contain the exit.
575 if (!DT->dominates(entry, exit)) {
576 for (BlockT *successor : *entrySuccs) {
577 if (successor != exit && successor != entry)
578 return false;
579 }
580
581 return true;
582 }
583
584 DST *exitSuccs = &DF->find(exit)->second;
585
586 // Do not allow edges leaving the region.
587 for (BlockT *Succ : *entrySuccs) {
588 if (Succ == exit || Succ == entry)
589 continue;
590 if (!exitSuccs->contains(Succ))
591 return false;
592 if (!isCommonDomFrontier(Succ, entry, exit))
593 return false;
594 }
595
596 // Do not allow edges pointing into the region.
597 for (BlockT *Succ : *exitSuccs) {
598 if (DT->properlyDominates(entry, Succ) && Succ != exit)
599 return false;
600 }
601
602 return true;
603}
604
605template <class Tr>
606void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
607 BBtoBBMap *ShortCut) const {
608 assert(entry && exit && "entry and exit must not be null!");
609
610 typename BBtoBBMap::iterator e = ShortCut->find(exit);
611
612 if (e == ShortCut->end())
613 // No further region at exit available.
614 (*ShortCut)[entry] = exit;
615 else {
616 // We found a region e that starts at exit. Therefore (entry, e->second)
617 // is also a region, that is larger than (entry, exit). Insert the
618 // larger one.
619 BlockT *BB = e->second;
620 (*ShortCut)[entry] = BB;
621 }
622}
623
624template <class Tr>
625typename Tr::DomTreeNodeT *
626RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
627 typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
628
629 if (e == ShortCut->end())
630 return N->getIDom();
631
632 return PDT->getNode(e->second)->getIDom();
633}
634
635template <class Tr>
636bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
637 assert(entry && exit && "entry and exit must not be null!");
638
639 unsigned num_successors =
640 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
641
642 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
643 return true;
644
645 return false;
646}
647
648template <class Tr>
649typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
650 BlockT *exit) {
651 assert(entry && exit && "entry and exit must not be null!");
652
653 if (isTrivialRegion(entry, exit))
654 return nullptr;
656 RegionT *region =
657 new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
658 BBtoRegion.insert({entry, region});
659
660 region->verifyRegion();
661
662 updateStatistics(region);
663 return region;
664}
665
666template <class Tr>
667void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
668 BBtoBBMap *ShortCut) {
669 assert(entry);
670
671 DomTreeNodeT *N = PDT->getNode(entry);
672 if (!N)
673 return;
674
675 RegionT *lastRegion = nullptr;
676 BlockT *lastExit = entry;
677
678 // As only a BasicBlock that postdominates entry can finish a region, walk the
679 // post dominance tree upwards.
680 while ((N = getNextPostDom(N, ShortCut))) {
681 BlockT *exit = N->getBlock();
682
683 if (!exit)
684 break;
685
686 if (isRegion(entry, exit)) {
687 RegionT *newRegion = createRegion(entry, exit);
688
689 if (lastRegion)
690 newRegion->addSubRegion(lastRegion);
691
692 lastRegion = newRegion;
693 lastExit = exit;
694 }
695
696 // This can never be a region, so stop the search.
697 if (!DT->dominates(entry, exit))
698 break;
699 }
700
701 // Tried to create regions from entry to lastExit. Next time take a
702 // shortcut from entry to lastExit.
703 if (lastExit != entry)
704 insertShortCut(entry, lastExit, ShortCut);
705}
706
707template <class Tr>
708void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
709 using FuncPtrT = std::add_pointer_t<FuncT>;
710
711 BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
712 DomTreeNodeT *N = DT->getNode(entry);
713
714 // Iterate over the dominance tree in post order to start with the small
715 // regions from the bottom of the dominance tree. If the small regions are
716 // detected first, detection of bigger regions is faster, as we can jump
717 // over the small regions.
718 for (auto DomNode : post_order(N))
719 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
720}
721
722template <class Tr>
723typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
724 while (region->getParent())
725 region = region->getParent();
726
727 return region;
728}
729
730template <class Tr>
731void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
732 BlockT *BB = N->getBlock();
733
734 // Passed region exit
735 while (BB == region->getExit())
736 region = region->getParent();
737
738 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
739
740 // This basic block is a start block of a region. It is already in the
741 // BBtoRegion relation. Only the child basic blocks have to be updated.
742 if (it != BBtoRegion.end()) {
743 RegionT *newRegion = it->second;
744 region->addSubRegion(getTopMostParent(newRegion));
745 region = newRegion;
746 } else {
747 BBtoRegion[BB] = region;
748 }
749
750 for (DomTreeNodeBase<BlockT> *C : *N) {
751 buildRegionsTree(C, region);
752 }
753}
754
755#ifdef EXPENSIVE_CHECKS
756template <class Tr>
758#else
759template <class Tr>
761#endif
762
763template <class Tr>
764typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
766
767template <class Tr>
769 OS << "Region tree:\n";
770 TopLevelRegion->print(OS, true, 0, printStyle);
771 OS << "End region tree\n";
772}
773
774#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
775template <class Tr>
777#endif
778
779template <class Tr> void RegionInfoBase<Tr>::releaseMemory() {
780 BBtoRegion.clear();
781 if (TopLevelRegion) {
782 delete TopLevelRegion;
783 TopLevelRegion = nullptr;
784 }
785}
786
787template <class Tr>
789 // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
790 // -verify-region-info
792 return;
793
794 TopLevelRegion->verifyRegionNest();
795
796 verifyBBMap(TopLevelRegion);
797}
798
799// Region pass manager support.
800template <class Tr>
801typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
802 return BBtoRegion.lookup(BB);
803}
804
805template <class Tr>
806void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
807 BBtoRegion[BB] = R;
808}
809
810template <class Tr>
811typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
812 return getRegionFor(BB);
813}
814
815template <class Tr>
816typename RegionInfoBase<Tr>::BlockT *
818 BlockT *Exit = nullptr;
819
820 while (true) {
821 // Get largest region that starts at BB.
822 RegionT *R = getRegionFor(BB);
823 while (R && R->getParent() && R->getParent()->getEntry() == BB)
824 R = R->getParent();
825
826 // Get the single exit of BB.
827 if (R && R->getEntry() == BB)
828 Exit = R->getExit();
829 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
830 Exit = *BlockTraits::child_begin(BB);
831 else // No single exit exists.
832 return Exit;
833
834 // Get largest region that starts at Exit.
835 RegionT *ExitR = getRegionFor(Exit);
836 while (ExitR && ExitR->getParent() &&
837 ExitR->getParent()->getEntry() == Exit)
838 ExitR = ExitR->getParent();
839
840 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
841 InvBlockTraits::child_end(Exit))) {
842 if (!R->contains(Pred) && !ExitR->contains(Pred))
843 break;
844 }
845
846 // This stops infinite cycles.
847 if (DT->dominates(Exit, BB))
848 break;
849
850 BB = Exit;
851 }
852
853 return Exit;
854}
855
856template <class Tr>
857typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
858 RegionT *B) const {
859 assert(A && B && "One of the Regions is NULL");
860
861 if (A->contains(B))
862 return A;
863
864 while (!B->contains(A))
865 B = B->getParent();
866
867 return B;
868}
869
870template <class Tr>
871typename Tr::RegionT *
873 RegionT *ret = Regions.pop_back_val();
874
875 for (RegionT *R : Regions)
876 ret = getCommonRegion(ret, R);
877
878 return ret;
879}
880
881template <class Tr>
882typename Tr::RegionT *
884 RegionT *ret = getRegionFor(BBs.back());
885 BBs.pop_back();
886
887 for (BlockT *BB : BBs)
888 ret = getCommonRegion(ret, getRegionFor(BB));
889
890 return ret;
891}
892
893template <class Tr>
894void RegionInfoBase<Tr>::calculate(FuncT &F) {
895 using FuncPtrT = std::add_pointer_t<FuncT>;
896
897 // ShortCut a function where for every BB the exit of the largest region
898 // starting with BB is stored. These regions can be threated as single BBS.
899 // This improves performance on linear CFGs.
900 BBtoBBMap ShortCut;
901
902 scanForRegions(F, &ShortCut);
904 buildRegionsTree(DT->getNode(BB), TopLevelRegion);
905}
906
907} // end namespace llvm
908
909#undef DEBUG_TYPE
910
911#endif // LLVM_ANALYSIS_REGIONINFOIMPL_H
static const Function * getParent(const Value *V)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:469
A single entry single exit Region.
Definition: RegionInfo.h:254
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
void clearNodeCache()
Clear the cache for BB RegionNodes.
std::string getNameStr() const
Returns the name of the Region.
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:370
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
unsigned getDepth() const
Get the nesting level of this Region.
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
void dump() const
Print the region to stderr.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
element_iterator element_begin()
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
void verifyRegion() const
Verify if the region is a correct region.
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
element_iterator element_end()
bool isSimple() const
Is this a simple region?
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
~RegionBase()
Delete the Region and all its subregions.
PrintStyle
PrintStyle - Print region in difference ways.
Definition: RegionInfo.h:429
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:674
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
static bool VerifyRegionInfo
Definition: RegionInfo.h:802
void print(raw_ostream &OS) const
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
static RegionT::PrintStyle printStyle
Definition: RegionInfo.h:803
void verifyAnalysis() const
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:117
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
constexpr double e
Definition: MathExtras.h:31
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< po_iterator< T > > post_order(const T &G)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1740
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1753
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
@ Keep
No function return thunk.
#define N