contrib/llvm/include/llvm/Analysis/RegionInfoImpl.h

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