include/llvm/Analysis/RegionInfoImpl.h

   1 //===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // Detects single entry single exit regions in the control flow graph.
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
  12 #define LLVM_ANALYSIS_REGIONINFOIMPL_H
  13
  14 #include "llvm/ADT/GraphTraits.h"
  15 #include "llvm/ADT/PostOrderIterator.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/iterator_range.h"
  19 #include "llvm/Analysis/DominanceFrontier.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/PostDominators.h"
  22 #include "llvm/Analysis/RegionInfo.h"
  23 #include "llvm/Analysis/RegionIterator.h"
  24 #include "llvm/Config/llvm-config.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <algorithm>
  29 #include <cassert>
  30 #include <iterator>
  31 #include <memory>
  32 #include <set>
  33 #include <string>
  34 #include <type_traits>
  35 #include <vector>
  36
  37 #define DEBUG_TYPE "region"
  38
  39 namespace llvm {
  40
  41 //===----------------------------------------------------------------------===//
  42 /// RegionBase Implementation
  43 template <class Tr>
  44 RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit,
  45                            typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
  46                            RegionT *Parent)
  47     : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
  48
  49 template <class Tr>
  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>
  57 void RegionBase<Tr>::replaceEntry(BlockT *BB) {
  58   this->entry.setPointer(BB);
  59 }
  60
  61 template <class Tr>
  62 void RegionBase<Tr>::replaceExit(BlockT *BB) {
  63   assert(exit && "No exit to replace!");
  64   exit = BB;
  65 }
  66
  67 template <class Tr>
  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>
  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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 225 bool RegionBase<Tr>::isSimple() const {
 226   return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
 227 }
 228
 229 template <class Tr>
 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 = 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 = getExit()->getName();
 248   } else
 249     exitName = "<Function Return>";
 250
 251   return entryName + " => " + exitName;
 252 }
 253
 254 template <class Tr>
 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>
 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>
 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>
 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>
 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>
 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
 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
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 526 void RegionBase<Tr>::dump() const {
 527   print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
 528 }
 529 #endif
 530
 531 template <class Tr>
 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>
 546 RegionInfoBase<Tr>::~RegionInfoBase() {
 547   releaseMemory();
 548 }
 549
 550 template <class Tr>
 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>
 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>
 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 (typename DST::iterator SI = entrySuccs->begin(),
 589                                 SE = entrySuccs->end();
 590          SI != SE; ++SI) {
 591       if (*SI != exit && *SI != entry)
 592         return false;
 593     }
 594
 595     return true;
 596   }
 597
 598   DST *exitSuccs = &DF->find(exit)->second;
 599
 600   // Do not allow edges leaving the region.
 601   for (BlockT *Succ : *entrySuccs) {
 602     if (Succ == exit || Succ == entry)
 603       continue;
 604     if (exitSuccs->find(Succ) == exitSuccs->end())
 605       return false;
 606     if (!isCommonDomFrontier(Succ, entry, exit))
 607       return false;
 608   }
 609
 610   // Do not allow edges pointing into the region.
 611   for (BlockT *Succ : *exitSuccs) {
 612     if (DT->properlyDominates(entry, Succ) && Succ != exit)
 613       return false;
 614   }
 615
 616   return true;
 617 }
 618
 619 template <class Tr>
 620 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
 621                                         BBtoBBMap *ShortCut) const {
 622   assert(entry && exit && "entry and exit must not be null!");
 623
 624   typename BBtoBBMap::iterator e = ShortCut->find(exit);
 625
 626   if (e == ShortCut->end())
 627     // No further region at exit available.
 628     (*ShortCut)[entry] = exit;
 629   else {
 630     // We found a region e that starts at exit. Therefore (entry, e->second)
 631     // is also a region, that is larger than (entry, exit). Insert the
 632     // larger one.
 633     BlockT *BB = e->second;
 634     (*ShortCut)[entry] = BB;
 635   }
 636 }
 637
 638 template <class Tr>
 639 typename Tr::DomTreeNodeT *
 640 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
 641   typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
 642
 643   if (e == ShortCut->end())
 644     return N->getIDom();
 645
 646   return PDT->getNode(e->second)->getIDom();
 647 }
 648
 649 template <class Tr>
 650 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
 651   assert(entry && exit && "entry and exit must not be null!");
 652
 653   unsigned num_successors =
 654       BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
 655
 656   if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
 657     return true;
 658
 659   return false;
 660 }
 661
 662 template <class Tr>
 663 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
 664                                                        BlockT *exit) {
 665   assert(entry && exit && "entry and exit must not be null!");
 666
 667   if (isTrivialRegion(entry, exit))
 668     return nullptr;
 669
 670   RegionT *region =
 671       new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
 672   BBtoRegion.insert({entry, region});
 673
 674 #ifdef EXPENSIVE_CHECKS
 675   region->verifyRegion();
 676 #else
 677   LLVM_DEBUG(region->verifyRegion());
 678 #endif
 679
 680   updateStatistics(region);
 681   return region;
 682 }
 683
 684 template <class Tr>
 685 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
 686                                               BBtoBBMap *ShortCut) {
 687   assert(entry);
 688
 689   DomTreeNodeT *N = PDT->getNode(entry);
 690   if (!N)
 691     return;
 692
 693   RegionT *lastRegion = nullptr;
 694   BlockT *lastExit = entry;
 695
 696   // As only a BasicBlock that postdominates entry can finish a region, walk the
 697   // post dominance tree upwards.
 698   while ((N = getNextPostDom(N, ShortCut))) {
 699     BlockT *exit = N->getBlock();
 700
 701     if (!exit)
 702       break;
 703
 704     if (isRegion(entry, exit)) {
 705       RegionT *newRegion = createRegion(entry, exit);
 706
 707       if (lastRegion)
 708         newRegion->addSubRegion(lastRegion);
 709
 710       lastRegion = newRegion;
 711       lastExit = exit;
 712     }
 713
 714     // This can never be a region, so stop the search.
 715     if (!DT->dominates(entry, exit))
 716       break;
 717   }
 718
 719   // Tried to create regions from entry to lastExit.  Next time take a
 720   // shortcut from entry to lastExit.
 721   if (lastExit != entry)
 722     insertShortCut(entry, lastExit, ShortCut);
 723 }
 724
 725 template <class Tr>
 726 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
 727   using FuncPtrT = typename std::add_pointer<FuncT>::type;
 728
 729   BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
 730   DomTreeNodeT *N = DT->getNode(entry);
 731
 732   // Iterate over the dominance tree in post order to start with the small
 733   // regions from the bottom of the dominance tree.  If the small regions are
 734   // detected first, detection of bigger regions is faster, as we can jump
 735   // over the small regions.
 736   for (auto DomNode : post_order(N))
 737     findRegionsWithEntry(DomNode->getBlock(), ShortCut);
 738 }
 739
 740 template <class Tr>
 741 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
 742   while (region->getParent())
 743     region = region->getParent();
 744
 745   return region;
 746 }
 747
 748 template <class Tr>
 749 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
 750   BlockT *BB = N->getBlock();
 751
 752   // Passed region exit
 753   while (BB == region->getExit())
 754     region = region->getParent();
 755
 756   typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
 757
 758   // This basic block is a start block of a region. It is already in the
 759   // BBtoRegion relation. Only the child basic blocks have to be updated.
 760   if (it != BBtoRegion.end()) {
 761     RegionT *newRegion = it->second;
 762     region->addSubRegion(getTopMostParent(newRegion));
 763     region = newRegion;
 764   } else {
 765     BBtoRegion[BB] = region;
 766   }
 767
 768   for (DomTreeNodeBase<BlockT> *C : *N) {
 769     buildRegionsTree(C, region);
 770   }
 771 }
 772
 773 #ifdef EXPENSIVE_CHECKS
 774 template <class Tr>
 775 bool RegionInfoBase<Tr>::VerifyRegionInfo = true;
 776 #else
 777 template <class Tr>
 778 bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
 779 #endif
 780
 781 template <class Tr>
 782 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
 783     RegionBase<Tr>::PrintNone;
 784
 785 template <class Tr>
 786 void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
 787   OS << "Region tree:\n";
 788   TopLevelRegion->print(OS, true, 0, printStyle);
 789   OS << "End region tree\n";
 790 }
 791
 792 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 793 template <class Tr>
 794 void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
 795 #endif
 796
 797 template <class Tr>
 798 void RegionInfoBase<Tr>::releaseMemory() {
 799   BBtoRegion.clear();
 800   if (TopLevelRegion)
 801     delete TopLevelRegion;
 802   TopLevelRegion = nullptr;
 803 }
 804
 805 template <class Tr>
 806 void RegionInfoBase<Tr>::verifyAnalysis() const {
 807   // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
 808   // -verify-region-info
 809   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
 810     return;
 811
 812   TopLevelRegion->verifyRegionNest();
 813
 814   verifyBBMap(TopLevelRegion);
 815 }
 816
 817 // Region pass manager support.
 818 template <class Tr>
 819 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
 820   typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
 821   return I != BBtoRegion.end() ? I->second : nullptr;
 822 }
 823
 824 template <class Tr>
 825 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
 826   BBtoRegion[BB] = R;
 827 }
 828
 829 template <class Tr>
 830 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
 831   return getRegionFor(BB);
 832 }
 833
 834 template <class Tr>
 835 typename RegionInfoBase<Tr>::BlockT *
 836 RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const {
 837   BlockT *Exit = nullptr;
 838
 839   while (true) {
 840     // Get largest region that starts at BB.
 841     RegionT *R = getRegionFor(BB);
 842     while (R && R->getParent() && R->getParent()->getEntry() == BB)
 843       R = R->getParent();
 844
 845     // Get the single exit of BB.
 846     if (R && R->getEntry() == BB)
 847       Exit = R->getExit();
 848     else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
 849       Exit = *BlockTraits::child_begin(BB);
 850     else // No single exit exists.
 851       return Exit;
 852
 853     // Get largest region that starts at Exit.
 854     RegionT *ExitR = getRegionFor(Exit);
 855     while (ExitR && ExitR->getParent() &&
 856            ExitR->getParent()->getEntry() == Exit)
 857       ExitR = ExitR->getParent();
 858
 859     for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
 860                                    InvBlockTraits::child_end(Exit))) {
 861       if (!R->contains(Pred) && !ExitR->contains(Pred))
 862         break;
 863     }
 864
 865     // This stops infinite cycles.
 866     if (DT->dominates(Exit, BB))
 867       break;
 868
 869     BB = Exit;
 870   }
 871
 872   return Exit;
 873 }
 874
 875 template <class Tr>
 876 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
 877                                                           RegionT *B) const {
 878   assert(A && B && "One of the Regions is NULL");
 879
 880   if (A->contains(B))
 881     return A;
 882
 883   while (!B->contains(A))
 884     B = B->getParent();
 885
 886   return B;
 887 }
 888
 889 template <class Tr>
 890 typename Tr::RegionT *
 891 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const {
 892   RegionT *ret = Regions.back();
 893   Regions.pop_back();
 894
 895   for (RegionT *R : Regions)
 896     ret = getCommonRegion(ret, R);
 897
 898   return ret;
 899 }
 900
 901 template <class Tr>
 902 typename Tr::RegionT *
 903 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const {
 904   RegionT *ret = getRegionFor(BBs.back());
 905   BBs.pop_back();
 906
 907   for (BlockT *BB : BBs)
 908     ret = getCommonRegion(ret, getRegionFor(BB));
 909
 910   return ret;
 911 }
 912
 913 template <class Tr>
 914 void RegionInfoBase<Tr>::calculate(FuncT &F) {
 915   using FuncPtrT = typename std::add_pointer<FuncT>::type;
 916
 917   // ShortCut a function where for every BB the exit of the largest region
 918   // starting with BB is stored. These regions can be threated as single BBS.
 919   // This improves performance on linear CFGs.
 920   BBtoBBMap ShortCut;
 921
 922   scanForRegions(F, &ShortCut);
 923   BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
 924   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
 925 }
 926
 927 } // end namespace llvm
 928
 929 #undef DEBUG_TYPE
 930
 931 #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H