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 39namespace llvm { 40 41//===----------------------------------------------------------------------===// 42/// RegionBase Implementation 43template <class Tr> 44RegionBase<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 49template <class Tr> 50RegionBase<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 56template <class Tr> 57void RegionBase<Tr>::replaceEntry(BlockT *BB) { 58 this->entry.setPointer(BB); 59} 60 61template <class Tr> 62void RegionBase<Tr>::replaceExit(BlockT *BB) { 63 assert(exit && "No exit to replace!"); 64 exit = BB; 65} 66 67template <class Tr> 68void 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 85template <class Tr> 86void 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 103template <class Tr> 104bool 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 120template <class Tr> 121bool 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 142template <class Tr> 143typename 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 154template <class Tr> 155typename 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 162template <class Tr> 163typename 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 180template <class Tr> 181bool 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 203template <class Tr> 204typename 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 224template <class Tr> 225bool RegionBase<Tr>::isSimple() const { 226 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); 227} 228 229template <class Tr> 230std::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 254template <class Tr> 255void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const { 256 if (!contains(BB)) 257 llvm_unreachable("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 llvm_unreachable("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 llvm_unreachable("Broken region found: edges entering the region must " 273 "go to the entry node!"); 274 } 275 } 276} 277 278template <class Tr> 279void 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 293template <class Tr> 294void 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 305template <class Tr> 306void RegionBase<Tr>::verifyRegionNest() const { 307 for (const std::unique_ptr<RegionT> &R : *this) 308 R->verifyRegionNest(); 309 310 verifyRegion(); 311} 312 313template <class Tr> 314typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() { 315 return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this)); 316} 317 318template <class Tr> 319typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() { 320 return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this)); 321} 322 323template <class Tr> 324typename RegionBase<Tr>::const_element_iterator 325RegionBase<Tr>::element_begin() const { 326 return GraphTraits<const RegionT *>::nodes_begin( 327 static_cast<const RegionT *>(this)); 328} 329 330template <class Tr> 331typename RegionBase<Tr>::const_element_iterator 332RegionBase<Tr>::element_end() const { 333 return GraphTraits<const RegionT *>::nodes_end( 334 static_cast<const RegionT *>(this)); 335} 336 337template <class Tr> 338typename 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 358template <class Tr> 359typename 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 llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)}; 369 at = BBNodeMap.insert(std::move(V)).first; 370 } 371 return at->second.get(); 372} 373 374template <class Tr> 375typename 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 383template <class Tr> 384void 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 392template <class Tr> 393void 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 435template <class Tr> 436typename 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 448template <class Tr> 449unsigned 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 458template <class Tr> 459typename 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 489template <class Tr> 490void 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) 525template <class Tr> 526void RegionBase<Tr>::dump() const { 527 print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle); 528} 529#endif 530 531template <class Tr> 532void 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 542template <class Tr> 543RegionInfoBase<Tr>::RegionInfoBase() = default; 544 545template <class Tr> 546RegionInfoBase<Tr>::~RegionInfoBase() { 547 releaseMemory(); 548} 549 550template <class Tr> 551void 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 llvm_unreachable("BB map does not match region nesting"); 561 } 562 } 563} 564 565template <class Tr> 566bool 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 577template <class Tr> 578bool 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 619template <class Tr> 620void 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 638template <class Tr> 639typename Tr::DomTreeNodeT * 640RegionInfoBase<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 649template <class Tr> 650bool 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 662template <class Tr> 663typename 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 DEBUG(region->verifyRegion()); 678#endif 679 680 updateStatistics(region); 681 return region; 682} 683 684template <class Tr> 685void 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 725template <class Tr> 726void 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 740template <class Tr> 741typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) { 742 while (region->getParent()) 743 region = region->getParent(); 744 745 return region; 746} 747 748template <class Tr> 749void 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 774template <class Tr> 775bool RegionInfoBase<Tr>::VerifyRegionInfo = true; 776#else 777template <class Tr> 778bool RegionInfoBase<Tr>::VerifyRegionInfo = false; 779#endif 780 781template <class Tr> 782typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle = 783 RegionBase<Tr>::PrintNone; 784 785template <class Tr> 786void 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) 793template <class Tr> 794void RegionInfoBase<Tr>::dump() const { print(dbgs()); } 795#endif 796 797template <class Tr> 798void RegionInfoBase<Tr>::releaseMemory() { 799 BBtoRegion.clear(); 800 if (TopLevelRegion) 801 delete TopLevelRegion; 802 TopLevelRegion = nullptr; 803} 804 805template <class Tr> 806void 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. 818template <class Tr> 819typename 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 824template <class Tr> 825void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) { 826 BBtoRegion[BB] = R; 827} 828 829template <class Tr> 830typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const { 831 return getRegionFor(BB); 832} 833 834template <class Tr> 835typename RegionInfoBase<Tr>::BlockT * 836RegionInfoBase<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 875template <class Tr> 876typename 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 889template <class Tr> 890typename Tr::RegionT * 891RegionInfoBase<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 901template <class Tr> 902typename Tr::RegionT * 903RegionInfoBase<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 913template <class Tr> 914void 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 932