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