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