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