LLVM 17.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 if (!contains(Pred))
258 report_fatal_error("Broken region found: edges entering the region must "
259 "go to the entry node!");
260 }
261 }
262}
263
264template <class Tr>
265void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
266 BlockT *exit = getExit();
267
268 visited->insert(BB);
269
270 verifyBBInRegion(BB);
271
272 for (BlockT *Succ :
273 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
274 if (Succ != exit && visited->find(Succ) == visited->end())
275 verifyWalk(Succ, visited);
276 }
277}
278
279template <class Tr>
281 // Only do verification when user wants to, otherwise this expensive check
282 // will be invoked by PMDataManager::verifyPreservedAnalysis when
283 // a regionpass (marked PreservedAll) finish.
285 return;
286
287 std::set<BlockT *> visited;
288 verifyWalk(getEntry(), &visited);
289}
290
291template <class Tr>
293 for (const std::unique_ptr<RegionT> &R : *this)
294 R->verifyRegionNest();
295
296 verifyRegion();
297}
298
299template <class Tr>
301 return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
302}
303
304template <class Tr>
306 return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
307}
308
309template <class Tr>
313 static_cast<const RegionT *>(this));
314}
315
316template <class Tr>
320 static_cast<const RegionT *>(this));
321}
322
323template <class Tr>
324typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
325 using RegionT = typename Tr::RegionT;
326
327 RegionT *R = RI->getRegionFor(BB);
328
329 if (!R || R == this)
330 return nullptr;
331
332 // If we pass the BB out of this region, that means our code is broken.
333 assert(contains(R) && "BB not in current region!");
334
335 while (contains(R->getParent()) && R->getParent() != this)
336 R = R->getParent();
337
338 if (R->getEntry() != BB)
339 return nullptr;
340
341 return R;
342}
343
344template <class Tr>
345typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
346 assert(contains(BB) && "Can get BB node out of this region!");
347
348 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
349
350 if (at == BBNodeMap.end()) {
351 auto Deconst = const_cast<RegionBase<Tr> *>(this);
352 typename BBNodeMapT::value_type V = {
353 BB,
354 std::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
355 at = BBNodeMap.insert(std::move(V)).first;
356 }
357 return at->second.get();
358}
359
360template <class Tr>
361typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
362 assert(contains(BB) && "Can get BB node out of this region!");
363 if (RegionT *Child = getSubRegionNode(BB))
364 return Child->getNode();
365
366 return getBBNode(BB);
367}
368
369template <class Tr>
371 for (std::unique_ptr<RegionT> &R : *this) {
372 R->parent = To;
373 To->children.push_back(std::move(R));
374 }
375 children.clear();
376}
377
378template <class Tr>
379void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
380 assert(!SubRegion->parent && "SubRegion already has a parent!");
381 assert(llvm::none_of(*this,
382 [&](const std::unique_ptr<RegionT> &R) {
383 return R.get() == SubRegion;
384 }) &&
385 "Subregion already exists!");
386
387 SubRegion->parent = static_cast<RegionT *>(this);
388 children.push_back(std::unique_ptr<RegionT>(SubRegion));
389
390 if (!moveChildren)
391 return;
392
393 assert(SubRegion->children.empty() &&
394 "SubRegions that contain children are not supported");
395
396 for (RegionNodeT *Element : elements()) {
397 if (!Element->isSubRegion()) {
398 BlockT *BB = Element->template getNodeAs<BlockT>();
399
400 if (SubRegion->contains(BB))
401 RI->setRegionFor(BB, SubRegion);
402 }
403 }
404
405 std::vector<std::unique_ptr<RegionT>> Keep;
406 for (std::unique_ptr<RegionT> &R : *this) {
407 if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
408 R->parent = SubRegion;
409 SubRegion->children.push_back(std::move(R));
410 } else
411 Keep.push_back(std::move(R));
413
414 children.clear();
415 children.insert(
416 children.begin(),
417 std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
418 std::move_iterator<typename RegionSet::iterator>(Keep.end()));
420
421template <class Tr>
422typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
423 assert(Child->parent == this && "Child is not a child of this region!");
424 Child->parent = nullptr;
425 typename RegionSet::iterator I =
426 llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) {
427 return R.get() == Child;
428 });
429 assert(I != children.end() && "Region does not exit. Unable to remove.");
430 children.erase(children.begin() + (I - begin()));
431 return Child;
432}
433
434template <class Tr>
435unsigned RegionBase<Tr>::getDepth() const {
436 unsigned Depth = 0;
437
438 for (RegionT *R = getParent(); R != nullptr; R = R->getParent())
439 ++Depth;
440
441 return Depth;
442}
443
444template <class Tr>
445typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
446 unsigned NumSuccessors = Tr::getNumSuccessors(exit);
447
448 if (NumSuccessors == 0)
449 return nullptr;
450
451 RegionT *R = RI->getRegionFor(exit);
452
453 if (R->getEntry() != exit) {
454 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
455 InvBlockTraits::child_end(getExit())))
456 if (!contains(Pred))
457 return nullptr;
458 if (Tr::getNumSuccessors(exit) == 1)
459 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
460 return nullptr;
461 }
462
463 while (R->getParent() && R->getParent()->getEntry() == exit)
464 R = R->getParent();
465
466 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
467 InvBlockTraits::child_end(getExit()))) {
468 if (!(contains(Pred) || R->contains(Pred)))
469 return nullptr;
470 }
471
472 return new RegionT(getEntry(), R->getExit(), RI, DT);
473}
474
475template <class Tr>
476void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
477 PrintStyle Style) const {
478 if (print_tree)
479 OS.indent(level * 2) << '[' << level << "] " << getNameStr();
480 else
481 OS.indent(level * 2) << getNameStr();
482
483 OS << '\n';
484
485 if (Style != PrintNone) {
486 OS.indent(level * 2) << "{\n";
487 OS.indent(level * 2 + 2);
489 if (Style == PrintBB) {
490 for (const auto *BB : blocks())
491 OS << BB->getName() << ", "; // TODO: remove the last ","
492 } else if (Style == PrintRN) {
493 for (const RegionNodeT *Element : elements()) {
494 OS << *Element << ", "; // TODO: remove the last ",
495 }
496 }
497
498 OS << '\n';
500
501 if (print_tree) {
502 for (const std::unique_ptr<RegionT> &R : *this)
503 R->print(OS, print_tree, level + 1, Style);
504 }
506 if (Style != PrintNone)
507 OS.indent(level * 2) << "} \n";
508}
509
510#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
511template <class Tr>
514}
515#endif
516
517template <class Tr>
519 BBNodeMap.clear();
520 for (std::unique_ptr<RegionT> &R : *this)
521 R->clearNodeCache();
522}
523
524//===----------------------------------------------------------------------===//
525// RegionInfoBase implementation
527
528template <class Tr>
530
531template <class Tr>
533 releaseMemory();
534}
535
536template <class Tr>
537void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
538 assert(R && "Re must be non-null");
539 for (const typename Tr::RegionNodeT *Element : R->elements()) {
540 if (Element->isSubRegion()) {
541 const RegionT *SR = Element->template getNodeAs<RegionT>();
542 verifyBBMap(SR);
543 } else {
544 BlockT *BB = Element->template getNodeAs<BlockT>();
545 if (getRegionFor(BB) != R)
546 report_fatal_error("BB map does not match region nesting");
547 }
548 }
549}
550
551template <class Tr>
552bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
553 BlockT *exit) const {
554 for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
555 InvBlockTraits::child_end(BB))) {
556 if (DT->dominates(entry, P) && !DT->dominates(exit, P))
557 return false;
558 }
559
560 return true;
561}
562
563template <class Tr>
564bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
565 assert(entry && exit && "entry and exit must not be null!");
566
567 using DST = typename DomFrontierT::DomSetType;
568
569 DST *entrySuccs = &DF->find(entry)->second;
570
571 // Exit is the header of a loop that contains the entry. In this case,
572 // the dominance frontier must only contain the exit.
573 if (!DT->dominates(entry, exit)) {
574 for (BlockT *successor : *entrySuccs) {
575 if (successor != exit && successor != entry)
576 return false;
577 }
578
579 return true;
580 }
581
582 DST *exitSuccs = &DF->find(exit)->second;
583
584 // Do not allow edges leaving the region.
585 for (BlockT *Succ : *entrySuccs) {
586 if (Succ == exit || Succ == entry)
587 continue;
588 if (exitSuccs->find(Succ) == exitSuccs->end())
589 return false;
590 if (!isCommonDomFrontier(Succ, entry, exit))
591 return false;
592 }
593
594 // Do not allow edges pointing into the region.
595 for (BlockT *Succ : *exitSuccs) {
596 if (DT->properlyDominates(entry, Succ) && Succ != exit)
597 return false;
598 }
599
600 return true;
601}
602
603template <class Tr>
604void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
605 BBtoBBMap *ShortCut) const {
606 assert(entry && exit && "entry and exit must not be null!");
607
608 typename BBtoBBMap::iterator e = ShortCut->find(exit);
609
610 if (e == ShortCut->end())
611 // No further region at exit available.
612 (*ShortCut)[entry] = exit;
613 else {
614 // We found a region e that starts at exit. Therefore (entry, e->second)
615 // is also a region, that is larger than (entry, exit). Insert the
616 // larger one.
617 BlockT *BB = e->second;
618 (*ShortCut)[entry] = BB;
619 }
620}
621
622template <class Tr>
623typename Tr::DomTreeNodeT *
624RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
625 typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
626
627 if (e == ShortCut->end())
628 return N->getIDom();
629
630 return PDT->getNode(e->second)->getIDom();
631}
632
633template <class Tr>
634bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
635 assert(entry && exit && "entry and exit must not be null!");
636
637 unsigned num_successors =
638 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
639
640 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
641 return true;
642
643 return false;
644}
645
646template <class Tr>
647typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
648 BlockT *exit) {
649 assert(entry && exit && "entry and exit must not be null!");
651 if (isTrivialRegion(entry, exit))
652 return nullptr;
653
654 RegionT *region =
655 new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
656 BBtoRegion.insert({entry, region});
657
658#ifdef EXPENSIVE_CHECKS
659 region->verifyRegion();
660#else
661 LLVM_DEBUG(region->verifyRegion());
662#endif
663
664 updateStatistics(region);
665 return region;
666}
667
668template <class Tr>
669void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
670 BBtoBBMap *ShortCut) {
671 assert(entry);
672
673 DomTreeNodeT *N = PDT->getNode(entry);
674 if (!N)
675 return;
676
677 RegionT *lastRegion = nullptr;
678 BlockT *lastExit = entry;
679
680 // As only a BasicBlock that postdominates entry can finish a region, walk the
681 // post dominance tree upwards.
682 while ((N = getNextPostDom(N, ShortCut))) {
683 BlockT *exit = N->getBlock();
684
685 if (!exit)
686 break;
687
688 if (isRegion(entry, exit)) {
689 RegionT *newRegion = createRegion(entry, exit);
690
691 if (lastRegion)
692 newRegion->addSubRegion(lastRegion);
693
694 lastRegion = newRegion;
695 lastExit = exit;
696 }
697
698 // This can never be a region, so stop the search.
699 if (!DT->dominates(entry, exit))
700 break;
701 }
702
703 // Tried to create regions from entry to lastExit. Next time take a
704 // shortcut from entry to lastExit.
705 if (lastExit != entry)
706 insertShortCut(entry, lastExit, ShortCut);
707}
708
709template <class Tr>
710void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
711 using FuncPtrT = std::add_pointer_t<FuncT>;
712
713 BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
714 DomTreeNodeT *N = DT->getNode(entry);
715
716 // Iterate over the dominance tree in post order to start with the small
717 // regions from the bottom of the dominance tree. If the small regions are
718 // detected first, detection of bigger regions is faster, as we can jump
719 // over the small regions.
720 for (auto DomNode : post_order(N))
721 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
722}
723
724template <class Tr>
725typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
726 while (region->getParent())
727 region = region->getParent();
728
729 return region;
730}
731
732template <class Tr>
733void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
734 BlockT *BB = N->getBlock();
735
736 // Passed region exit
737 while (BB == region->getExit())
738 region = region->getParent();
739
740 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
741
742 // This basic block is a start block of a region. It is already in the
743 // BBtoRegion relation. Only the child basic blocks have to be updated.
744 if (it != BBtoRegion.end()) {
745 RegionT *newRegion = it->second;
746 region->addSubRegion(getTopMostParent(newRegion));
747 region = newRegion;
748 } else {
749 BBtoRegion[BB] = region;
750 }
751
752 for (DomTreeNodeBase<BlockT> *C : *N) {
753 buildRegionsTree(C, region);
754 }
755}
756
757#ifdef EXPENSIVE_CHECKS
758template <class Tr>
760#else
761template <class Tr>
763#endif
764
765template <class Tr>
766typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
768
769template <class Tr>
771 OS << "Region tree:\n";
772 TopLevelRegion->print(OS, true, 0, printStyle);
773 OS << "End region tree\n";
774}
775
776#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
777template <class Tr>
779#endif
780
781template <class Tr> void RegionInfoBase<Tr>::releaseMemory() {
782 BBtoRegion.clear();
783 if (TopLevelRegion) {
784 delete TopLevelRegion;
785 TopLevelRegion = nullptr;
786 }
787}
788
789template <class Tr>
791 // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
792 // -verify-region-info
794 return;
795
796 TopLevelRegion->verifyRegionNest();
797
798 verifyBBMap(TopLevelRegion);
799}
800
801// Region pass manager support.
802template <class Tr>
803typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
804 return BBtoRegion.lookup(BB);
806
807template <class Tr>
808void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
809 BBtoRegion[BB] = R;
811
812template <class Tr>
813typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
814 return getRegionFor(BB);
815}
816
817template <class Tr>
818typename RegionInfoBase<Tr>::BlockT *
820 BlockT *Exit = nullptr;
821
822 while (true) {
823 // Get largest region that starts at BB.
824 RegionT *R = getRegionFor(BB);
825 while (R && R->getParent() && R->getParent()->getEntry() == BB)
826 R = R->getParent();
827
828 // Get the single exit of BB.
829 if (R && R->getEntry() == BB)
830 Exit = R->getExit();
831 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
832 Exit = *BlockTraits::child_begin(BB);
833 else // No single exit exists.
834 return Exit;
835
836 // Get largest region that starts at Exit.
837 RegionT *ExitR = getRegionFor(Exit);
838 while (ExitR && ExitR->getParent() &&
839 ExitR->getParent()->getEntry() == Exit)
840 ExitR = ExitR->getParent();
841
842 for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
843 InvBlockTraits::child_end(Exit))) {
844 if (!R->contains(Pred) && !ExitR->contains(Pred))
845 break;
846 }
847
848 // This stops infinite cycles.
849 if (DT->dominates(Exit, BB))
850 break;
851
852 BB = Exit;
853 }
854
855 return Exit;
856}
857
858template <class Tr>
859typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
860 RegionT *B) const {
861 assert(A && B && "One of the Regions is NULL");
862
863 if (A->contains(B))
864 return A;
865
866 while (!B->contains(A))
867 B = B->getParent();
868
869 return B;
870}
871
872template <class Tr>
873typename Tr::RegionT *
875 RegionT *ret = Regions.pop_back_val();
877 for (RegionT *R : Regions)
878 ret = getCommonRegion(ret, R);
879
880 return ret;
881}
882
883template <class Tr>
884typename Tr::RegionT *
886 RegionT *ret = getRegionFor(BBs.back());
887 BBs.pop_back();
888
889 for (BlockT *BB : BBs)
890 ret = getCommonRegion(ret, getRegionFor(BB));
891
892 return ret;
893}
894
895template <class Tr>
896void RegionInfoBase<Tr>::calculate(FuncT &F) {
897 using FuncPtrT = std::add_pointer_t<FuncT>;
898
899 // ShortCut a function where for every BB the exit of the largest region
900 // starting with BB is stored. These regions can be threated as single BBS.
901 // This improves performance on linear CFGs.
902 BBtoBBMap ShortCut;
903
904 scanForRegions(F, &ShortCut);
906 buildRegionsTree(DT->getNode(BB), TopLevelRegion);
907}
908
909} // end namespace llvm
910
911#undef DEBUG_TYPE
912
913#endif // LLVM_ANALYSIS_REGIONINFOIMPL_H
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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
print Instructions which execute on loop entry
#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.
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:467
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:1749
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
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:1762
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
@ Keep
No function return thunk.
#define N